BZOJ4870 组合数问题

题解

首先推导一下这个式子的组合意义
然后发现其实就是要求在 $nk$ 件物品中取出的物品件数 $\% k$ 为 $r$ 的方案数
设在 $n$ 件物品中取物品件数 $\% k$ 为 $i$ 的方案数为 $f[n][i]$ ,那么 $f[n+1][i] = f[n][i]+f[n][(i – 1 + k) mod k] $
发现转移方程与第一位无关,于是可以快乐矩乘
复杂度 $O(k^3\log{nk})$

代码

struct matrix {
    ll a[MAX_K][MAX_K];

    inline void init () {
        memset(a, 0, sizeof(a));
        for (int i = 0; i < K; ++i)
            a[i][i] = 1;
    }
};

matrix operator % (matrix x, ll mod) {
    for (int i = 0; i < K; ++i) {
        for (int j = 0; j < K; ++j) {
            x.a[i][j] %= mod;
        }
    }
    return x;
}

matrix operator * (matrix x, matrix y) {
    matrix z;
    memset(z.a, 0, sizeof(z.a));
    for (int i = 0; i < K; ++i) {
        for (int j = 0; j < K; ++j) {
            for (int k = 0; k < K; ++k) {
                (z.a[i][j] += x.a[i][k] * y.a[k][j] % MOD) %= MOD;
            }
        }
    }
    return z;
}

inline matrix quick_pow2 (matrix x, ll p) {
    matrix ans;
    ans.init();
    while (p) {
        if (p & 1) ans = (ans = ans * x % MOD);
        x = (x * x % MOD);
        p >>= 1;
    }
    return ans;
}

inline ll quick_pow (ll x, ll p) {
    ll ans = 1;
    while (p) {
        if (p & 1) (ans *= x) %= MOD;
        (x *= x) %= MOD;
        p >>= 1;
    }
    return ans;
}

int main () {
    read(N), read(MOD), read(K), read(R);
    if (K == 1) {
        printf("%lld\n", quick_pow(2LL, N));
        return 0;
    }
    matrix A;
    memset(A.a, 0, sizeof(A.a));
    for (int i = 0; i < K; ++i)
        A.a[i][i] = 1LL, A.a[i][(i - 1 + K) % K] = 1LL;
    A = quick_pow2(A, N * (ll)K);
    printf("%lld\n", (A.a[R][0]) % MOD);
    return 0;
}

本题完
发现对于任意 $x,y$ ,都有
$$ f[x+y][j]=f[x][0]\cdot f[y][j]+f[x][1]\cdot f[y][j-1]+…+f[x][j]\cdot f[y][0]$$
也发现
$$ f[2i][j]=f[i][0]\cdot f[i][j]+f[i][1]\cdot f[i][j-1]+ … +f[i][j]\cdot f[i][0] $$
上面这个式子是一个倍增,于是可以处理出 ${ f[2^i][j]|0\leq i\leq \log{nk}}$
然后将 $nk$ 拆成二进制位用之前的方法处理出总方案就解决了
复杂度 $O(k^2\log{nk})$ 就算 $k$ 出到 $500$ 也可以轻松地解决
代码


int K, R; ll N; ll MOD, f[80][MAX_K], g[2][MAX_K]; int main () { read(N), read(MOD), read(K), read(R); f[0][0] = f[0][1] = 1; if (K == 1) f[0][0]++; for (int i = 1; i < 80; ++i) { for (int j = 0; j < K; ++j) { for (int k = 0; k < K; ++k) { (f[i][j] += f[i - 1][k] * f[i - 1][(j - k + K) % K] % MOD) %= MOD; } } } g[0][0] = 1; int cnt = 0; N *= (ll)K; while (N) { if (N & 1) { for (int i = 0; i < K; ++i) { for (int j = 0; j < K; ++j) { (g[1][i] += g[0][j] * f[cnt][(i - j + K) % K] % MOD) %= MOD; } } memcpy(g[0], g[1], sizeof(g[0])); memset(g[1], 0, sizeof(g[1])); } cnt++; N >>= 1; } printf("%lld\n", g[0][R]); return 0; }

比较上面两个方法的效率
4870status.png

本题完
对于上面的递推式
$$ f[2i][j]=f[i][0]\cdot f[i][j]+f[i][1]\cdot f[i][j-1]+…+f[i][j]\cdot f[i][0] $$
进行观察发现 $f[2i]$ 是由 $f[i]$ 卷积得来,由于模数任意,可以使用 $MTT$ 解决,若固定模数,可以用 $NTT$ 解决,相对简单一些
复杂度 $O(k\log k \log{nk})$
其实我也不知道这个方法对不对

sys_con

高一 OIer,常规 / 竞赛都渣得不行

发表评论

电子邮件地址不会被公开。 必填项已用*标注