题目描述

输入

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

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

输出

一行一个整数代表答案。

样例输入

2 10007 2 0

样例输出

8

---

题目大意

问从nk个数中选出若干个，且选出数的数目mod k=r的方案数

题解

dp+快速幂/矩阵乘法

题目描述是骗人的，一个一个加根本不可能加的过来。

关于矩阵乘法的题解可以参考 ，时间复杂度为O(k^3logn)，

我的做法是dp+快速幂。

（UPD：后来知道这其实就是循环矩阵乘法）

设 $f[i][j]$ 表示从 $i$ 个数中选出若干个，且选出的数的数目 $\text{mod} k=j$ 的方案数

那么有 $f[i1+i2][j]=\sum((j1+j2)mod k = j)f[i1][j1]∗f[i2][j2]$ 

这里可能比较难用数学语言表述，但事实上其中的求和符号仅是对于 $j1$ 和 $j2$ ，并不对于 $i1$ 和 $i2$ ，也就是说只要找到任意一组 $i1$ 和 $i2$ ，就可以用 $f[i1]$ 和 $f[i2]$ 推出。

发现这一点类似于乘方，于是我们可以使用快速幂的方法来快速推出f[nk]数组，时间复杂度为O(k^2logn).

注意一下这里k可能等于1，所以初始化时不能简单地将f[0][1]赋为1，而是将f[0][1%k]加上1。

#include 
     
      #include 
      
       typedef long long ll;int p , k;struct data{	ll f[60];	data()	{		memset(f , 0 , sizeof(f));	}	data operator*(const data a)const	{		int i , j;		data tmp;		for(i = 0 ; i < k ; i ++ )			for(j = 0 ; j < k ; j ++ )				tmp.f[(i + j) % k] = (tmp.f[(i + j) % k] + f[i] * a.f[j]) % p;		return tmp;	}}ans;data pow(data x , ll y){	data ans;	ans.f[0] = 1;	while(y)	{		if(y & 1) ans = ans * x;		x = x * x , y >>= 1;	}	return ans;}int main(){	int n , r;	scanf("%d%d%d%d" , &n , &p , &k , &r);	ans.f[0] ++ , ans.f[1 % k] ++ ;	printf("%lld\n" , pow(ans , (ll)n * k).f[r]);	return 0;}