第 45 届国际大学生程序设计竞赛(ICPC)亚洲区域赛(济南)-L Bit Sequence

题意

给你两个数l,m,大小为m的数组a,求[0,l]之间满足以下条件的数x的个数:
对于任何i输入[0,m-1],f(x+i)%2=a[i];f(k):代表k在二进制下1的个数
m的范围

思路

显然l的范围1e18,大概率就是数位DP了

  1. 观察到m是
  2. 那么只要对前半部分进行数位DP,dp[pos][lim][cnt][d]代表位置在pos处,lim代表有无达到上限,cnt为1代表前面有奇数个1为0代表偶数个1,d代表从pos起向前有偶数还是奇数个1;
  3. 对于第七位以后的部分,直接暴力计算就好了,统计以下是否进位;

代码

#include 

using namespace std;

#define nl "n"
#define nf endl
#define ll long long
#define pb push_back
#define _  pw = {23, 19, 17, 13, 11, 9, 7, 5, 4};

ll ask(ll a, ll b) {
   cout > x;
   return x;
}

void clm(ll x) {
   cout > t;
   while (t--) {
       for (i = 1; i 

文章来源于互联网:第 45 届国际大学生程序设计竞赛(ICPC)亚洲区域赛(济南)-L Bit Sequence

THE END
分享
二维码