CF 1548C The Three Little Pigs

题目描述

https://www.luogu.com.cn/problem/CF1548C

简要题意：给定 $n$ 和 $q$，现在有 $q$ 次询问，每次询问给定 $x$ 求 $\sum_{i=1}^n\binom{3i}{x}$

$n\le 10^6,q\le 2\times 10^5,x\le 3n$

Solution

考虑生成函数知识，我们知道 $\binom{n}{i}=x^i^n$，那么关于 $x$ 的生成函数为 $F(x)=\sum_{i=1}^n(1+x)^{3i}$，简单化简我们可以得到 $\frac{(1+x)^{3n+3}-(1+x)^3}{(1+x)^3-1}$，这个东西上面可以直接用组合数计算，下面这个除法我们暴力做多项式除法即可

时间复杂度 $O(n)$

#include <iostream>
#include <vector>
#define maxn 3000010
using namespace std;

const int p = 1000000007;
inline int add(int x, int y) { return (x += y) >= p ? x - p : x; }
inline int mul(int x, int y) { return 1ll * x * y % p; }
inline int add(initializer_list<int> lst) { int s = 0; for (auto t : lst) s = add(s, t); return s; }
inline int mul(initializer_list<int> lst) { int s = 1; for (auto t : lst) s = mul(s, t); return s; }
int pow_mod(int x, int n) {
    int s = 1;
    for (; n; n >>= 1, x = mul(x, x))
        if (n & 1) s = mul(s, x);
    return s; 
}

int fac[maxn], inv[maxn];
void init_C(int n) {
    fac[0] = 1; for (int i = 1; i <= n; ++i) fac[i] = mul(fac[i - 1], i);
    inv[n] = pow_mod(fac[n], p - 2); for (int i = n - 1; ~i; --i) inv[i] = mul(inv[i + 1], i + 1); 
}
int C(int n, int m) { return n < m ? 0 : mul({ fac[n], inv[m], inv[n - m] }); }

int n, m;

#define Poly vector<int> 

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

    cin >> n >> m; init_C(3 * (n + 1));
    Poly A(3 * (n + 1) + 1), res(3 * n + 1); 
    for (int i = 0; i <= 3 * (n + 1); ++i) A[i] = C(3 * (n + 1), i);
    A[0] = add(A[0], p - 1); A[1] = add(A[1], p - 3); A[2] = add(A[2], p - 3); A[3] = add(A[3], p - 1);
    for (int i = 3 * n; ~i; --i) {
        res[i] = A[i + 3];
        A[i + 3] = add(A[i + 3], p - res[i]); 
        A[i + 2] = add(A[i + 2], p - mul(3, res[i]));
        A[i + 1] = add(A[i + 1], p - mul(3, res[i])); 
    }
    for (int i = 1; i <= m; ++i) {
        int x; cin >> x;
        cout << res[x] << "\n";
    }
    return 0; 
}