题目大意

C(M,N) = M! / N! / (M - N)! (组合数)。给出M和质数p,求C(M,0), C(M,1)......C(M,M)这M + 1个数中,有多少数不是p的倍数,有多少是p的倍数但不是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。

所以输出:4 4 1 2。

分析

根据kummer定理,\(C_{n+m}^{n}\)的含的质数p的幂次等于在p进制下n+m的进位次数。

于是数位dp,设\(f[i][j][0/1]\)表示,做到第i位,进了j次位,当前位是否进位的方案数。

#include <cmath>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <bitset>
#include <set>
#include <vector>
const int inf=2147483647;
const int mo=1e9+7;
const int N=75;
using namespace std;
int T;
long long n,p,f[N][N][2],m,a[N];
int main()
{
for(scanf("%d",&T);T--;)
{
scanf("%lld%lld",&n,&p);
memset(f,0,sizeof(f));
a[0]=0;
for(long long x=n;x;x/=p) a[++a[0]]=x%p;
f[1][0][0]=a[1]+1,f[1][1][1]=p-a[1]-1;
for(int i=1;i<a[0];i++)
for(int j=0;j<=i;j++)
{
f[i+1][j][0]+=(a[i+1]+1)*f[i][j][0]+a[i+1]*f[i][j][1];
f[i+1][j+1][1]+=(p-a[i+1]-1)*f[i][j][0]+(p-a[i+1])*f[i][j][1];
}
for(int i=a[0];i>=0;i--)
if(f[a[0]][i][0])
{
for(int j=0;j<=i;j++) printf("%lld ",f[a[0]][j][0]);
break;
}
putchar('\n');
}
}
05-26 11:35