【BZOJ3209】花神的数论题（数位DP）

大致题意： 设\(sum(i)\)表示\(i\)二进制中1的个数，请求出\(\prod_{i=1}^n sum(i)\)。

数位\(DP\)

很显然，这是一道数位\(DP\)题。我们可以先将\(n\)转化为二进制，然后DP预处理，最后求答案。

设\(f[i][j]\)表示当前数字的1~\(i\)位中共有\(j\)个1，这可以得到转移方程：

f[i][j]=f[i-1][j]+f[i-1][j-1];

初始时将全部\(f[i][0]\)赋值为1。

然后我们就能发现，这样子我们就相当于求出了一个杨辉三角形。

最后，再对\(sum(i)\)的每一种可能值依次进行操作，求出有多少个数在二进制下有\(i\)个1，再用快速幂将其累乘即可求出答案。

代码

#include<bits/stdc++.h>

#define LL long long

#define YKH 10000007

using namespace std;

LL n,ans=1ll,tot,num[100],f[100][100];

inline char tc()

{

    static char ff[100000],*A=ff,*B=ff;

    return A==B&&(B=(A=ff)+fread(ff,1,100000,stdin),A==B)?EOF:*A++;

}

inline void read(LL &x)

{

    x=0;LL f=1;char ch;

    while(!isdigit(ch=tc())) f=ch^'-'?1:-1;

    while(x=(x<<3)+(x<<1)+ch-'0',isdigit(ch=tc()));

    x*=f;

}

inline void write(LL x)

{

    if(x<0) putchar('-'),x=-x;

    if(x>9) write(x/10);

    putchar(x%10+'0');

}

inline LL quick_pow(LL x,LL y)//快速幂

{

    LL res=1;

    while(y)

    {

        if(y&1) (res*=x)%=YKH;

        (x*=x)%=YKH,y>>=1;

    }

    return res;

}

inline LL doing(LL x)//求出二进制下含有i个1的数的个数，利用了先前求出的杨辉三角形

{

	LL sum=0;//统计个数

	for(register LL i=tot;i>0;--i)

	{

		if(num[i]) sum+=f[i-1][x--];//判断该位是否为1

		if(x<0) return sum;//如果x小于0，返回sum

	}

	return sum;

}

int main()

{

    register LL i,j;LL w;

    for(read(n),w=n+1,tot=0;w;num[++tot]=w&1,w>>=1);

    for(i=0;i<=tot;++i) f[i][0]=1;

    for(i=1;i<=tot;++i)//预处理出一个杨辉三角形

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

    		f[i][j]=f[i-1][j]+f[i-1][j-1];

    for(i=1;i<=tot;++i)

        (ans*=quick_pow(i,doing(i)))%=YKH;//求出答案，并累乘

    return write(ans),0;

}

巴特西

【BZOJ3209】花神的数论题（数位DP）

数位\(DP\)

代码

最新文章

热门文章