首页 > 代码库 > [BZOJ 3209]花神的数论题
[BZOJ 3209]花神的数论题
一道简单的数位 dp 题
但是脑子里只有 __builtin_popcountll 了呢（自重）
看完题解后很快就理解了，而且有一种这么简单的题居然没想到做法真是不应该唉~的感觉
用 f[i] 表示 1 的位数为 i 且小于 n 的数的个数
然后答案就是 Πif[i] ，而 f[i] 的话从高到低 dp 用组合数乱搞搞一下就可以了 O((lgn)2)
比如说前 i-1 位有 k 位 1 ，第 i 位是 1 ，后面还有 j 位数
然后令第 i 位取 0 ，那么无论后 j 位取了什么数，都比 n 小，用组合数来更新 f[k+l] (0<=l<=j) 即可
但是 WA 了好久噻，愕然发现 10000007 这个比赛中超常用的模数居然
不！是！质！数！
10000007=941*10627
然后用费马小定理的我就这样 biubiu~
只好边枚举边算答案
以后果然一定要注意一下了，以上
1 #include <cstdio> 2 typedef long long LL; 3 const int mod=10000007; 4 const int size=64; 5 6 LL n; 7 LL ans; 8 LL c[size][size]; 9 LL f[1024];10 inline LL getint();11 inline void putint(LL);12 inline int lg(LL);13 inline LL mul(LL, LL);14 inline LL pow(LL, LL);15 inline void calc();16 17 int main()18 {19 n=getint();20 ans=1;21 calc();22 putint(ans);23 24 return 0;25 }26 inline LL getint()27 {28 register LL num=0;29 register char ch;30 do ch=getchar(); while (ch<‘0‘ || ch>‘9‘);31 do num=num*10+ch-‘0‘, ch=getchar(); while (ch>=‘0‘ && ch<=‘9‘);32 return num;33 }34 inline void putint(LL num)35 {36 char stack[21];37 register int top=0;38 if (num==0) stack[top=1]=‘0‘;39 for ( ;num;num/=10) stack[++top]=num%10+‘0‘;40 for ( ;top;top--) putchar(stack[top]);41 putchar(‘\n‘);42 }43 inline int lg(LL x)44 {45 int ret=0;46 for ( ;x>1;x>>=1) ret++;47 return ret;48 }49 inline LL mul(LL a, LL b)50 {51 return a*b%mod;52 }53 inline LL pow(LL a, LL b)54 {55 LL c=1;56 for ( ;b;b>>=1)57 {58 if (b & 1) c=mul(c, a);59 a=mul(a, a);60 }61 return c;62 }63 inline void calc()64 {65 for (int i=0;i<64;i++)66 {67 c[i][0]=1;68 for (int j=1;j<i;j++)69 c[i][j]=c[i-1][j-1]+c[i-1][j];70 c[i][i]=1;71 }72 int k=0;73 for (int i=lg(n);i>=0;i--) if ((n>>i) & 1)74 {75 ans=mul(ans, k+1);76 for (int j=1;j<=i;j++)77 ans=mul(ans, pow(k+j, c[i][j]));78 ++k;79 }80 }
[BZOJ 3209]花神的数论题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。