[BZOJ 3209]花神的数论题

一道简单的数位 dp 题

但是脑子里只有 __builtin_popcountll 了呢（自重）

看完题解后很快就理解了，而且有一种这么简单的题居然没想到做法真是不应该唉~的感觉

用 f[i] 表示 1 的位数为 i 且小于 n 的数的个数

然后答案就是 Πi^f[i]，而 f[i] 的话从高到低 dp 用组合数乱搞搞一下就可以了 O((lgn)²)

比如说前 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('
');
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 }

本傻 WA 出翔系列