首页 > 代码库 > codeforces 215E 数位DP
codeforces 215E 数位DP
题意:一个数的二进制表示如果是一个周期数那么它就是需要的,问[l,r]中有多少个好的数
题解:明显很像数位DP,枚举第一周期的长度,根据第一周期的数值大小来确定有多少种方案,注意首位不能为0.然后就是要注意去重问题,因为对于第一周期长度为k算到的数字,长度为k可以整除的数时必定也算过一遍,减一下就好了,根据这个去重
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<string> 5 #include<algorithm> 6 #include <cmath> 7 using namespace std; 8 typedef long long ll; 9 const ll INF = -100000000000ll;10 const double eps = 1e-8;11 const int maxn = 70;12 const double PI = acos(-1);13 ll dp[maxn],bin[maxn];14 ll l,r;15 int num[maxn],cnt;16 void init(){17 bin[0] = 1;18 for(int i = 1;i <= 62;i++) bin[i] = 2*bin[i-1];19 }20 ll cal(int len,int k,ll x)21 {22 ll a=0,b=0;23 for(int i=0;i<k;i++)24 a+=(num[len-i]<<(k-1-i));25 b=a;26 for(int i=1;i<len/k;i++)27 b<<=k,b+=a;28 return a-(1<<(k-1))+1-(b>x);29 }30 ll solve(ll u){31 cnt = 0;32 ll ans = u,sum = 0;33 while(ans > 0){34 num[++cnt] = ans % 2;35 ans /= 2;36 }37 memset(dp,0,sizeof(dp));38 for(int i = 1;i < cnt;i++){39 // memset(dp,0,sizeof(dp));40 if(cnt % i != 0) continue;41 dp[i]= cal(cnt,i,u);42 for(int j = 1;j < i;j++)43 if(i % j == 0) dp[i] -= dp[j];44 sum += dp[i];45 }46 // cout<<sum<<endl;47 for(int i = 2;i < cnt;i++){48 memset(dp,0,sizeof(dp));49 for(int j = 1;j < i;j++){50 if(i % j) continue;51 dp[j] = bin[j-1];52 for(int k = 1;k < j;k++)53 if(j % k == 0) dp[j] -= dp[k];54 //cout<<i<<" "<<j<<" "<<dp[j]<<endl;55 sum += dp[j];56 }57 }58 // cout<<sum<<endl;59 return sum;60 }61 int main()62 {63 // freopen("in.txt","r",stdin);64 init();65 cin>>l>>r;66 cout<<solve(r) - solve(l-1)<<endl;67 return 0;68 }
codeforces 215E 数位DP
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。