BZOJ 3780 数字统计

发表于 | 更新于

Link

Solution

从低位到高位DP。。现在感觉这种边DP边卡的做法很舒服啊。。 f[i][0/1][0/1]f[i][0/1][0/1]表示第ii位，是否卡到了上界(卡上界的情况需要包含超上界的情况，因为是从低到高DP的)，删之后剩下了0/10/1的方案数目。转移的时候和从高到低的判断条件不太一样，不要手滑写错。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include "lucida"
using std::reverse;
using std::max;
const int MAXB=200+11;
IO::Ost &operator <<(IO::Ost &,struct BinNum &); 
struct BinNum {
	short a[MAXB];int n;
	short &operator [](int x) {
		return a[x];
	}
	BinNum(int x=0) {
		memset(a,0,sizeof(a));
		for(n=0;x;x>>=1)
			a[++n]=x&1;
	}
	friend BinNum operator +(BinNum a,BinNum b) {
		int &n=a.n=max(a.n,b.n);
		for(int i=1;i<=n;++i) {
			a[i]+=b[i];
		}
		for(int i=1;i<=n;++i) {
			a[i+1]+=a[i]>>1;
			a[i]&=1;
			if(a[i+1]) 
				chkmx(n,i+1);
		}
		return a;
	}
	friend BinNum operator -(BinNum a,BinNum b) {
		int &n=a.n=max(a.n,b.n);
		for(int i=1;i<=n;++i)
			a[i]-=b[i];
		for(int i=1;i<=n;++i)
			if(a[i]<0) {
				a[i]+=2;
				a[i+1]--;
			}
		while(n && !a[n]) --n;//n..
		return a;
	}
	#define template template <class T>
	template BinNum &operator +=(T a) {
		return *this=*this+a;
	}
	template BinNum &operator -=(T a) {
		return *this=*this-a;
	}
	#undef template
};
IO::Ist &operator >>(IO::Ist &is,BinNum &x) {
	int &n=x.n=0;
	char ch;
	while(ch=getchar(),(ch!='0' && ch!='1'));
	do	x[++n]=ch-'0';
	while(ch=getchar(),(ch=='0' || ch=='1'));	
	reverse(x.a+1,x.a+1+n);
	return is;
}
IO::Ost &operator <<(IO::Ost &os,BinNum &x) {
	int p=x.n;
	while(p && !x[p]) p--;
	if(p) do 
		putchar(x[p--]+'0');
	while(p);
	else putchar('0');
	return os;
}
BinNum f[MAXB][2][2];//定义成了int64????2333..
BinNum Calc(BinNum x,int Y) {
	#define merge(x,y) ((x)==0 && (y)==0)
	memset(f,0,sizeof(f));
	//f[i][(f)0/1][(s)0/1] 表示后i位,</>= x,删出来的结果为0/1
	//答案就是f[len][0][Y]
	for(int i=0;i<2;++i)
		f[1][i>=x[1]][i]=1;
	for(int i=2;i<=x.n;++i) {
		for(int dt=0;dt<2;++dt)
			for(int ff=0;ff<2;++ff)
				for(int fs=0;fs<2;++fs) {
					f[i][dt>x[i] || (dt==x[i] && ff)][merge(dt,fs)]+=f[i-1][ff][fs];	
				}
	}
	return f[x.n][0][Y];
}
void Work() {
	int M,Y;is>>M>>Y;
	BinNum l,r;is>>l>>r;
	BinNum Ans=Calc(r+1,Y)-Calc(l,Y);
	os<<Ans<<'\n';
}
int main() {
//	freopen("input","r",stdin);
	int T;is>>T;
	while(T--)
		Work();
	return 0;
}