首页 > 代码库 > BZOJ:3209: 花神的数论题
BZOJ:3209: 花神的数论题
今天居然没参考任何资料解决了这道数位DP，事先只是搞一道数论题练练；
思路：求SUM[1]-SUM[N]的二进制的乘积mod1000000007；
N<=10^15;BZOJ的题不会是几个简单的FOR就完结的，
假如N的二进制是：1001001；
位数：1234567
那么当第一位是0的情况：那么数就是000000-111111
序列号： 123456-123456
发现我们可以用排列组合算出二进制有1-6个1的数比如：1个1就是C[6][1],2个1就是C[6][2],......
当第一位是0：那么就看下一位为1的位置，去枚举计算，注意第一位为1后面全部为0的情况我们要考虑。
说的比较不靠谱。
比如：第一位为0;那么枚举1-6位的位置；
当第一位为1是：可能1-6位都为0，所以前面的这个1要考虑，
可以自己画画
#include<stdio.h>#include<iostream>#include<string.h>#include<math.h>using namespace std;#define N 10000007typedef long long ll;ll c[61][61];int b[61];ll kuai(ll a,ll b)//快速米{ ll ans=1; while (b) { if (b&1) ans=ans*a%N; a=a*a%N; b/=2; } return ans;}int main(){ ll n; int t=0; for (int i=0;i<=61;i++)//预先计算排列组合 c[i][0]=1; for (int i=1;i<=60;i++) for (int j=1;j<=60;j++) c[i][j]=(c[i-1][j]+c[i-1][j-1]); scanf("%lld",&n); while (n) { t++; if (n&1) b[t]=1; n/=2; } int k=0; ll ans=1; for (int i=t;i>=1;i--) if (b[i]) { ans=ans*(k+1)%N; for (int j=1;j<=i-1;j++) ans=ans*kuai(j+k,c[i-1][j])%N; k++; } printf("%d\n",ans); return 0;}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。