【luoguP3746】组合数问题

这个题目……开始我yy了一个dp方程为\(dp[i] = dp[i – 1] + C_{nk}^{ik + r}\),然后矩阵一波发现emmmmmm里面有个组合数是会随着i的增长,m不断改变的。然后我就弃疗了。看完题解以后顿时觉得自己是个zz啊
组合数的递推公式\(C_{n}^{m}=C_{n-1}^{m-1}+C_{n-1}^{m}\),那么我这个式子加个\(\\sum\)也不是不行啊
于是式子变成了这样\(\sum C_{n}^{m} = \sum C_{n – 1}^{m – 1} + \sum C_{n – 1}^{m}\)
然后我就可以设置dp[i][j] = dp[i-1][j-1] + dp[i-1][j],dp[i][j]表示$n$为i的时候且m为$a*k+j$的时候的答案
这个东西显然可以矩阵快速幂优化
但是其实这个方程这么写是错的
$j$为$0$的时候$j-1$不就是$-1$了吗
那么真正的方程式为dp[i][j] = dp[i – 1][j] + dp[i – 1][(j – 1 + k) % k]

#include<algorithm>
#include<iostream>
#include<cstring>
#include<climits>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#include<queue>
#include<map>
#define ri register int

using namespace std;

typedef long long lo;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

inline void re(lo &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

lo n, p, k, r;

struct in
{
    lo a[55][55];
}a, ans;

in operator * (in x, in y)
{
    in c; memset(c.a, 0, sizeof(c.a));
    for(ri kk = 0; kk < k; kk ++)
        for(ri i = 0; i < k; i ++)
            for(ri j = 0; j < k; j ++)
                c.a[i][j] = (c.a[i][j] + x.a[i][kk] * y.a[kk][j] % p) % p;
    return c;
}

int main()
{
    re(n), re(p), re(k), re(r), n *= k;
    for(ri i = 0; i < k; i ++)
        a.a[i][i] ++, a.a[(i - 1 + k) % k][i] ++;
    for(ri i = 0; i < k; i ++)
        ans.a[i][i] = 1;
    while(n)
    {
        if(n & 1)
            ans = a * ans;
        a = a * a, n >>= 1;
    }
    printf("%lld", ans.a[0][r]);
}

发表评论

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