首页 > 代码库 > 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