9.17 第一题

题意

给出\(n,b,k\)，求
\[ \sum_{i=1}^n {i \choose k} b^i \pmod p \]
\(n\leq 10^{18},k\leq 5\times 10^5,b\leq p, p\in prime\)

解法

\(\%\%\%MAXe\)

抽象出一个杨辉三角形

把每一行赋予一个权值，其中第\(i\)行的权值是\(b^i\)

我们定义一列\(j\)的权值是这一列上所有元素（即组合数）与其行权值的乘积之和

我们发现我们最后要求的实际上就是杨辉三角的第\(k\)列的权值

我们希望求出一个列与列之间的递推式，如果能够求出来，那么我们就有一个\(O(K)\)的算法了

我们令\(f[k]\)为第\(k\)列的权值，假设我们现在已知\(f[k-1]\)，尝试递推出\(f[k]\)

我们先把第\(k-1\)列的权值乘上一个\(b\)使其与\(f[k]\)同阶，去掉最下面的一个元素（因为它无法转移到\(k\)中的组合数）再与\(f[k]\)合并解方程

这里不太好讲，画图理解一下还是很直观的，结合公式\({n \choose m}={n-1\choose m-1}+{n-1\choose m}\)

总之，我们可以列出一个这样的方程：
\[ f_k=f_{k-1}\times b-{n\choose k-1}\times b^{n+1}+ f_k \times b - {n\choose k}\times b^{n+1} \]
把方程解开，就变成了
\[ f_k=\frac{{n+1\choose k}\cdot b^{n+1}-f_{k-1} \cdot b}{b-1} \]
预处理以\(n+1\)为底的组合数就可以了

注意取模，有点恶心

代码

#include <cstdio>

using namespace std;

const int N = 500010;
const int mod = 998244353;

long long n, b, k;
long long c1, c2;

long long f[N], g[N], C[N];

long long qpow(long long x, long long y) {
    x %= mod;
    long long res = 1;
    while (y) {
        if (y & 1)  res = res * x % mod;
        x = x * x % mod, y >>= 1;   
    }
    return res;
}

void init() {
    
    g[1] = C[1] = (n + 1) % mod;
    
    long long fac = 1;
    for (long long i = 2, j = n; i <= k; ++i, --j) {
        fac = fac * i % mod;
        g[i] = g[i - 1] * (j % mod) % mod;
        C[i] = g[i] * qpow(fac, mod - 2) % mod;
    }
//  for (int i = 1; i <= k; ++i)
//      printf("%d choose %d: %d\n", n + 1, i, C[i]);
    c1 = qpow(b, n + 1), c2 = qpow(b - 1, mod - 2);
}

int main() {
    
    scanf("%lld%lld%lld", &n, &b, &k);
    
    init(); 
    
    f[0] = (1 - c1 + mod) % mod * qpow(1 - b + mod, mod - 2) % mod;
    for (int i = 1; i <= k; ++i) 
        f[i] = (C[i] * c1 % mod - f[i - 1] * b % mod + mod) % mod * c2 % mod;
    
    printf("%lld\n", f[k]);
    
    return 0;
}

9.17 第一题

原文：https://www.cnblogs.com/VeniVidiVici/p/11536930.html