分数取模的应用
这是牛客寒假营第一场的A题，这是我第一次接触分数取模的题，从这里面学到了分数取模以及乘法逆元的相关知识。
我的整体思路就是定义两个数组p1和p2，其中p1中存放的是1-7个灯管亮的概率，p2中存放的是1-7个灯管不亮的概率。其中就用到了分数取模操作。其中用到了快速幂算法。接着在基于当前每个灯管亮的概率下，再去分别计算每个数字亮的概率，最后在将所有满足A + B = C的形式的 数的概率加起来就能得到最终的答案。我觉得难点主要是在分数取模这一步。
分数取模的具体解释如下：
具体代码如下：
#include <bits/stdc++.h> #define MOD 998244353 #define ll long long using namespace std; //a的b次方 ll qkm(ll a,ll b){ ll ans = 1; ll base = a; while (b){ if (b & 1){ ans = (ans * base) % MOD; } b >>= 1; base = (base * base) % MOD; } return ans; } void solve(){ ll c; cin>>c; //p1是1-7灯管亮的概率，p2是1-7灯管不良的概率 vector<ll> p1(8),p2(8); for (int i = 1;i <= 7;++i){ ll x; cin>>x; p1[i] = (x * qkm(100,MOD - 2)) % MOD; p2[i] = (1 - p1[i] + MOD) % MOD; // cout<<p1[i]<<" ! "<<p2[i]<<endl; } vector<ll> abc(10); vector<vector<ll>> num(10,vector<ll> (10));//每个数字亮的概率p num[0][1] = num[0][1] = num[0][2] = num[0][3] = num[0][5] = num[0][6] = num[0][7] = 1; num[1][3] = num[1][6] = 1; num[2][1] = num[2][3] = num[2][4] = num[2][5] = num[2][7] = 1; num[3][1] = num[3][3] = num[3][4] = num[3][6] = num[3][7] = 1; num[4][2] = num[4][3] = num[4][4] = num[4][6] = 1; num[5][1] = num[5][2] = num[5][4] = num[5][6] = num[5][7] = 1; num[6][1] = num[6][2] = num[6][4] = num[6][5] = num[6][6] = num[6][7] = 1; num[7][1] = num[7][3] = num[7][6] = 1; num[8][1] = num[8][2] = num[8][3] = num[8][4] = num[8][5] = num[8][6] = num[8][7] = 1; num[9][1] = num[9][2] = num[9][3] = num[9][4] = num[9][6] = num[9][7] = 1; for (int i = 0;i <= 9;++i){ ll ss = 1; for (int j = 1;j <= 7;++j){ if (num[i][j] == 1){ ss = (ss * p1[j]) % MOD; } else{ ss = (ss * p2[j]) % MOD; } } abc[i] = ss; } ll fz = 0; for (int i = 0;i <= c;++i){ ll sh = 1; ll g,s,b,q; g = i % 10; s = i % 100 / 10; b = i % 1000 / 100; q = i / 1000; sh = (sh * abc[g]) % MOD; sh = (sh * abc[s]) % MOD; sh = (sh * abc[b]) % MOD; sh = (sh * abc[q]) % MOD; g = (c - i) % 10; s = (c - i) % 100 / 10; b = (c - i) % 1000 / 100; q = (c - i) / 1000; sh = (sh * abc[g]) % MOD; sh = (sh * abc[s]) % MOD; sh = (sh * abc[b]) % MOD; sh = (sh * abc[q]) % MOD; if (fz == 0){ fz = sh; } else{ fz = (fz + sh) % MOD; } } cout<<fz<<endl; } int main() { int t; cin>>t; while (t--){ solve(); } return 0; }