本场同 CF923。

A. Primal Sport

设 f(x,p) 是对数 x 选择小于 x 质数 p 得到的最小的 \geq x 的质数。若 f(x,p)=y，则 p 应是 y 的一个质因子，且 x\in[\min(y-p+1,p+1),y]。可以枚举合法的 x1，再选出最小的 x_2。复杂度 O(X_2)。

B. Producing Snow

用优先队列维护还没有融化的雪的体积，每天 pop 掉当天融化的雪，同时统计答案。每堆雪只会入队和出队各一次，复杂度 O(N\log N)。

C. Perfect Security

套路题。维护 01trie 支持删除操作和查询最小异或值即可。复杂度 O(30N)。

D. Picking Strings

通过观察，得到

• B\to AC\to AAB\to AAAC\to C
• C\to AB\to AAC\to AAAB\to B

因此，B 与 C 等价。下面把所有的 C 替换为 B，又有

• B\to AB
• AB\to AAB\to AAAB\to B

因此，B 与 AB 等价。把原串中的 AB 替换为 B，可以转化为 BB\cdots BAA\cdots A 的形式，任意一个 B 前可以插入任意数量的 A，串尾的 A 可以一次删掉 3 个。继续观察，可以得到

• A\to BB
• B\to AB\to BBB

可以发现，B 的个数只增不减且奇偶性不变。设原串和目标串中 B 的个数分别为 x,y，末尾 A 的个数分别为 z,w，就可以开始讨论了。

• x=y。此时不能把 A 转化成 B，串尾的 A 只能通过一次删除 3 个达到目标。仅当 z\geq w 且 z\equiv w(\mod 3) 时可行。
• x<y 且 x\equiv y(\mod 2)。此时又分两种情况：
  • 原串只包含 A。此时可以将其中一个 A 改为 BB 使得修改后的串尾的 A 的个数与目标串在模 3 意义下相等，再通过 B\to BBB 继续增加 B 的数量。这样至少会损失一个串尾的 A，因此仅当 z>w 时可行。
  • 原串不只包含 A。此时可以选择将其中一个串尾 A 改成 BB 使得修改后的串尾的 A 的个数与目标串在模 3 意义下相等，也可以选择将一个 B 改成 BBB。这样可以不损失串尾的 A，因此仅当 z\geq w 时可行。
• 其他情况均不可行。

对原串和目标串分别统计 B（和 C）的个数的前缀和，以及每个前缀的末尾最长连续 A 的长度。复杂度 O(|S|+|T|+Q)。下面是代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN=110000;
char s[MAXN], t[MAXN];
int bs[MAXN], cs[MAXN];
int bt[MAXN], ct[MAXN];
int main()
{
//  freopen("D.in", "r", stdin);
//  freopen("D.out", "w", stdout);
    int m, n, q;
    scanf("%s%s", s+1, t+1);
    m=strlen(s+1), n=strlen(t+1);
    for (int i=1; i<=m; i++)
    {
        bs[i]=bs[i-1]+(s[i]!='A');
        cs[i]=s[i]=='A'?cs[i-1]+1:0;
    }
    for (int i=1; i<=n; i++)
    {
        bt[i]=bt[i-1]+(t[i]!='A');
        ct[i]=t[i]=='A'?ct[i-1]+1:0;
    }
    scanf("%d", &q);
    while (q--)
    {
        int a, b, c, d;
        scanf("%d%d%d%d", &a, &b, &c, &d);
        int x=bs[b]-bs[a-1], y=bt[d]-bt[c-1];
        int z=min(cs[b], b-a+1), w=min(ct[d], d-c+1);
        if (x==y&&z>=w&&(z-w)%3==0
          ||x<y&&(y-x)%2==0&&(x?z>=w:z>w)) putchar('1');
        else putchar('0');
    }
    putchar('\n');
    return 0;
}

E. Perpetual Subtraction

很经典的推式子题。可以参考 GKxx 的博客，我感觉我不能比他讲得更清楚了。。

代码：

#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN=440000;
const int P=998244353;
const int G=3, GI=332748118;
int qpow(int n, int k)
{
    int r=1;
    while (k)
    {
        if (k&1) r=1ll*r*n%P;
        n=1ll*n*n%P; k>>=1;
    }
    return r;
}
int l, r[MAXN];
void getl(int n)
{
    l=1, r[0]=0; int d=0;
    while (l<=n) l<<=1, d++;
    for (int i=1; i<l; i++) r[i]=r[i>>1]>>1|(i&1)<<d-1;
}
void ntt(int* a, int ty)
{
    for (int i=0; i<l; i++)
        if (i<r[i]) swap(a[i], a[r[i]]);
    for (int k=1; k<l; k<<=1)
    {
        int wn=qpow(ty==1?G:GI, (P-1)/(k<<1));
        for (int i=0; i<l; i+=k<<1)
            for (int j=0, w=1; j<k; j++, w=1ll*w*wn%P)
            {
                int x=a[i+j], y=1ll*w*a[i+k+j]%P;
                a[i+j]=(x+y)%P; a[i+k+j]=(x-y+P)%P;
            }
    }
    if (ty==-1)
    {
        int li=qpow(l, P-2);
        for (int i=0; i<l; i++) a[i]=1ll*a[i]*li%P;
    }
}
int fac[MAXN], ifac[MAXN];
int p[MAXN], f[MAXN], g[MAXN];
int main()
{
//  freopen("E.in", "r", stdin);
//  freopen("E.out", "w", stdout);
    int n; long long m;
    scanf("%d%lld", &n, &m); m%=P-1;
    for (int i=0; i<=n; i++) scanf("%d", &p[i]);
    fac[0]=1;
    for (int i=1; i<=n; i++) fac[i]=1ll*fac[i-1]*i%P;
    ifac[n]=qpow(fac[n], P-2);
    for (int i=n; i>=1; i--) ifac[i-1]=1ll*ifac[i]*i%P;
    for (int i=0; i<=n; i++)
        f[i]=1ll*fac[n-i]*p[n-i]%P, g[i]=ifac[i];
    for (int i=n+1; i<l; i++) f[i]=g[i]=0;
    getl(2*n);
    ntt(f, 1); ntt(g, 1);
    for (int i=0; i<l; i++) f[i]=1ll*f[i]*g[i]%P;
    ntt(f, -1);
    for (int i=0; i<=n; i++)
        g[i]=1ll*f[n-i]*ifac[i]%P*qpow(qpow(i+1, m), P-2)%P;
    for (int i=0; i<=n; i++) f[i]=1ll*fac[n-i]*g[n-i]%P;
    for (int i=0; i<=n; i++) g[i]=i&1?P-ifac[i]:ifac[i];
    for (int i=n+1; i<l; i++) f[i]=g[i]=0;
    ntt(f, 1); ntt(g, 1);
    for (int i=0; i<l; i++) f[i]=1ll*f[i]*g[i]%P;
    ntt(f, -1);
    for (int i=0; i<=n; i++) printf("%d ", 1ll*f[n-i]*ifac[i]%P);
    putchar('\n');
    return 0;
}