题解：P12057 [THUPC 2025 决赛] 好串

CityRainVeil · 2026-08-08 12:15:46 · 题解

P12057 [THUPC 2025 决赛] 好串

题目分析

题意：对于三个长度为 n 的 01 字符串 s_1,s_2,s_3，称长度为 n 的 01 字符串 t 是好的当且仅当 \forall 1 \le i,j \le n, \exists k \in \{1,2,3\}, s_{k,i} = t_i, s_{k,j} = t_j。设 f(s_1,s_2,s_3) 为这样的好的串的数量。

现给定三个长度为 n 的随机 01 字符串 s_1,s_2,s_3，其中 s_i (1 \le i \le 3) 的第 j (1 \le j \le n) 个字符有 \frac{p_{i,j}}{9} 的概率为 1，\left(1 - \frac{p_{i,j}}{9}\right) 的概率为 0，其中 p_{i,j} 是一个 0 至 9 的整数。所有的随机事件是独立的。你需要求 f(s_1,s_2,s_3) 的期望，对 M=998244353 取模。
数据范围：3 \le n \le 3 \times 10^5。

算法分析

只需求出 f(s_1,s_2,s_3) 每个取值其概率即可。
注意到 f(s_1,s_2,s_3) 的取值为 \{1,2,3,4\}，所有好串为 \{s_1,s_2,s_3,t\}，其中 t_i 为 s_{1,i},s_{2,i},s_{3,i} 出现次数最多的数，即众数，这其实也是构造方式。
得出上面结论后即可进行分类讨论：
- 假定已经处理过 p_{i,j}。
- 令所有可能的长度为 n 的 01 字符串为全集 U，s_1 的所有可能结果为 A，s_2 的所有可能结果为 B，s_3 的所有可能结果为 C。
- 绘制出 \text{Venn} 图，记 t 位于位置 i 的概率为 d_i，如图有 a,b,c,d，以及集合 A,B,C,U。
- 当 f(s_1,s_2,s_3)=1 时，t=s_1=s_2=s_3，相当于 t 位于图中位置 a，此时概率
  P_1=d_a=d_{A\cap B\cap C}
- 当 f(s_1,s_2,s_3)=2 时，t=s1=s2\neq s_3 或 t=s_1=s_3\neq s_2 或 t=s_2=s_3\neq s_1，相当于 t 位于图中所有位置 b，此时概率利用容斥原理可得
  P_2=d_b=d_b+d_a-d_a=d_{A\cap B}+d_{A\cap C}+d_{B\cap C}-3P_1
- 当 f(s_1,s_2,s_3)=3 时，t=s_1\neq s_2\neq s_3 或 t=s_2\neq s_1\neq s_3 或 t=s_3\neq s_1\neq s_2。有一个性质，以第一种举例，s_{1,i} 应与 s_{2,i} 和 s_{3,i} 至少一个相同，还要排除全相同或两个相同的情况。此时相当于 t 位于图中所有位置 c，概率同样用容斥原理可得
  \begin{aligned} P_3&=d_c=d_c+d_b+d_a-d_b-d_a\\ &=d_A+d_B+d_C-2d_{A\cap B}-2d_{A\cap C}-2d_{B\cap C}+3d_{A\cap B\cap C}\\ &=d_A+d_B+d_C-2P_2-3P_1 \end{aligned}
- 当 f(s_1,s_2,s_3)=4 时，观察发现 P_1,P_2,P_3,P_4 构成全集，则
  P_4=1-P_1-P_2-P_3
- 最终期望值
  P_1+2P_2+3P_3+4P_4
代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 3e5+10;
const int MOD = 998244353;

int n;
int p[4][N];
int P[4],w;

int ksm(int base,int pw){
    int res=1;
    while(pw){
        if(pw&1) res=res*base%MOD;
        base=base*base%MOD;
        pw>>=1;
    }
    return res%MOD;
}

int mul(int x,int y,int z){
    x=(x+MOD)%MOD;
    y=(y+MOD)%MOD;
    z=(z+MOD)%MOD;
    return (x*y%MOD)*z%MOD;
}

int A(int x,int y,int z){
    int res=1;
    for(int i=1;i<=n;++i){
        int a=p[x][i],b=p[y][i],c=p[z][i];
        res*=(mul(a,b,c)+mul(1-a,1-b,1-c));
        res%=MOD;
    }
    return res;
}

int B(int x,int y,int z){
    int res=1;
    for(int i=1;i<=n;++i){
        int a=p[x][i],b=p[y][i],c=p[z][i];
        res*=(mul(a,b,c)+mul(a,b,1-c)+mul(1-a,1-b,c)+mul(1-a,1-b,1-c))%MOD;
        res%=MOD;
    }
    return res%MOD;
}

int C(int x,int y,int z){
    int res=1;
    for(int i=1;i<=n;++i){
        int a=p[x][i],b=p[y][i],c=p[z][i];
        res*=(mul(a,b,c)+mul(a,b,1-c)+mul(a,1-b,c)
        +mul(1-a,1-b,c)+mul(1-a,b,1-c)+mul(1-a,1-b,1-c))%MOD;
        res%=MOD;
    }
    return res%MOD;
}

signed main(){
    cin>>n;
    string s;
    w=ksm(9,MOD-2);
    for(int i=1;i<=3;++i){
        cin>>s;
        for(int j=1;j<=n;++j){
            p[i][j]=(s[j-1]-'0')*w;
        }
    }
    P[1]=A(1,2,3)%MOD;
    P[2]=(B(1,2,3)+B(1,3,2)+B(2,3,1)-3*P[1]%MOD+3*MOD)%MOD;
    P[3]=(C(1,2,3)+C(2,1,3)+C(3,1,2)-2*P[2]%MOD-3*P[1]%MOD+5*MOD)%MOD;
    P[4]=(1-P[1]-P[2]-P[3]+3*MOD)%MOD;
    cout<<(P[1]+2*P[2]+3*P[3]+4*P[4])%MOD; 
    return 0;
}

注意

我们求的是模 M 意义下的概率和期望，则 p_{i,j} 应为 p_{i,j}\cdot 9^{-1}，但是当我们求该位为 0 的概率时，仍应用 1 减去，但需加上 M 保证非负。

题目位置

P12057