【BZOJ4870】组合数问题 [矩阵乘法][DP]

组合数问题

Time Limit: 10 Sec Memory Limit: 512 MB
[Submit][Status][Discuss]

Description

Input

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

Output

　　一行一个整数代表答案。

Sample Input

　　2 10007 2 0

Sample Output

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<iostream>

#include<string>

#include<algorithm>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<cmath>

using namespace std;

typedef long long s64;

const int ONE = ;

int n,MOD,num,r;

inline s64 get()

{

        s64 res=,Q=;  char c;

        while( (c=getchar())< || c>)

        if(c=='-')Q=-;

        if(Q) res=c-;

        while((c=getchar())>= && c<=)

        res=res*+c-;

        return res*Q;

}

struct Matrix

{

        s64 v[ONE][ONE];

        friend Matrix operator *(Matrix a,Matrix b)

        {

            Matrix record;

            for(int i=;i<num;i++)

            for(int j=;j<num;j++)

            {

                record.v[i][j]=;

                for(int k=;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=;i<num;i++) res.v[i][i] = ;

        while(b)

        {

            if(b&) res = res*a;

            a = a*a;

            b>>=;

        }

        return res;

}

int main()

{

        n=get();    MOD=get();    num=get();    r=get();

        for(int i=;i<num;i++)

        {

            B.v[i][i]++;

            B.v[((i-)%num+num)%num][i]++;

        }

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

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

}

巴特西