洛谷P4317

Description

定义 \(sum(i)\) 表示 \(i\) 的二级制中 1 的个数

给定一个 N，求 \(\prod_{i=1}^N sum(i)\)

Solution

显然是数位 DP

考虑 DP 数组应存储的信息以及维数

设 \(f[i][j][k]\) 表示枚举到第 i 位，数字为 j，此时二进制中 1 的个数为 k

由 Suzt_ilymtics 的口胡和 Aliemo 的证明可得转移方程和限制条件：

\[f[i][0][j]=\sum_{k=0}^if[i-1][1][k]+f[i-1][0][k]
\]

\[f[i][1][j]=\sum_{k=1}^if[i-1][0][k-1]+f[i-1][1][k-1]
\]

然后，对于答案的统计

对于首位为 1 且前面有 \(cnt\) 个 1 的 \(f\) ,

\[ans=ans\times (j+cnt)^{f[i][0][j]}\mid i\in[1,len),j\in[1,len/2-cnt]
\]

而对于首位为 0 的 \(f\)，

\[ans=ans\times j^{f[i][1][j]}\mid i\in [1,len),j\in[1,i/2]
\]

最后答案就是 \(ans_{1,N}\)

自己在做题过程中有许多错误，总结一下：

注意边界问题和初始化问题
注意什么地方该取模（统计）
注意限制条件的判断以及循环中上下界的大小
压行什么得确保没问题了再说，避免 Debug 困难

Code

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<algorithm>

#include<queue>

#include<cmath>

#include<cstring>

#define Mod 10000007

#define int long long

using namespace std;

int a[50];

int n,f[80][2][80];

inline int read(){

	int s=0,w=1;char ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}

	while(ch>='0'&&ch<='9') s=(s<<1)+(s<<3)+ch-'0',ch=getchar();

	return w*s;

}

inline int Pow(int x,int y){

	int ans=1;

	while(y){if(y&1)ans=(ans*x)%Mod;x=(x*x)%Mod;y>>=1;}

	return ans%Mod;

}

inline void init(){

	f[1][1][1]=1;f[1][0][0]=1;

	for(register int i=2;i<64;i++)

		for(register int j=0;j<=1;j++)

			for(register int k=0;k<=i;k++)

				for(register int s=0;s<=1;s++){

					if(j==0) f[i][j][k]+=f[i-1][s][k];

					if(j==1&&k!=0) f[i][j][k]+=f[i-1][s][k-1];

				}

}

inline int solve(int x){

	memset(a,0,sizeof a);

	int len=0,cnt=1,ans=0;

	while(x){a[++len]=x%2;ans+=a[len],x/=2;}

	for(register int i=len-1;i>=1;i--){

		if(a[i]) for(register int j=0;j<=len-cnt;j++)

			if(f[i][0][j]!=0) ans=(ans*Pow(j+cnt,f[i][0][j]))%Mod;

		cnt+=a[i];

	}

	for(register int i=1;i<len;i++)

		for(register int j=1;j<=i;j++)

			if(f[i][1][j]!=0) ans=(ans*Pow(j,f[i][1][j]))%Mod;

	return ans%Mod;

}

signed main(){

	n=read();init();

	printf("%lld",solve(n));

	return 0;

}

巴特西

洛谷P4317

Description

Solution

Code

最新文章

热门文章