组合数问题

Time Limit: 10 Sec  Memory Limit: 512 MB

[][][]

Description

　　

Input

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

Output

　　一行一个整数代表答案。

Sample Input

　　2 10007 2 0

Sample Output

　　8

HINT

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

Solution

　　首先，不难发现，题目的本质是：从n*k个中选模k等于r个的方案数，那么轻易地写出了暴力DP：f[i][j]=f[i-1][j]+f[i-1][(j-1+k)%k]。

　　然后套个矩阵乘法优化一下即可。

Code

#include
      
         #include
       
          #include
        
           #include
         
            #include
          
             #include
           
             #include
            
             using namespace std;typedef long long s64;const int ONE = 55;int n,MOD,num,r;inline s64 get(){ s64 res=1,Q=1; char c; while( (c=getchar())<48 || c>57) if(c=='-')Q=-1; if(Q) res=c-48; while((c=getchar())>=48 && c<=57) res=res*10+c-48; return res*Q; }struct Matrix{ s64 v[ONE][ONE]; friend Matrix operator *(Matrix a,Matrix b) { Matrix record; for(int i=0;i
             
              >=1; } return res;}int main(){ n=get(); MOD=get(); num=get(); r=get(); for(int i=0;i