[BZOJ4870][Shoi2017]组合数问题 dp+矩阵乘

4870: [Shoi2017]组合数问题

Time Limit: 10 Sec Memory Limit: 512 MB

Description

Input

第一行有四个整数 n, p, k, r，所有整数含义见问题描述。

1 ≤ n ≤ 10^9, 0 ≤ r < k ≤ 50, 2 ≤ p ≤ 2^30 − 1

Output

一行一个整数代表答案。

Sample Input

2 10007 2 0

Sample Output

题解：

今年的省选题……

题目的要求很简单，就是求满足要求的组合数在膜（？）意义下的和，但这其实是一道假的数学题。

不难发现，对于符合要求的C(n*k)^x中的x都有x%k==r

我们考虑组合数最原始的应用：在一堆物品里选一些物品出来，那么题目的含义就是在n*k个物品中选x个物品，使x%k=r，求方案数

这不就是个背包吗？

那么我们设dp数组f[i][j]为前i个物品选出一些物品，使得物品的个数x%k==j

那么不难写出转移方程：f[i][j]=f[i-1][j]+f[i-1][(j-1+k)%k]（前者表示不选第i个，后者表示选）

这显然是一个线性的递推式，因此我们考虑矩阵乘优化

设矩阵A中A[i][j]表示从%k=i转移到%k=j的方案数

那么我们的目标就是pow(A，n)之后的A[0][r];

初始化的时候，把所有的A[j][j]++,所有A[(j-1+k)%k][j]++（类比上面的转移方程）

然后再来一个单位矩阵一乘就好了。代码见下：

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <cmath>
 5 using namespace std;
 6 typedef long long LL;
 7 const int N=60;
 8 LL n,p,k,r;
 9 struct marx
10 {
11     LL m[N][N];
12     inline void print()
13     {
14         for(int i=0;i<k;i++)
15         {
16             for(int j=0;j<k;j++)
17                 printf("%lld ",m[i][j]);
18             printf("
");
19         }
20         printf("
");
21     }
22     inline void clear(){memset(m,0,sizeof(m));}
23     marx operator * (const marx &b) const
24     {
25         marx c;c.clear();
26         for(int i=0;i<k;i++)
27             for(int j=0;j<k;j++)
28                 for(int u=0;u<k;u++)
29                     c.m[i][j]=(c.m[i][j]+m[i][u]*b.m[u][j])%p;
30         return c;
31     }
32 }A,B,C;
33 int main()
34 {
35     scanf("%lld%lld%lld%lld",&n,&p,&k,&r);
36     A.clear(),B.clear(),C.clear();
37     C.m[0][0]=1;
38     for(int j=0;j<k;j++)
39         B.m[j][j]=1,A.m[(j-1+k)%k][j]++,A.m[j][j]++;
40     LL tmp=n*k;
41     while(tmp)
42     {
43         if(tmp&1)B=B*A;
44         tmp>>=1;A=A*A;
45     }
46     C=C*B;
47     printf("%lld
",C.m[0][r]);
48 }