最近越来越懒了，估了很长时间的题解， OI 生涯结束前是凑不够 200 篇博客了，但退役前还是努力写点东西吧。
第一次写题解的大约在暑假集训，原因是当时改模拟赛题目经常参考学长的博客，于是自己也尝试这写了博客；然而省选以后，改题就很少参考学长的博客，一个原因是很难找到模拟赛题目的题解，一个原因是下发题解大多数也能理解了（貌似不理解的题都被我直接弃了）。从那之后自己的题解就变的很不连续， 3 个多月只写了 40 篇左右题解。
T1 染色题
观察题目的性质，容易发现奇数位置和偶数位置的颜色互不干扰，对于任意序列，如果 \(a_{i}\) 和 \(a_{i+2}\) 不相等，我们认为 \(i\) 位置上存在一个小球，容易发现原题目限制相当于区间 \(L, R\) 不存在奇数和偶数位置都存在小球。考虑 dp 求解方案，设 \(f_i\) 表示当前最后一个小球在位置 \(i\) 的方案数，枚举 \(i\) 前合法的 \(j\) 进行转移即可，由于合法的奇偶性相同的 \(j\) 构成一段区间，可以使用前缀和优化为 \(O(n)\) 。注意到确定 \(a_1, a_2\) 后整个序列才能完全确定，因此总方案数乘以 \(8\) 即为答案。
code
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int max1 = 1e6;
const int mod = 998244353;
const int inf = 0x3f3f3f3f;
int n, m, Min[max1 + 5];
int f[max1 + 5], sum[max1 + 5], ans;
void Add ( int &x, int y )
{
x += y;
if ( x >= mod )
x -= mod;
return;
}
int main ()
{
freopen("colour.in", "r", stdin);
freopen("colour.out", "w", stdout);
scanf("%d%d", &n, &m);
for ( int i = 1; i <= n; i ++ )
Min[i] = i;
for ( int i = 1, L, R; i <= m; i ++ )
{
scanf("%d%d", &L, &R);
if ( R > 2 )
Min[R - 2] = min(Min[R - 2], L);
}
for ( int i = n - 1; i >= 1; i -- )
Min[i] = min(Min[i + 1], Min[i]);
f[0] = sum[0] = ans = 1;
for ( int i = 1; i <= n - 2; i ++ )
{
if ( i > 1 )
f[i] = sum[i - 2];
int p = Min[i] - 1 - ((Min[i] ^ i) & 1);
if ( p >= 0 )
Add(f[i], sum[p]);
sum[i] = f[i];
if ( i > 1 )
Add(sum[i], sum[i - 2]);
Add(ans, f[i]);
}
ans = 8LL * ans % mod;
printf("%d\n", ans);
return 0;
}
T2 石头剪刀布
首先考虑枚举 \(u\) ，容易发现 \(u\) 向上合并的过程可以类似线段树进行优化为 \(O(\log n)\) 。
设函数 \(f(L, R, x, y)\) 表示选手编号位于 \([L, R]\) ， \(u\) 编号位于 \([x, y]\) 的答案，设 \(mid=\tfrac{L+R}{2}\) ，发现对于 \(u<mid\) ，都会和 \([mid, R]\) 区间的概率合并，对于 \(u>mid\) ，都会和 \([L, mid]\) 的区间的概率合并，因此 \(f\) 函数可以递归进行求解。不难发现 \(f\) 函数会递归形成 \(O(\log n)\) 个区间，满足 \(x\le L\le R\le y\) ，这部分的概率是可以直接预处理的，总复杂度可以做到 \(O(n\log n)\) 。
code
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <ctime>
#include <iostream>
using namespace std;
const int max1 = 3e5;
const int mod = 998244353;
int n, m;
char s[max1 + 5];
int inv[max1 + 5];
struct Data
{
int f[3];
void Clear ()
{
memset(f, 0, sizeof(f));
return;
}
Data operator + ( const Data &A ) const
{
Data res; res.Clear();
res.f[0] = (res.f[0] + 1LL * f[0] * A.f[0]) % mod;
res.f[0] = (res.f[0] + 2LL * f[0] * A.f[1] % mod * inv[3]) % mod;
res.f[1] = (res.f[1] + 1LL * f[0] * A.f[1] % mod * inv[3]) % mod;
res.f[0] = (res.f[0] + 1LL * f[0] * A.f[2] % mod * inv[3]) % mod;
res.f[2] = (res.f[2] + 2LL * f[0] * A.f[2] % mod * inv[3]) % mod;
res.f[1] = (res.f[1] + 1LL * f[1] * A.f[1]) % mod;
res.f[1] = (res.f[1] + 2LL * f[1] * A.f[2] % mod * inv[3]) % mod;
res.f[2] = (res.f[2] + 1LL * f[1] * A.f[2] % mod * inv[3]) % mod;
res.f[1] = (res.f[1] + 1LL * f[1] * A.f[0] % mod * inv[3]) % mod;
res.f[0] = (res.f[0] + 2LL * f[1] * A.f[0] % mod * inv[3]) % mod;
res.f[2] = (res.f[2] + 1LL * f[2] * A.f[2]) % mod;
res.f[2] = (res.f[2] + 2LL * f[2] * A.f[0] % mod * inv[3]) % mod;
res.f[0] = (res.f[0] + 1LL * f[2] * A.f[0] % mod * inv[3]) % mod;
res.f[2] = (res.f[2] + 1LL * f[2] * A.f[1] % mod * inv[3]) % mod;
res.f[1] = (res.f[1] + 2LL * f[2] * A.f[1] % mod * inv[3]) % mod;
return res;
}
};
Data P[max1 + 5][20];
pair <Data, int> Q[max1 + 5][20];
pair <Data, int> Solve ( int L, int R, int x, int y )
{
pair <Data, int> res;
if ( L >= x && R <= y )
return Q[L][__lg(R - L + 2)];
int mid = (L + R) >> 1;
if ( y <= mid )
{
res = Solve(L, mid - 1, x, y);
res.first = res.first + P[mid][__lg(R - mid + 1)];
return res;
}
if ( x >= mid )
{
res = Solve(mid + 1, R, x, y);
res.first = P[L][__lg(mid - L + 1)] + res.first;
return res;
}
pair <Data, int> resL = Solve(L, mid - 1, x, y), resR = Solve(mid + 1, R, x, y);
resL.first = resL.first + P[mid][__lg(R - mid + 1)];
resR.first = P[L][__lg(mid - L + 1)] + resR.first;
res.second = resL.second + resR.second;
res.first.f[0] = (1LL * resL.first.f[0] * resL.second + 1LL * resR.first.f[0] * resR.second) % mod * inv[res.second] % mod;
res.first.f[1] = (1LL * resL.first.f[1] * resL.second + 1LL * resR.first.f[1] * resR.second) % mod * inv[res.second] % mod;
res.first.f[2] = (1LL * resL.first.f[2] * resL.second + 1LL * resR.first.f[2] * resR.second) % mod * inv[res.second] % mod;
return res;
}
int main ()
{
freopen("rps.in", "r", stdin);
freopen("rps.out", "w", stdout);
scanf("%d%d%s", &n, &m, s + 1);
inv[1] = 1;
for ( int i = 2; i <= max(3, n); i ++ )
inv[i] = 1LL * (mod - mod / i) * inv[mod % i] % mod;
for ( int i = 1; i <= n; i ++ )
{
P[i][0].Clear();
if ( s[i] == 'R' )
P[i][0].f[0] = 1;
else if ( s[i] == 'S' )
P[i][0].f[1] = 1;
else
P[i][0].f[2] = 1;
}
for ( int k = 1; (1 << k) <= n; k ++ )
for ( int i = 1; i + (1 << k) - 1 <= n; i ++ )
P[i][k] = P[i][k - 1] + P[i + (1 << (k - 1))][k - 1];
for ( int i = 1; i <= n; i ++ )
{
Q[i][1].first.Clear();
Q[i][1].second = 1;
if ( s[i] == 'R' )
Q[i][1].first.f[0] = 1;
else if ( s[i] == 'S' )
Q[i][1].first.f[1] = 1;
else
Q[i][1].first.f[2] = 1;
}
Data tmp1, tmp2;
for ( int k = 2; (1 << k) - 1 <= n; k ++ )
{
for ( int i = 1; i + (1 << k) - 2 <= n; i ++ )
{
Q[i][k].second = Q[i][k - 1].second + Q[i + (1 << (k - 1))][k - 1].second;
tmp1 = Q[i][k - 1].first + P[i + (1 << (k - 1)) - 1][k - 1];
tmp2 = P[i][k - 1] + Q[i + (1 << (k - 1))][k - 1].first;
for ( int j = 0; j < 3; j ++ )
Q[i][k].first.f[j] = 1LL * (tmp1.f[j] + tmp2.f[j]) * inv[2] % mod;
}
}
int L, R, x, y;
while ( m -- )
{
scanf("%d%d%d%d", &L, &R, &x, &y);
printf("%d\n", Solve(L, R, x, y).first.f[0]);
}
return 0;
}
T3 树状数组
预处理 \(f_{i, k, 0/1}\) 表示当前位于序列第 \(i\) 个位置，只考虑低 \(k\) 位，初始第 \(k\) 位为 \(0/1\) ，其余位为 \(0\) 时，第一个满足低 \(k\) 位均为 \(0\) 的时刻，通过判断 \(f_{i, k-1, 0/1}\) 很容易求解 \(f_{i, k, 0/1}\) 。
预处理 \(ans_i\) 表示初始值为 \(0\) ，经过 \([i, n]\) 的所有操作后得到的数，转移考虑找到最大的满足存在 \(f_{i, k, 0}\) 的 \(k\) ，容易发现高于 \(k\) 的二进制位不会收到 \(-1\) 操作的影响，直接异或求解即可，小于等于 \(k\) 的二进制位可以继承 \(f_{i, k, 0}\) 处的 \(ans\) 信息。
考虑查询，从低到高依次枚举 \(x\) 的二进制位，通过跳 \(f_{L, i, 0}\) 可以消去 \(x\) 的第 \(i\) 位，如果不存在对应的 \(f_{L, i, 0}\) ，说明第 \(i\) 位及以上不会受到 \(-1\) 操作的影响，此时可以直接得到答案。
code
#include <cstdio>
#include <algorithm>
using namespace std;
const int max1 = 5e5;
const int inf = 0x3f3f3f3f;
int n, m, k, A, B;
int val[max1 + 5], sum[max1 + 5];
int f[max1 + 5][30][2], ans[max1 + 5], last;
int main ()
{
freopen("fenwick.in", "r", stdin);
freopen("fenwick.out", "w", stdout);
scanf("%d%d%d%d%d", &n, &m, &k, &A, &B);
for ( int i = 1; i <= n; i ++ )
scanf("%d", &val[i]);
val[n + 1] = 0;
sum[0] = 0;
for ( int i = 1; i <= n + 1; i ++ )
{
sum[i] = sum[i - 1];
if ( val[i] != -1 )
sum[i] ^= val[i];
}
f[n + 1][0][0] = n + 2; f[n + 1][0][1] = inf;
for ( int i = n; i >= 1; i -- )
{
if ( val[i] == -1 )
{
f[i][0][0] = i + 1;
f[i][0][1] = i + 1;
}
else
{
if ( !(val[i] & 1) )
{
f[i][0][0] = i + 1;
f[i][0][1] = f[i + 1][0][1];
}
else
{
f[i][0][0] = f[i + 1][0][1];
f[i][0][1] = i + 1;
}
}
}
for ( int u = 1; u <= k - 1; u ++ )
{
f[n + 1][u][0] = n + 2; f[n + 1][u][1] = inf;
for ( int i = n; i >= 1; i -- )
{
if ( val[i] == -1 )
{
f[i][u][0] = i + 1;
f[i][u][1] = i + 1;
}
else
{
f[i][u][0] = f[i][u][1] = inf;
int j = f[i][u - 1][0];
if ( j != inf )
{
if ( !(((sum[i - 1] ^ sum[j - 1]) >> u) & 1) )
f[i][u][0] = j;
else
f[i][u][0] = f[j][u][1];
}
j = f[i][u - 1][0];
if ( j != inf )
{
if ( !(((sum[i - 1] ^ sum[j - 1]) >> u) & 1) )
f[i][u][1] = f[j][u][1];
else
f[i][u][1] = j;
}
}
}
}
ans[n + 1] = 0;
for ( int i = n; i >= 1; i -- )
{
int u = -1;
for ( int j = k - 1; j >= 0; j -- )
if ( f[i][j][0] != inf )
{ u = j; break; }
if ( u == -1 )
ans[i] = sum[i - 1] ^ sum[n];
else
ans[i] = (((sum[i - 1] ^ sum[n]) >> (u + 1)) << (u + 1)) | (ans[f[i][u][0]] & ((1 << (u + 1)) - 1));
}
int L, x;
while ( m -- )
{
scanf("%d%d", &L, &x);
L = L ^ ((1LL * A * last + B) % n);
x = x ^ ((1LL * A * last + B) % (1 << k));
for ( int i = 0; i <= k - 1; i ++ )
{
if ( (x >> i) & 1 )
{
if ( f[L][i][1] == inf )
{
last = (x ^ (((sum[L - 1] ^ sum[n]) >> i) << i)) | (ans[L] & ((1 << i) - 1));
break;
}
x ^= ((sum[f[L][i][1] - 1] ^ sum[L - 1]) >> (i + 1)) << (i + 1);
x ^= 1 << i;
L = f[L][i][1];
}
}
if ( !x )
last = ans[L];
printf("%d\n", last);
}
return 0;
}