题目描述
传送门
题目大意：设 sum(i) 表示 i 的二进制表示中 1 的个数。给出一个正整数 N ，求 sum(1)—sum(N) 的乘积。
题解
数位DP 将读进来的数进行二进制分解，然后从高位到低位开始DP。
f[i][j][0/1]
表到第i位一共填了j个1是否卡上界的方案数。 最后的答案就是
∏if[n][i][0]+f[n][i][1]
代码
using namespace std;
LL f[N][N][
2],
x,g[N];
LL ans[N],n;
LL quickpow(LL num,LL
x)
{
LL base=num
%p; LL ans=
1;
while (
x) {
if (
x&
1) ans=ans
*base%p;
x>>=
1;
base=base
*base%p;
}
return ans;
}
int main()
{
freopen(
"a.in",
"r",stdin);
freopen(
"my.out",
"w",stdout);
scanf(
"%lld",&
x);
while (
x) {
ans[++n]=
x&
1;
x>>=
1;
}
reverse(ans+
1,ans+n+
1);
if (ans[
1]==
0) f[
1][
0][
1]=
1;
else f[
1][
0][
0]=
1,f[
1][
1][
1]=
1;
for (
int i=
1;i<=n-
1;i++)
for (
int j=
0;j<=i;j++)
for (
int k=
0;k<=
1;k++)
if (f[i][j][k]) {
if (k)
for (
int t=
0;t<=ans[i+
1];t++){
if (t==
0) f[i+
1][j][t==ans[i+
1]]+=f[i][j][k];
if (t==
1) f[i+
1][j+
1][t==ans[i+
1]]+=f[i][j][k];
}
else
for (
int t=
0;t<=
1;t++) {
if (t==
0) f[i+
1][j][
0]+=f[i][j][k];
if (t==
1) f[i+
1][j+
1][
0]+=f[i][j][k];
}
}
for (
int i=
1;i<=n;i++) g[i]=f[n][i][
0]+f[n][i][
1];
LL ans=
1;
for (
int i=
1;i<=n;i++) ans=ans
*quickpow(i,g[i])
%p;
printf(
"%lld\n",ans);
}
