首页 > 代码库 > 【BZOJ】3209: 花神的数论题

【BZOJ】3209: 花神的数论题

2024-09-04 12:42:06   218人阅读

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=3209

 

显然是按照二进制位进行DP。

考虑预处理$F[i][j]$表示到了二进制的第$i$位，有$j$个$1$的数字有多少个。

显然：${F[i][j]=F[i-1][j-1]+F[i-1][j]}$

组合数。。。

接下来只需补充不漏的计算比$n+1$小的每一个数字对应的1的多少。数位统计即可。

技术分享
 1 llg work(llg x) 2 { 3     llg tot=0; 4     for (llg i=tail;i>=1;i--) 5     { 6         if (x<0) break; 7         if (a[i]) 8         { 9             tot+=c[i-1][x];10               x--;11         }12     }13     return tot;14 }
View Code

(这上面表示的是有二进制中有$x$个$1$的数有多少个)

 1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<vector> 5 #include<cstdlib> 6 #include<cmath> 7 #include<cstring> 8 using namespace std; 9 #define maxn 1001010 #define md 1000000711 #define llg long long 12 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);13 llg n,m,a[maxn],c[100][100],tail,ans;14 15 llg ksm(llg A,llg B)16 {17     llg ans=1;18     while (B)19     {20         if (B%2) ans*=A,ans%=md;21         A*=A; A%=md;22         B/=2;23     }24     return ans;25 }26 27 llg work(llg x)28 {29     llg tot=0;30     for (llg i=tail;i>=1;i--)31     {32         if (x<0) break;33         if (a[i])34         {35             tot+=c[i-1][x];36               x--;37         }38     }39     return tot;40 }41 42 int main()43 {44     yyj("bzoj3209");45     cin>>n;46     n++;47     for (llg i=0;i<=60;i++) c[i][0]=1;48     for (llg i=1;i<=60;i++)49         for (llg j=1;j<=i;j++)50             c[i][j]=c[i-1][j]+c[i-1][j-1];51     while (n!=0)52     {53         a[++tail]=n%2;54         n/=2;55     }56     ans=1;57     for (llg i=1;i<=60;i++) 58         ans*=ksm(i,work(i)),ans%=md;59     cout<<ans;60     return 0;61 }

 

【BZOJ】3209: 花神的数论题


联系
我们