NC9986B系数_牛客博客

Solution

比赛的时候手推，发现规律，然后打了个表。
看到了如下的规律:

 0 : 1
 1 : 1 1 1
 2 : 1 2 0 2 1
 3 : 1 0 0 1 0 0 1
 4 : 1 1 1 1 1 1 1 1 1
 5 : 1 2 0 0 0 0 0 0 0 2 1
 6 : 1 0 0 2 0 0 0 0 0 2 0 0 1
 7 : 1 1 1 2 2 2 0 0 0 2 2 2 1 1 1
 8 : 1 2 0 1 2 0 1 2 0 2 1 0 2 1 0 2 1
 9 : 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1
10 : 1 1 1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 1 1
11 : 1 2 0 2 1 0 0 0 0 1 2 0 2 1 0 0 0 0 1 2 0 2 1
12 : 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1
13 : 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
14 : 1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 1
15 : 1 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 1
16 : 1 1 1 2 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 2 2 1 1 1
17 : 1 2 0 1 2 0 1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 1 0 2 1 0 2 1
18 : 1 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 1
19 : 1 1 1 0 0 0 0 0 0 2 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 2 2 0 0 0 0 0 0 1 1 1
20 : 1 2 0 2 1 0 0 0 0 2 1 0 1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 2 1 0 1 2 0 0 0 0 1 2 0 2 1
21 : 1 0 0 1 0 0 1 0 0 2 0 0 2 0 0 2 0 0 0 0 0 0 0 0 0 0 0 2 0 0 2 0 0 2 0 0 1 0 0 1 0 0 1
22 : 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 0 0 0 0 0 0 0 0 0 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1
23 : 1 2 0 0 0 0 0 0 0 1 2 0 0 0 0 0 0 0 1 2 0 0 0 0 0 0 0 2 1 0 0 0 0 0 0 0 2 1 0 0 0 0 0 0 0 2 1
24 : 1 0 0 2 0 0 0 0 0 1 0 0 2 0 0 0 0 0 1 0 0 2 0 0 0 0 0 2 0 0 1 0 0 0 0 0 2 0 0 1 0 0 0 0 0 2 0 0 1
25 : 1 1 1 2 2 2 0 0 0 1 1 1 2 2 2 0 0 0 1 1 1 2 2 2 0 0 0 2 2 2 1 1 1 0 0 0 2 2 2 1 1 1 0 0 0 2 2 2 1 1 1
26 : 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 2 1 0 2 1 0 2 1 0 2 1 0 2 1 0 2 1 0 2 1 0 2 1 0 2 1
27 : 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
28 : 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1
29 : 1 2 0 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 0 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 0 2 1
30 : 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1

然后我太菜了，就到此为止了。

看了下题解的做法一，发现很巧妙，因为我们求的是对 $3$ 取模后的答案，所以我们将题目里的多项式配上一个 $-3x$ 对答案不造成影响！

$(x ^ 2 + x + 1) ^ n -> (x ^ 2 - 2 * x + 1) ^ n = (x - 1) ^ {2 * n}$
由二项式定理可知：
对于 $(x + y) ^ n$ 展开式中含有 $x ^ k$ 项的为 $C_{n} ^ {k} x ^ k y ^ {n - k}$ ,系数为 $C_{n} ^ {k} y ^ {n - k}$ 。

代入得 $ans = C_{2 * n}^{k} (-1) ^ {2 * n - k} (mod~3)$ ，对于 $(-1) ^ {2 * n - k}$ 和 $2 * n - k$ 的奇偶性有关，

$2 * n - k$ 是奇数 $ans = - C_{2 * n}^{k}(mod~3)$
$2 * n - k$ 是偶数 $ans = C_{2 * n}^{k}(mod~3)$

Code_bruceforce

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

constexpr ll N = 1e6 + 5;

int f[100][N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    f[0][0] = 1;
    cout << setw(2) << 0 << " : " << 1 << "\n";
    for (int i = 1; i <= 30; i++) {
        cout << setw(2) << i << " : ";
        for (int j = 0; j <= 2 * i; j++) {
            if (j - 2 >= 0) f[i][j] += f[i - 1][j - 2];
            if (j - 1 >= 0) f[i][j] += f[i - 1][j - 1];
            f[i][j] += f[i - 1][j];
            f[i][j] %= 3;
            cout << f[i][j] << " \n"[j == 2 * i];
        }
    }

    return 0;
}

Code

#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define lowbit(x) ((x) & -(x))

using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;

constexpr double eps = 1e-8;
constexpr int NINF = 0xc0c0c0c0;
constexpr int INF = 0x3f3f3f3f;
constexpr ll mod = 3;
constexpr ll N = 1e6 + 5;

/*
    (x ^ 2 + x + 1) ^ n
    = (x ^ 2 - 2 * x + 1) ^ n
    = (x - 1) ^ (2 * n)

    ans = C(2 * n, k) x ^ k * (-1) ^ (2 * n - k) % 3
*/

ll p = 3;

inline ll qpow(ll a, ll b) {
    ll base = a % p;
    ll ans = 1;
    while (b > 0) {
        if (b & 1) ans = (ans * base) % p;
        base = base * base % p;
        b >>= 1;
    }
    return ans;
}

inline ll C(ll n, ll m) {
    if (n < m) return 0;//组合数n<m特判
    if (m > n - m) m = n - m;//组合数性质
    ll a = 1, b = 1;
    for (int i = 0; i < m; i++) {
        a = (a * (n - i) % p);//组合数分子 a 
        b = (b * (i + 1)) % p;//组合数分母 b
    }
    return a * qpow(b, p - 2) % p;//费马小定理 a/b=a*b^(p-2) 
}

inline ll Lucas(ll n, ll m) {
    if (m == 0) return 1;
    return Lucas(n / p, m / p) * C(n % p, m % p) % p;
}

void solve() {
    ll n, k;
    cin >> n >> k;
    n = 2 * n;
    cout << (Lucas(n, k) * ((n - k) & 1 ? -1 : 1) % mod + mod) % mod << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        solve();
    }

    return 0;
}