组合数问题

Time Limit: 10 Sec Memory Limit: 512 MB

Description

img

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include<bits/stdc++.h>
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<num;i++)
            for(int j=0;j<num;j++)
            {
                record.v[i][j]=0;
                for(int k=0;k<num;k++)
                    record.v[i][j] = (s64)(record.v[i][j] + a.v[i][k]*b.v[k][j] % MOD) % MOD;
            }
        return record;
    }
};
Matrix B,Ans;

Matrix Quickpow(Matrix a,s64 b)
{
    Matrix res;
    for(int i=0;i<num;i++) res.v[i][i] = 1;
    while(b)
    {
        if(b&1) res = res*a;
        a = a*a;
        b>>=1;
    }
    return res;
}

int main()
{
    n=get();    MOD=get();    num=get();    r=get();
    for(int i=0;i<num;i++)
    {
        B.v[i][i]++;
        B.v[((i-1)%num+num)%num][i]++;
    }

    Ans = Quickpow(B, (s64)n*num);

    cout<<Ans.v[0][r];

}