欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

2018.10.27 bzoj3209: 花神的数论题(数位dp)

程序员文章站 2022-05-21 12:10:13
...

传送门
数位dpdp经典题。
题面已经暗示了我们按照二进制位来数位dpdp
直接dpdp多少个数有1111,2211,3311…,
然后快速幂算就行了。
于是我们枚举前几位跟nn相同,后面比nn小的方案数。
这个显然是可以用组合数算的。
注意nn自己的也要算进贡献。
代码:

#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;
}
相关标签: dp