题面

JZM 想要创造两个数字 x 和 y，它们需要满足 x or y = T，且L_x ≤ x ≤ R_x, L_y ≤ y ≤ R_y，JZM 想知道 x and y 有多少种可能的不同的取值。若有多组 (x, y) 有相同的 x and y 的取值，则只算一次。

0 ≤ T,L_x,R_x,L_y,R_y < 2⁶⁰.

Sample Input
11 3 10 8 13
Sample Output
7

题解

看上去貌似是数位 DP，于是我们就设计一个 DP：

[

]

[

]

[

]

[

]

[

]

dp[i][s_1][s_2][s_3][s_4]

dp[i][s1][s2][s3][s4] 表示[当前转移到第

i 位，

x 是/否达到下界，

x 是/否达到上界，

y 是/否达到下界，

y 是/否达到上界]时

x and y

\text{x and y}

x and y 有多少种不同的取值。

然后观察样例，我们发现这不好转移，原因是本质相同的一种与值很容易计算多次。我们如果能保证当前位与值为 1 时和为 0 时两种情况能唯一转移到其它状态，这样就能保证不重复。但是如果当前位与值为 0 ，

x,y

x,y 可以是

0 & 1

\text{0 \& 1}

0 & 1，

1 & 0

\text{1 \& 0}

1 & 0 或

0 & 0

\text{0 \& 0}

0 & 0，而三种情况

{

}

\{s_1,s_2,s_3,s_4\}

{s1,s2,s3,s4} 结果不一样，那么就不可避免的要么计算重复，要么计算缺失了。

如果说这种情况能唯一对应一个状态的话，那就是状态集

{

}

{

}

\{\{s_1,s_2,s_3,s_4\}_1,\{s_1,s_2,s_3,s_4\}_2,...\}

{{s1,s2,s3,s4}1,{s1,s2,s3,s4}2,...} ，表示集合中每一种状态

{

}

\{s_1,s_2,s_3,s_4\}_i

{s1,s2,s3,s4}i 都可行。不同的

{

}

\{s_1,s_2,s_3,s_4\}

{s1,s2,s3,s4} 一共有

2^4=16

24=16 种，不妨就记为二进制数

0000—1111

\text{0000---1111}

0000—1111 ，那我们就可以用

2^{16}

216 以内的二进制数来表示状态集，第

i 位上表示

0000—1111

\text{0000---1111}

0000—1111 这 16 种状态的第

i 种是否可能。（状态有

2^4=16

24=16 种，状态集有

2^{2^4}=2^{16}

224=216 种）

于是我们可以设计一个状态数为

log

⁡

∗

\log T*2^{16}

logT∗216 的 DP：

[

]

[

]

dp[i][S]

dp[i][S] 表示进行到第

i 位，状态集为

S. 转移的时候就把状态集

S 中每一种可能的状态进行转移，然后处理出下一位每一种状态是否可行，以便处理出新的状态集

′

S'_0

S0′ 和

′

S'_1

S1′（对应当前位的与值为 0 或 1）。

这应该是做过的单次复杂度最高的数位 DP 了，复杂度为

(

log

⁡

∗

)

O(\log T*2^{16}*16)

O(logT∗216∗16) （按道理复杂度中不应该带常数的）。

CODE

#include<set>

#include<map>

#include<cmath>

#include<queue>

#include<vector>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

#define MAXN 100005

#define DB double

#define LL long long

#define ENDL putchar('\n')

#define lowbit(x) (-(x) & (x))

#pragma GCC optimize(2)

LL read() {

	LL f = 1,x = 0;char s = getchar();

	while(s < '0' || s > '9') {if(s=='-')f = -f;s = getchar();}

	while(s >= '0' && s <= '9') {x=x*10+(s-'0');s = getchar();}

	return f * x;

}

const int MOD = 998244353;

int n,m,i,j,s,o,k;

LL T,l1,r1,l2,r2;

LL dp[65][1<<16|5];

int cg(int i,int ss,int x,int y) {

	int s1 = (ss&1),s2 = ((ss>>1)&1),s3 = ((ss>>2)&1),s4 = ((ss>>3)&1);

	int b1 = (s1 ? ((l1>>i)&1):0),t1 = (s2 ? (((r1&T)>>i)&1):((T>>i)&1));

	int b2 = (s3 ? ((l2>>i)&1):0),t2 = (s4 ? (((r2&T)>>i)&1):((T>>i)&1));

	if(x < b1 || x > t1 || y < b2 || y > t2 || (x|y) != ((T>>i)&1)) return 16;

	int res = 0;

	if(x == ((l1>>i)&1) && s1) res |= 1;

	if(x == ((r1>>i)&1) && s2) res |= (1<<1);

	if(y == ((l2>>i)&1) && s3) res |= (1<<2);

	if(y == ((r2>>i)&1) && s4) res |= (1<<3);

	return res;

}

int main() {

	freopen("number.in","r",stdin);

	freopen("number.out","w",stdout);

	T = read();l1 = read();r1 = read();l2 = read();r2 = read();

	dp[60][1<<15] = 1;

	for(int i = 59;i >= 0;i --) {

		for(int S = 0;S < (1<<16);S ++) {

			if(!dp[i+1][S]) continue;

			int S1 = 0,S0 = 0;

			for(int j = 0;j < 16;j ++) {

				if(!(S & (1<<j))) continue;

				S1 |= (1<<cg(i,j,1,1));

				S0 |= (1<<cg(i,j,1,0));

				S0 |= (1<<cg(i,j,0,1));

				S0 |= (1<<cg(i,j,0,0));

			}

			S1 &= ((1<<16)-1);

			S0 &= ((1<<16)-1);

			if(S1) dp[i][S1] += dp[i+1][S];

			if(S0) dp[i][S0] += dp[i+1][S];

		}

	}

	LL ans = 0;

	for(int i = 1;i < (1<<16);i ++) {

		ans += dp[0][i];

	}

	printf("%lld\n",ans);

	return 0;

}

巴特西

造数字（数位DP）

题面

题解

CODE

最新文章

热门文章