【题解】[六省联考 2017] 组合数问题

题意

给定 $n,k,p,r$。

求

$$\sum_{i=0}^{+∞}\binom{nk}{r+ki} \bmod p$$

范围：$1 \le n \le 10^9$，$0 \le r < k \le 50$，$2 \le p < 2^{30}$。

题解

写出组合数的递推式：

$$\binom{n}{m}=\binom{n-1}{m}+\binom{n-1}{m-1}$$

令 $f_{i,j}=\binom{n}{m}$，那么有 $f_{i,j}=f_{i-1,j}+f_{i-1,j-1}$。

直接求时间空间都炸，考虑优化递推式。

由于我们要求出所有 $a \equiv r \pmod k$ 的 $\binom{nk}{a}$ 之和，所以第二维只需在意对 $k$ 取模的值。

把第二维压缩，重新定义 $f_{i,j}$ 为满足 $a \equiv r \pmod k$ 的 $\binom{i}{a}$ 之和。

那么有 $f_{0,0}=1$，$f_{i,j}=f_{i-1,j}+f_{i-1,(j-1) \bmod k}$ 。

此时式子出现了 $\bmod k$，发现存在 $k=1$ 的情况，此时 $f_{i,0}$ 在推导下等于 $1$，显然不对，所以要特判算一下，算得结果为 $\sum\limits_{i=0}^n \binom{n}{i}=2^n$。

对于 $k \neq 1$ 的情况，发现 $f$ 中第一维 $i$ 只与第 $i-1$ 的状态有关，所以上矩阵快速幂（向量乘矩阵）即可。

初始状态构造方式：向量 $A$ 的第 $0$ 项为 $1$，矩阵 $E$ 中 $\forall i$，$\ E_{i,i},E_{(i-1) \bmod k,i}$ 设为 $1$。

这么做时间复杂度 $\mathcal{O}(k^3 \log nk)$。当然有更快的 $\mathcal{O}(k^2 (\log n+\log k))$ 卷积做法，这里先不说了。

代码

#include <bits/stdc++.h>
#define eps 1e-6
typedef long long ll;
using namespace std;
const int INF = 1e9;

struct Matrix{
    int m[55][55], h, w;
}A, E;
int n, p, k, r;
ll nn;

int qpow(int a, int b){
    int t = 1;
    while(b){
        if(b & 1) t = 1ll * t * a % p;
        a = 1ll * a * a % p;
        b >>= 1;
    }
    return t;
}

Matrix operator * (Matrix x, Matrix y){
    Matrix z;
    memset(z.m, 0, sizeof(z.m));
    z.h = x.h, z.w = y.w;
    for(int k = 0; k < x.w; k++)
        for(int i = 0; i < x.h; i++)
            for(int j = 0; j < y.w; j++)
                z.m[i][j] = (z.m[i][j] + 1ll * x.m[i][k] * y.m[k][j] % p) % p;
    return z;
}

int main(){

    scanf("%d%d%d%d", &n, &p, &k, &r), nn = 1ll * n * k;
    if(k == 1){
        printf("%d\n", qpow(2, n));
        return 0;
    }
    A.h = 1, A.w = E.h = E.w = k, A.m[0][0] = 1;
    for(int i = 0; i < k; i++) E.m[i][i] = 1;
    for(int i = 0; i < k; i++) E.m[(i - 1 + k) % k][i] = 1;
    while(nn){
        if(nn & 1) A = A * E;
        E = E * E;
        nn >>= 1;
    }
    printf("%d\n", A.m[0][r]);
    
    return 0;
}