UVaLive 7634 - Game of XOR

发表于 分类于 Disqus：

链接

传送门

题意

给出一个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;
}
相关文章