[JZOJ6244]【NOI2019模拟2019.7.1】islands【计数】【图论】

冷不防 2021-12-11 11:37 158阅读 0赞

## Description![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h6ajEwNTQ2ODk2OTk_size_16_color_FFFFFF_t_70] ##

n<=1e9,M,K<=100

## Solution ##

显然任选m个港口的答案是一样的，乘个组合数即可。  
考虑枚举m个港口的度数之和D  
可以DP计算  
记\\(F\_\{m,D\}\\)为将D的度数分给m个港口的方案数  
枚举新的一个度数分配给谁，然后此时可能某一个超出了限制，减掉这一个的贡献。

接下来我们可以用一个超级根把D个点连起来  
prufer序简单计数即可  
\\(n-m+1\\)个点，其中超级根出现了\\(D-1\\)次  
就是\\(\{n-m-1\\choose D-1\}(n-m)^\{n-m-D\}\\)  
总的答案为\\\[\{n\\choose m\}\\sum\\limits\_\{i=0\}^\{mK\}F\_\{m,i\}\{n-m-1\\choose D-1\}(n-m)^\{n-m-D\}\\\]  
组合数取模的时候，我们先对模数分解质因子，每次组合数相当于乘一个数除一个数  
暴力枚举质因子，剩下的部分就有逆元了

注意n=m的时候会有问题需要特判。

## Code ##

#include <bits/stdc++.h> #define fo(i,a,b) for(int i=a;i<=b;++i) #define fod(i,a,b) for(int i=a;i>=b;--i) const int N=105; typedef long long LL; using namespace std; int t,n,m,num,l,mo,f[N][N*N],cs[N*N][N],pr[N][2]; LL ksm(LL k,LL n) { LL s=1; for(;n;n>>=1,k=k*k%mo) if(n&1) s=s*k%mo; return s; } void exgcd(LL a,LL b,LL &x,LL &y) { if(b==0) {x=1,y=0;return;} exgcd(b,a%b,y,x); y-=(a/b)*x; } LL ny(int k) { LL x,y; exgcd(k,mo,x,y); return (x%mo+mo)%mo; } void make(int n) { num=0; int n1=sqrt(n); fo(i,2,n1) { if(n%i==0) { pr[++num][0]=i; while(n%i==0) pr[num][1]++,n/=i; } } if(n>1) pr[++num][0]=n,pr[num][1]=1; } int pv[N]; void mul(LL &s,LL v) { if(v!=0) fo(i,1,num) while(v%pr[i][0]==0) v/=pr[i][0],pv[i]++; s=s*v%mo; } void dvi(LL &s,LL v) { fo(i,1,num) while(v%pr[i][0]==0) v/=pr[i][0],pv[i]--; s=s*ny(v)%mo; } LL get(LL s) { fo(i,1,num) s=s*ksm(pr[i][0],pv[i])%mo; return s; } int main() { cin>>t; while(t--) { scanf("%d%d%d%d",&n,&m,&l,&mo); if(n==m) {printf("%d\n",1%mo);continue;} cs[0][0]=1%mo; make(mo); fo(i,1,m*l) { cs[i][0]=1%mo; int r=min(i,l); fo(j,1,r) cs[i][j]=((LL)cs[i-1][j]+cs[i-1][j-1])%mo; } f[0][0]=1; fo(i,1,m) { int r=min(i*l,n-m); f[i][0]=1; fo(j,1,r) { f[i][j]=(LL)f[i][j-1]*i%mo; if(j>l) f[i][j]=(f[i][j]-(LL)cs[j-1][l]*f[i-1][j-1-l]%mo*i%mo+mo)%mo; } } memset(pv,0,sizeof(pv)); LL v=1,ans=0;int r=min(n-m,l*m); fo(i,1,r) { ans=(ans+ksm(n-m,n-i-m)*f[m][i]%mo*get(v)%mo)%mo; mul(v,n-m-i),dvi(v,i); } v=1;memset(pv,0,sizeof(pv)); fo(j,0,m-1) mul(v,n-j),dvi(v,j+1); ans=ans*get(v)%mo; printf("%lld\n",ans); } }

转载于:https://www.cnblogs.com/BAJimH/p/11117152.html

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h6ajEwNTQ2ODk2OTk_size_16_color_FFFFFF_t_70]: /images/20211211/a2030aac0bd84b378addaaaf23745f44.png