51nod 1245 Binomial Coefficients Revenge
Description
C(M,N) = M! / N! / (M - N)! (组合数)。给出M和质数p,求C(M,0), C(M,1)......C(M,M)这M + 1个数中,有多少数不是p的倍数,有多少是p的倍数但不是p2的倍数,有多少是p2的倍数但不是p^3的倍数......。
例如:M = 10, P = 2。C(10,0) -> C(10,10)
分别为:1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1。
P的幂 = 1 2 4 8 16......
1 45 45 1 这4个数只能整除1。
10 210 210 10这4个数能整除2但不能整除4。
252 能整除4但不能整除8。
120 120 这2个数能整除8但不能整除16。
Solution
一个质数出现了 \(k\) 次,那么 \(2^{1,2....,k}\) 都出现过
判断一个质数在 \(n!\) 中出现的次数就是:
\(\sum_{i=1}^{n} \lfloor\frac{n}{p^i}\rfloor\)
那么 \(C_{n}^{m}\) 的贡献就是 \(\sum \lfloor\frac{n}{p^i}\rfloor-\lfloor\frac{m}{p^i}\rfloor-\lfloor\frac{n-m}{p^i}\rfloor\)
\(\lfloor\frac{n}{p^i}\rfloor-\lfloor\frac{m}{p^i}\rfloor-\lfloor\frac{n-m}{p^i}\rfloor\) 的值不是 \(1\) 就是 \(0\)
是 \(1\) 的条件是 \(n \mod P<m \mod P\)
那么把 \(n\) 看成 \(P\) 进制数,从高位到低位看的话,也就是统计满足 \(n\) 的某个后缀大于 \(m\) 的某个后缀的个数
从低位到高位做,设 \(f[i][j][0/1]\) 表示前 \(i\) 位,满足条件的后缀个数是 \(j\),相对于 \(n\) 是危险态还是安全态的方案数(\(m\) 要小于 \(n\))
#include<bits/stdc++.h>
using namespace std;
template<class T>void gi(T &x){
int f;char c;
for(f=1,c=getchar();c<'0'||c>'9';c=getchar())if(c=='-')f=-1;
for(x=0;c<='9'&&c>='0';c=getchar())x=x*10+(c&15);x*=f;
}
typedef long long ll;
const int N=105;
ll n,P,a[N],f[N][N][2];int m=0;
inline void work(){
m=0;
memset(f,0,sizeof(f));
cin>>n>>P;
ll x=n;
while(x)a[++m]=x%P,x/=P;
f[1][1][1]=P-1-a[1];f[1][0][0]=a[1]+1;
for(int i=1;i<m;i++){
for(int j=0;j<=i;j++){
f[i+1][j+1][1]+=f[i][j][1]*(P-a[i+1])+f[i][j][0]*(P-a[i+1]-1);
f[i+1][j][0]+=f[i][j][0]*(a[i+1]+1)+f[i][j][1]*a[i+1];
}
}
for(int i=0;i<N && f[m][i][0];i++)
printf("%lld ",f[m][i][0]);
puts("");
}
int main(){
freopen("pp.in","r",stdin);
freopen("pp.out","w",stdout);
int T;cin>>T;
while(T--)work();
return 0;
}
最新文章
- CentOS系统常用基本命令&;Centos 7 命令变化
- 小小收获for python
- SqlServer性能优化 手工性能收集动态管理视图(三)
- 《菊与刀》--[美]鲁思&#183;本尼迪克特(Ruth Benedict)
- AOJ 2170 Marked Ancestor (基础并查集)
- ccr1
- PHP扩展开发(1):入门
- SP2-0618: Cannot find the Session Identifier. Check PLUSTRACE role is enabled
- MySQL 5.7 重置root默认密码
- (Problem 5)Smallest multiple
- SQL点滴32—Excel中CONCATENATE函数生成SQL语句
- hibernate不能自动生成表的原因总结
- Unity3D换装系统
- JAVA设计模式之:命令模式
- superset在 centos 7安装运行
- 后台web端的react
- flask基本介绍及虚拟环境
- Docker:使用Jenkins构建Docker镜像
- 解决 Could not resolve com.android.tools.build:gradle:3.1.3
- HDU1081 最大字段和 压缩数组(单调队列优化)