数数好题

SOLUTION

首先，显然行与行之间没有任何关系，所以单独考虑行即可。

对于一个序列，如果要单调不减，就是差分非负。于是我们可以直接考虑这个东西的组合意义：设我们现在有

k

件物品，有

m

个隔板，把它分成

m+1

份，两个隔板可以在同一个缝里。

下面来解释一下，我们考虑要得到一个

m

的不降序列，而且每个数不超过

k

，每个数不超过

k

，对于上述每一种方案，都可以取前

m

个份作为其差分即可。因此一行的方案为

\binom{m+k-1}{m}

。

然后因为有

n

行，求个下降幂就好。

好，这个问题的关键在于模数不一定是质数，我们可以这样处理组合数：把这个模数质因数分解，在处理组合数的时候，把每个数和模数不互质的部分用一个桶把指数存下来，互质的部分可以直接乘或除（及用

exgcd

求逆元）。

CODE

CPP

#include<bits/stdc++.h>
using namespace std;
int p[20];
int cnt[20];
int exgcd(int l,int r,int &x,int &y){
	if(r==0){x=1;y=0;return l;}
	else{
		int d=exgcd(r,l%r,y,x);
		y-=l/r*x;
		return d; 
	} 
}inline int inv(int a,int m){
	int x,y;
	if(exgcd(a,m,x,y)==1)return (x%m+m)%m;
	return -1;
}
int main(){
	int n,m,k,mod;
	scanf("%d%d%d%d",&n,&m,&k,&mod);
	int t=mod; 
	for(int i=2; i*1ll*i<=t; i++){
		if(t%i==0){
			p[++p[0]]=i;
			while(t%i==0)t/=i; 
		}
	}if(t!=1)p[++p[0]]=t;
	long long ans=1;
	for(int i=m+k-1; i>=k; i--){
		int t=i;
		for(int j=1; j<=p[0]; j++)while(t%p[j]==0)t/=p[j],cnt[j]++;
		ans=ans*t%mod;
	}for(int i=m; i>=1; i--){
		int t=i;
		for(int j=1; j<=p[0]; j++)while(t%p[j]==0)t/=p[j],cnt[j]--;
		ans=ans*inv(t,mod)%mod;
	}
	for(int i=1; i<=p[0]; i++)while(cnt[i]--)ans=ans*p[i]%mod;
	int tmp=ans;ans=1;
	for(int i=tmp; i>=tmp-n+1; i--){
		ans=ans*i%mod;
	}ans=(ans+mod)%mod;
	cout<<ans;
	return 0;
}

题解：P5481 [BJOI2015] 糖果

文章操作

SOLUTION

CODE

相关推荐

评论

题解：P5481 [BJOI2015] 糖果