首页 > 代码库 > 2014ACM/ICPC亚洲区西安站现场赛 F color(二项式反演)
2014ACM/ICPC亚洲区西安站现场赛 F color(二项式反演)
题意:小球排成一排,从m种颜色中选取k种颜色给n个球上色,要求相邻的球的颜色不同,求可行的方案数,答案模1e9+7。T组数据,1<= n, m <= 1e9, 1 <= k <= 1e6, k <= n, m
分析:
a(k)表示用不超过k种颜色染n个位置,两两相邻颜色不相同的总数,很简单a(k)=k(n-1)^(k-1)
b(k)表示恰好用k种颜色
很显然a(k)=ΣC(k,i)b(i),我们知道a,想知道b,这里就用到二项式反演
那么b(k)=ΣC(k,i)*i*(-1)^(k-i)*(n-1)^(k-1)
再利用kC(n,k)=nC(n-1,k-1)代入,就可以写成二项式展开的式子,从而用快速幂加速
然后就是枚举k,ans=ΣC(m,k)*b(k)
2014ACM/ICPC亚洲区西安站现场赛 F color(二项式反演)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。