UVaLive 7634 - Game of XOR

链接

传送门

题意

给出一个01串长度为$s(1 \leq s \leq 100000)$,进行$g(1 \leq g \leq 10000)$次分裂(貌似是这个意思,队友读的题),再给出起点、终点和两点在分裂时移动的方向,输出起点到终点的闭区间内0和1的个数。

思路

当前数字分裂生成的数字与后继数字有关,有:

  • $00 \rightarrow 000$
  • $01 \rightarrow 011$
  • $10 \rightarrow 110$
  • $11 \rightarrow 101$

因此可以DP求出每个点位分裂$i(0 \leq i \leq g)$次后生成的0和1的个数,剩下的就是模拟了。

有一个trick是$g=1$时,两个路径为空串。

代码

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
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int mod = 342307123;
const int maxn = 100010;
const int maxg = 10010;
const int a[5] = {0, 1, 3, 2};
const int b[5] = {0, 3, 2, 1};
char s[maxn], t1[maxg], t2[maxg];
LL cnt[5];
int dp[5][maxg];
inline int getVal(int x) {
if (s[x + 1] == 0) {
return (s[x] - '0') << 1;
}
return ((s[x] - '0') << 1) + s[x + 1] - '0';
}
LL pow_mod(LL x, int k) {
LL res = 1, cur = x;
while (k) {
if (k & 1) {
res = (res * cur) % mod;
}
cur = (cur * cur) % mod;
k >>= 1;
}
return res;
}
int main() {
dp[1][0] = 0, dp[2][0] = 1, dp[3][0] = 1;
for (int i = 1; i < maxg; ++i) {
for (int j = 1; j < 4; ++j) {
dp[j][i] = (dp[a[j]][i - 1] + dp[b[j]][i - 1]) % mod;
}
}
int t, tt = 0;
scanf("%d", &t);
while (t--) {
int g, p1, p2;
scanf("%s%d", s, &g);
--g;
if (g == 0) {
scanf("%d%d", &p1, &p2);
} else {
scanf("%d%s%d%s", &p1, t1, &p2, t2);
}
memset(cnt, 0, sizeof cnt);
for (int i = p1; i < p2; ++i) {
++cnt[getVal(i)];
}
LL ans = 0;
for (int i = 0; i < 4; ++i) {
ans = (ans + cnt[i] * dp[i][g]) % mod;
}
int st1 = getVal(p1), st2 = getVal(p2);
LL sum = (pow_mod(2, g) * (p2 - p1) + 1)% mod;
for (int i = 0; i < g; ++i) {
if (t1[i] == 'R') {
ans = (ans - dp[a[st1]][g - i - 1] + mod) % mod;
sum = (sum - pow_mod(2, g - i - 1) + mod) % mod;
st1 = b[st1];
} else {
st1 = a[st1];
}
if (t2[i] == 'R') {
ans = (ans + dp[a[st2]][g - i - 1]) % mod;
sum = (sum + pow_mod(2, g - i - 1)) % mod;
st2 = b[st2];
} else {
st2 = a[st2];
}
}
ans += a[st2] >> 1;
printf("Case %d: %d %d\n", ++tt, int((sum - ans + mod) % mod), int(ans));
}
return 0;
}

支付宝扫码领红包