A-A+B Problem
https://ac.nowcoder.com/acm/contest/120561/A
题意：小苯有 8 个故障的七段数码管（每段亮灯概率为 pi%），需完成： 把 8 个数码管分成两组各 4 个，分别组成四位数 A、B； 要求： 每个数码管至少亮一段； 每个数码管显示合法数字（0-9）； A+B=C（C 是指定数，0≤C≤2026）。 求满足所有条件的概率（结果用数模表示）。
这题整个思路不难就是先算出0~9的概率，再直接暴力算出能满足的A和B的数字，把这个数字拆分成四位，然后算A和B的概率，再把所有可能相加。难点就是要把pi百分数转换成真实的概率再%mod，就需要用逆元(p/100)%mod=(p*100的mod-2次幂)%mod，计算幂值就用快速幂
using namespace std;
//#define int long long
const long long mod=998244353;
#define endl '\n'
long long ksm(long long x,long long y)//快速幂
{
long long ans=1;
while(y)
{
if(y&1)
{
ans=ans*x%mod;
}
x=x*x%mod;
y>>=1;
}
return ans;
}
signed main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t;
cin>>t;
for(int i=0;i<t;i++)
{
int c;
cin>>c;
vector<long long>p(8);
for(int j=1;j<=7;j++)
{
cin>>p[j];
}
for(int j=1;j<=7;j++)
{
p[j]=p[j]*ksm(100,mod-2)%mod;
}
vector<long long>pi(10);
pi[0]=p[1]*p[2]%mod;
pi[0]=pi[0]*p[3]%mod;
pi[0]=pi[0]*p[5]%mod;
pi[0]=pi[0]*p[7]%mod;
pi[0]=pi[0]*p[6]%mod;
pi[0] = pi[0] * ((1 - p[4] + mod) % mod) % mod;//计算0~9出现概率，分布算保证不溢出
pi[1]=p[3]*p[6]%mod;
pi[1]=pi[1]*((1-p[1]+mod)%mod)%mod;
pi[1]=pi[1]*((1-p[2]+mod)%mod)%mod;
pi[1]=pi[1]*((1-p[4]+mod)%mod)%mod;
pi[1]=pi[1]*((1-p[5]+mod)%mod)%mod;
pi[1]=pi[1]*((1-p[7]+mod)%mod)%mod;
pi[2] = p[1] * ((1 - p[2] + mod) % mod) % mod;
pi[2] = pi[2] * p[3] % mod;
pi[2] = pi[2] * p[4] % mod;
pi[2] = pi[2] * p[5] % mod;
pi[2] = pi[2] * ((1 - p[6] + mod) % mod) % mod;
pi[2] = pi[2] * p[7] % mod;
pi[3] = p[1] * ((1 - p[2] + mod) % mod) % mod;
pi[3] = pi[3] * p[3] % mod;
pi[3] = pi[3] * p[4] % mod;
pi[3] = pi[3] * ((1 - p[5] + mod) % mod) % mod;
pi[3] = pi[3] * p[6] % mod;
pi[3] = pi[3] * p[7] % mod;
pi[4] = ((1 - p[1] + mod) % mod) * p[2] % mod;
pi[4] = pi[4] * p[3] % mod;
pi[4] = pi[4] * p[4] % mod;
pi[4] = pi[4] * ((1 - p[5] + mod) % mod) % mod;
pi[4] = pi[4] * p[6] % mod;
pi[4] = pi[4] * ((1 - p[7] + mod) % mod) % mod;
pi[5] = p[1] * p[2] % mod;
pi[5] = pi[5] * ((1 - p[3] + mod) % mod) % mod;
pi[5] = pi[5] * p[4] % mod;
pi[5] = pi[5] * ((1 - p[5] + mod) % mod) % mod;
pi[5] = pi[5] * p[6] % mod;
pi[5] = pi[5] * p[7] % mod;
pi[6] = p[1] * p[2] % mod;
pi[6] = pi[6] * ((1 - p[3] + mod) % mod) % mod;
pi[6] = pi[6] * p[4] % mod;
pi[6] = pi[6] * p[5] % mod;
pi[6] = pi[6] * p[6] % mod;
pi[6] = pi[6] * p[7] % mod;
pi[7] = p[1] * ((1 - p[2] + mod) % mod) % mod;
pi[7] = pi[7] * p[3] % mod;
pi[7] = pi[7] * ((1 - p[4] + mod) % mod) % mod;
pi[7] = pi[7] * ((1 - p[5] + mod) % mod) % mod;
pi[7] = pi[7] * p[6] % mod;
pi[7] = pi[7] * ((1 - p[7] + mod) % mod) % mod;
pi[8] = p[1] * p[2] % mod;
pi[8] = pi[8] * p[3] % mod;
pi[8] = pi[8] * p[4] % mod;
pi[8] = pi[8] * p[5] % mod;
pi[8] = pi[8] * p[6] % mod;
pi[8] = pi[8] * p[7] % mod;
pi[9] = p[1] * p[2] % mod;
pi[9] = pi[9] * p[3] % mod;
pi[9] = pi[9] * p[4] % mod;
pi[9] = pi[9] * ((1 - p[5] + mod) % mod) % mod;
pi[9] = pi[9] * p[6] % mod;
pi[9] = pi[9] * p[7] % mod;
long long ans=0;
for(int j=0;j<=c;j++)//枚举可能取值
{
int g=j%10;//拆分成四位
int s=j/10%10;
int b=j/100%10;
int q=j/1000;
int m=c-j;
if(m < 0) continue;
int g1=m%10;
int s1=m/10%10;
int b1=m/100%10;
int q1=m/1000;
long long probA = pi[q] * pi[b] % mod;//计算数A对应的概率
probA = probA * pi[s] % mod;
probA = probA * pi[g] % mod;
long long probB = pi[q1] * pi[b1] % mod;//算B对应概率
probB = probB * pi[s1] % mod;
probB = probB * pi[g1] % mod;
ans=(ans+probA*probB%mod)%mod;//A和B概率相乘再把所有可能情况相加
}
cout<<ans<<endl;
}
return 0;
}
代码写的有点复杂，分布保证不溢出
G-Digital Folding
https://ac.nowcoder.com/acm/contest/120561/G
题意：就是给定L,R区间，让你求这个区间里面的数翻转后最大 要求翻转的数最大，就要尽量让低位是9并且挨近R，思路是L如果和R位数相同，那就直接比较他们第一位不同的位置，将这个变为R上的数字减1，后面的变为9，前面的数照抄；如果位数不同，那就直接缩小范围（比如让L变为与R位数相同的最小值再比较），特殊要判断的是L等于R就直接翻转
using namespace std;
#define endl '\n'
string re(string s)
{
int x=0;
while(x<s.size()&&s[x]=='0')
{
x++;
}
return x==s.size() ? "0" : s.substr(x);
}
signed main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t;
cin>>t;
while(t--)
{
string L, R;
cin >> L >> R;
int n = R.size();
// 特殊处理 R 是 1000...0 的情况
string tr(n, '0');
tr[0] = '1';
if(R == tr)
{
if(L == R)//如果L和R都是100..0时，翻转为1
{
cout << 1 << endl;
}
else
{
cout << string(n-1, '9') << endl;//不是直接r-1
}
continue;
}
//保证 L 和 R 位数相同（让构造出来的位数尽可能大），把L变成与R位数相同最小的数，因为L位数比R小，肯定存在
if(L.size() < R.size())
{
L = string(n, '0');
L[0] = '1';
//L.back() = '1';
}
// 找到第一个 L[i] != R[i] 的位置 k
int k = -1;
for(int i = 0; i < n; i++)
{
if(L[i] != R[i])
{
k = i;
break;
}
}
string ans;
if(k == -1)//L==R相同就直接翻转
{
ans = L;
while(ans.size() > 1 && ans.back() == '0')
{
ans.pop_back();
}
reverse(ans.begin(), ans.end());
}
else//直接构造折叠数
{
bool ok = true;
for(int i = k + 1; i < n; i++)
{
ans += '9';//将第一个不同的位置后面的数变为9，如果R后面也都是9，R就是最大的，如果不是就把不同位上的数减1
ok &= (R[i] == '9');
}
ans += (R[k] - !ok);
for(int i = k - 1; i >= 0; i--)
{
ans += L[i];//将前面相同的部分添加到后面
}
}
cout << ans << endl;
}
return 0;
}
京公网安备 11010502036488号