题解：P5481 [BJOI2015] 糖果

· · 题解

数数好题

SOLUTION

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

对于一个序列，如果要单调不减，就是差分非负。于是我们可以直接考虑这个东西的组合意义：设我们现在有 k 件物品，有 m 个隔板，把它分成 m+1 份，两个隔板可以在同一个缝里。

下面来解释一下，我们考虑要得到一个 m 的不降序列，而且每个数不超过 k ，每个数不超过 k，对于上述每一种方案，都可以取前 m 个份作为其差分即可。因此一行的方案为 \binom{m+k-1}{m} 。

然后因为有 n 行，求个下降幂就好。

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

CODE

#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;
}