题解 | #A+B Problem#

A． A+B Problem题解

一. 题目理解

基本设定

1.有8个相同的气短数码管，每个数码管有7个灯管（编号1-7）

2.每个灯管有独立点亮概率p_i%

3.将这8个显示器分成2排，每排4个

4.没拍显示一个四位数（允许前导0）

5.2个四位数A和B满足：A+B=C

要求概率的时间必须同时满足：

1.每个显示器都有灯管被点亮

2.每个显示器都显示合法数字

3.第一排显示A，第二排显示B，且A+B=C

二．核心思路

1.计算单个数字 的显示概率

第i个灯管亮：p_i/100,不亮：（100-p_i）/100

2.计算四位数的显示概率

对于四位数X（千位x1，百位x2，十位x3，个位x4），4个显示器独立，所以： P(X) = prob[x₁] × prob[x₂] × prob[x₃] × prob[x₄]

3.由于C<=2026,我们可以枚举A从0到min（C,9999），B=C-A: 总概率 = Σ{A=0}^{min(C,9999)} [P(A) × P(B)]，其中B在0-9999范围内

4.模运算处理

题目要求输出概率998244353.由于概率是分数，需要用费马小定理进行分数取模： 对于分数a/b mod M: a/b mod M = a × b^{M-2} mod M 代码中提取计算了inv100 = 100^{-1} mod 998244353 = 828542813

三．示例代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
const ll mod = 998244353;
const ll inv100 = 828542813;

const vector<vector<int>> seg = {
    {1,1,1,0,1,1,1},
    {0,0,1,0,0,1,0},
    {1,0,1,1,1,0,1},
    {1,0,1,1,0,1,1},
    {0,1,1,1,0,1,0},
    {1,1,0,1,0,1,1},
    {1,1,0,1,1,1,1},
    {1,0,1,0,0,1,0},
    {1,1,1,1,1,1,1},
    {1,1,1,1,0,1,1}
};

void solve() {
    int C;
    cin >> C;
    
    vector<ll> p(8);
    for(int i = 1; i <= 7; i++) {
        int x;
        cin >> x;
        p[i] = (ll)x * inv100 % mod;
    }
    
    vector<ll> prob(10);
    for(int x = 0; x < 10; x++) {
        ll res = 1;
        for(int i = 1; i <= 7; i++) {
            if(seg[x][i-1] == 1) {
                res = res * p[i] % mod;
            } else {
                res = res * ((1 - p[i] + mod) % mod) % mod;
            }
        }
        prob[x] = res;
    }
    
    vector<ll> proa(10000, 0);
    for(int a = 0; a < 10000; a++) {
        int a1 = a / 1000;
        int a2 = (a / 100) % 10;
        int a3 = (a / 10) % 10;
        int a4 = a % 10;
        proa[a] = prob[a1] * prob[a2] % mod * prob[a3] % mod * prob[a4] % mod;
    }
    
    ll ans = 0;
    for(int A = 0; A <= min(C, 9999); A++) {
        int B = C - A;
        if(B >= 0 && B < 10000) {
            ans = (ans + proa[A] * proa[B] % mod) % mod;
        }
    }
    
    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int T;
    cin >> T;
    while(T--) {
        solve();
    }
    return 0;
}