「校园内仿真模拟」模拟为了部落

  • 内容
  • 相关

下载.jpg
Description
T次了解,每一次了解得出n,m,k,P,问n个点的全部有型号转化成山林中,连接块数为m的计划方案中,从每株树中挑选一个近视度数<=k的点的计划方案数对P取模的计划方案数
n<=10^9,m,k<=100
Solution
人们先选关键环节,再数生成树
显而易见随意m个点的计划方案数是相同的,人们只必须特定m个关键环节,参考答案乘以(nm)\binom{n}{m}(mn​)
考虑到枚举这m个点的近视度数,设总近视度数为D,剩余的一部分为,n-m个点,D棵有型号有根树的转化成山林数量
考虑到怎样做n个点m棵有型号有根树,由于是有根树,在建一个点n+1向全部根连边,这一等额的于n+1个点,点n+1的近视度数为m的树的数量
用prufer序记数,等于挑选m-1个部位填n+1,剩余的部位填1~n,计划方案数为(n−1m−1)nn−m\binom{n-1}{m-1}n^{n-m}(m−1n−1​)nn−m
接下去难题等于,将n个物件分成m组,一组总数<=k
设F[n][m]表达参考答案,考虑到第n个物件在哪儿一组,假如添加后不合理合法等于这一组原本就会有k个,枚举是哪k个剩下的等于是F[n-1-k][m-1]
因此人们有F[n][m]=F[n−1][m]∗m−F[n−1−k][m−1]∗(n−1k)∗mF[n][m]=F[n-1][m]*m-F[n-1-k][m-1]*\binom{n-1}{k}*mF[n][m]=F[n−1][m]∗m−F[n−1−k][m−1]∗(kn−1​)∗m
最终将两一部分合拼,有一个(n−1m−1)\binom{n-1}{m-1}(m−1n−1​)因为P不一定为质数因此立即爆力分解质因数
一次了解复杂性为O(m2k+mk2+mklog⁡2P)O(m^2k+mk^2+mk\log^2P)O(m2k+mk2+mklog2P)
Code
#include
#include
#include
#definefo(i,a,b)for(inti=a;i<=b;i++)
#definefd(i,a,b)for(inti=a;i>=b;i--)
usingnamespacestd;
typedeflonglongll;
constintN=1e4+5;
intty,n,m,k,Mo,lim,cnt[N],p[N];
llf[105][N],C[N][105];
llpwr(llx,inty){
llz=1;
for(;y;y>>=1,x=x*x%Mo)
if(y&1)z=z*x%Mo;
returnz;
}
llcalc(){
llret=1;
fo(i,1,p[0])ret=ret*pwr(p[i],cnt[i])%Mo;
returnret;
}
llins(intx,intf){
if(!x)return1;
fo(i,1,p[0])while(!(x%p[i]))x

本文标签:

版权声明:若无特殊注明,本文皆为《Black Leaguer》原创,转载请保留文章出处。『鹦鹉搜索』

百度收录:百度已收录『查看详情』

本文链接:「校园内仿真模拟」模拟为了部落 - https://www.15qq.cn/spe_seo/1090.html

发表评论

电子邮件地址不会被公开。 必填项已用*标注

允许邮件通知