【2021牛客寒假第六场】B-系数 傻逼题

传送门：https://ac.nowcoder.com/acm/contest/9986/B

题意

$输出(x^2+x+1)^n的第k项\%3。$

思路

看到数据范围就知道，每次查询必须O(1)或者O(logn)，直接就想到了Lucas。

但是赛中的时候想的思路特别麻烦，想了我将近3个小时，一直以为是找规律题，赛后突发奇想，真就傻逼题。

因为是\%3，所以次幂里面可以+3x的任意倍数而保持不变，即

$$(x^2+x+1)^n=(x^2-2x+1)^n=(x-1)^{2n}$$

所以第k项系数为$C_{2n}^kx^k(-1)^{2n-k}$。

因为n和k都很大，所以要用Lucas优化一下。

总时间复杂度为$O(N+T\log n)$

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
##include "bits/stdc++.h"

using namespace std;

typedef long long ll;

ll quick_pow(ll a, ll b) {
    ll ans = 1;
    while (b) {
        if (b & 1) ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans % mod;
}

const int N = 2e5 + 10;

ll p = 3; // C(n,m) % p

ll f[N], inv[N], invF[N];

void Init() {
    f[0] = f[1] = inv[0] = inv[1] = invF[0] = invF[1] = 1;
    for(int i = 2;i <= p; i++)
    {
        f[i] = f[i - 1] * i % p;
        inv[i] = p - (p / i) * inv[p % i] % p;
        invF[i] = invF[i - 1] * inv[i] % p;
    }
}

ll C(ll m, ll n) {
    if(m < 0  n < 0  n > m)
        return 0;
    ll ans = f[m];
    ans = ans * invF[n] % p;
    ans = ans * invF[m - n] % p;
    return ans;
}

ll Lucas(ll m, ll n) {
    return n ? Lucas(m / p, n / p) * C(m % p, n % p) % p : 1;
}

void solve() {
    Init();
    int _; cin >> _;
    while(_--) {
        ll ans = 0;
        ll n, k; cin >> n >> k;
        k = min(k, 2 * n - k);
        ans = Lucas(2 * n, k);
        if((2 * n - k) & 1) ans = -ans;
        cout << (ans % 3 + 3) % 3 << endl;
    }
}

signed main() {
    solve();
}

本文作者：jujimeizuo
本文地址： https://blog.jujimeizuo.cn/2021/02/24/2021-nowcoder-hanjia-6-b/
本博客所有文章除特别声明外，均采用 CC BY-SA 3.0 协议。转载请注明出处！