bzoj 3209: 花神的数论题

限于本人DP处于背包--水平，不组声（就是对神奇的数位DP，找出j个1的有多少个，然后j的多少个次方就行）

 1 #include<bits/stdc++.h>
 2 #define N 100005
 3 #define LL long long
 4 #define inf 0x3f3f3f3f
 5 using namespace std;
 6 inline LL ra()
 7 {
 8     LL x=0,f=1; char ch=getchar();
 9     while (ch<'0' || ch>'9') {if (ch=='-') f=-1; ch=getchar();}
10     while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();}
11     return x*f;
12 }
13 const LL mod=10000007LL;
14 int l,wei[100];
15 LL c[100][100],n,ans; 
16 void pre()
17 {
18     for (int i=0; i<=60; i++) c[i][0]=1;
19     for (int i=1; i<=60; i++)
20         for (int j=1; j<=i; j++)
21             c[i][j]=c[i-1][j-1]+c[i-1][j];
22 }
23 LL ksm(LL a, LL b)
24 {
25     LL sum=1; a%=mod;
26     for(;b;b>>=1,a=a*a%mod)
27         if (b&1LL) sum=sum*a%mod;
28     return sum;
29 }
30 LL solve(int x)
31 {
32     LL sum=0;
33     for (int i=l; i>=1; i--)
34     {
35         if (wei[i]==1)
36             sum+=c[i-1][x--];//计算的时候默认i位是0，计算完后默认i位是1，，应该是这样子的，，不会dp不会dp，，，
37                              //这样求出来的应该就是最小值了233 
38         if (x<0) break;
39     }
40     return sum;
41 }
42 int main()
43 {
44     pre(); n=ra()+1;
45     while (n)
46     {
47         wei[++l]=n&1;
48         n>>=1;
49     }
50     ans=1LL;
51     for (int i=1; i<=l; i++)
52         ans=ans*ksm(i,solve(i))%mod;
53     printf("%lld
",ans);
54     return 0;
55 }