2018.10.27 bzoj3209: 花神的数论题（数位dp）

传送门

数位dpdpdp经典题。

题面已经暗示了我们按照二进制位来数位dpdpdp。

直接dpdpdp多少个数有111个111,222个111,333个111…,

然后快速幂算就行了。

于是我们枚举前几位跟nnn相同，后面比nnn小的方案数。

这个显然是可以用组合数算的。

注意nnn自己的也要算进贡献。

代码：

#include<bits/stdc++.h>using namespace std;typedef long long ll;const int mod=10000007;ll n,C[65][65],ans=1,cnt[65];int len,pre;inline ll ksm(ll x,ll p){ll ret=1;for(;p;p>>=1,x=x*x%mod)if(p&1)ret=ret*x%mod;return ret;}int main(){cin>>n;for(int i=0;i<=60;++i){C[i][0]=1;for(int j=1;j<=i;++j)C[i][j]=C[i-1][j-1]+C[i-1][j];}while((1ll<<len)<=n)++len;for(int i=len-1;~i;--i)if((n>>i)&1){for(int j=0;j+pre<=len;++j)cnt[j+pre]+=C[i][j];++pre;}++cnt[pre];for(int i=2;i<=60;++i)(ans*=ksm(i,cnt[i]))%=mod;cout<<ans;return 0;}