题目描述

链接：https://ac.nowcoder.com/acm/contest/120561/A 来源：牛客网

小苯正在学习 A+B Problem，为此他从家中翻出了恰好八个"七段码数位显示器"（以下简称显示器）。

如下图所示，显示器共有 7 个灯管，图中已标明编号。点亮其中的一些灯管就可以形成合法的数字， 0 − 9的对应的点亮结果如下图二，其中红色灯管是被点亮的，灰色则是未被点亮（其余的结果均是不合法的数字）。

遗憾的是，放置时间太久导致所有的显示器都发生了相同的故障，具体来说，在点亮他们的编号为 i 的灯管时，灯管都是仅有 𝑝 𝑖 % 的概率会被点亮，而还会有 100 % − 𝑝 𝑖 % 的概率不会被点亮（各根灯管的点亮尝试相互独立；不同显示器之间、同一显示器内不同编号灯管之间的点亮结果均互不影响）。 但小苯的学习还得进行下去，现在他会让小红指定一个整数 C ( 0 ≦ C ≦ 2026 )，接着小苯会将其中的四个排成一排，另外四个排成另一排，并对其 7 根灯管（共 7 × 8等于 56）均各尝试一次点亮操作。（由于所有显示器参数相同，具体选哪 4 台放在第一排与第二排均等价，可视为任意固定分配）。

现在请你计算出如下事件的概率（需全部满足）：   最终所有显示器均有灯管被点亮（也就是说显示器的灯管不能全灭）。 最终所有显示器显示的结果均为合法数字。

  第一排的显示器前后拼接形成的四位十进制数记作 A，第二排的显示器前后拼接形成的四位十进制数记作 B 的话，满足： A + B 等于 C（两排显示器从左到右依次作为千位、百位、十位、个位进行拼接，可以存在前导 0 ）。

题解如下：

首先存储每一根灯管点亮的概率，而计算每一个数字被表达出来的概率，可以通过状态压缩，更方便计算，计算每个数字被表现出来的概率时，应注意，比如0，要计算123567灯管点亮的概率乘上4灯管点不亮的概率，同时在过程中通过逆元的方式取模避免溢出。之后暴力扫一遍A+B=C的可能情况，过程同样需要取模，最后将每一对A+B=C的概率相加并取模可得最后答案。 下附代码：

using namespace std;
typedef long long int ll;
ll ksm(ll x, ll y) {
	ll res = 1;
	while (y) {
		if(y & 1) res = res * x % mod;
		y >>= 1;
		x = x * x % mod;
	}
	return res;
}
ll inv(ll x) {
	return ksm(x, mod - 2);
}
void G(vector<ll>&num,vector<ll>&vt)
{
	ll inv100=inv(100);
	ll bb[10]={1110111,100100,1011101,1101101,101110,1101011,1111011,100101,1111111,1101111};
	for(ll i=0;i<10;i++)//注意存储0~9状态时，如果用整型存储不要用0开头否则会被识别成8进制，警示后人
	{
		ll digit=bb[i];
		for(ll j=0;j<7;j++)
		{
			if(digit%10==1)
				vt[i]=vt[i]*(num[j]*inv100%mod)%mod;
			else vt[i]=vt[i]*((100-num[j])*inv100%mod)%mod;
			digit/=10;                                                                                                                                
		}
//		cout<<vt[i]<<endl;
	}
}
void solve()
{
	ll C,ans=0;
	cin>>C;
	vector<ll>num(7);
	vector<ll>vt(10,1);
	for(ll i=0;i<7;i++)
		cin>>num[i];
	G(num,vt);
	for(ll i=0;i<=C;i++)
	{
		ll nub1=i,nub2=C-i,prob=1;
		for(ll k=0;k<4;k++)
		{
			prob=prob*vt[nub1%10]%mod;
			prob=prob*vt[nub2%10]%mod;
			nub1/=10;
			nub2/=10;
		}
		ans=(ans+prob)%mod;
	}
	cout<<ans<<endl;
}

如有错误烦请指正谢谢