[BZOJ4870][六省联考2017]组合数问题(组合数动规)

4870: [Shoi2017]组合数问题

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

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

8

HINT

Source

黑吉辽沪冀晋六省联考

[Submit][Status][Discuss]

题目实际上是要求所有kn以内的所有模k余r的数的组合数之和。对于这种余数固定的题目常常可以根据余数DP，而根据r,k范围都很小而只有n很大可以初步猜测需要用到矩阵快速幂。

那么我们设$f[i][j]=\sum\limits_{l=0}^{+\infty}C_{i}^{lk+j}$，那么可以得出f[i+j][(x+y)%k]+=f[i][x]*f[j][y]。

这样我们把f[i]看成一个行向量，就可以矩阵乘法了。复杂度$O(k^3 \log n)$

实际上还可以优化，发现f[i]之间的转移有一个非常重要的性质：转移符合交换律！这意味着我们可以直接像快速幂一样进行DP转移。复杂度$O(k^2 \log n)$

#include<cstdio>

#include<cstring>

#include<algorithm>

#define rep(i,l,r) for (int i=l; i<=r; i++)

typedef long long ll;

using namespace std;

const int N=100;

ll ans[N],c[N],a[N],n,p,k,r,t;

void dp(ll a[],ll b[]){

	for (int i=0; i<k; i++) c[i]=0;

	for (int i=0; i<k; i++) for (int j=0; j<k; j++)

		c[(i+j)%k]=(c[(i+j)%k]+a[i]*b[j]%p)%p;

	for (int i=0; i<k; i++) a[i]=c[i];

}

int main(){

	freopen("bzoj4870.in","r",stdin);

	freopen("bzoj4870.out","w",stdout);

	scanf("%lld%lld%lld%lld",&n,&p,&k,&r);

	ans[0]++; ans[1%k]++; a[0]++; a[1%k]++; t=n*k-1;

	while (t>0){

		if (t & 1) dp(ans,a);

		dp(a,a); t>>=1;

	}

	printf("%lld\n",ans[r]);

	return 0;

}

巴特西

[BZOJ4870][六省联考2017]组合数问题(组合数动规)

4870: [Shoi2017]组合数问题

Description

Input

Output

Sample Input

Sample Output

HINT

Source

最新文章

热门文章