题目描述

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

图1: 灯管编号 图2: 数字 0∼90\sim90∼9 对应的状态

\hspace{15pt}遗憾的是，放置时间太久导致所有的显示器都发生了相同的故障，具体来说，在点亮他们的编号为 iii 的灯管时，灯管都是仅有 pi%p_i\%pi​% 的概率会被点亮，而还会有 100%−pi%100\%-p_i\%100%−pi​% 的概率不会被点亮（各根灯管的点亮尝试相互独立；不同显示器之间、同一显示器内不同编号灯管之间的点亮结果均互不影响）。

\hspace{15pt}但小苯的学习还得进行下去，现在他会让小红指定一个整数 C(0≦C≦2026)\textrm{C} \left(0 \leqq \textrm{C} \leqq 2026\right)C(0≦C≦2026)，接着小苯会将其中的四个排成一排，另外四个排成另一排，并对其 777 根灯管（共 7×8=567\times 8=567×8=56 根）均各尝试一次点亮操作。（由于所有显示器参数相同，具体选哪 444 台放在第一排与第二排均等价，可视为任意固定分配）。

\hspace{15pt}现在请你计算出如下事件的概率（需全部满足）： ∙ \hspace{23pt}\bullet\,∙最终所有显示器均有灯管被点亮（也就是说显示器的灯管不能全灭）。 ∙ \hspace{23pt}\bullet\,∙最终所有显示器显示的结果均为合法数字。 ∙ \hspace{23pt}\bullet\,∙第一排的显示器前后拼接形成的四位十进制数记作 A\textrm{A}A，第二排的显示器前后拼接形成的四位十进制数记作 B\textrm{B}B 的话，满足：A+B=C\textrm{A}+\textrm{B}=\textrm{C}A+B=C。（两排显示器从左到右依次作为千位、百位、十位、个位进行拼接，可以存在前导 000）。

题解：由于每根灯管点亮概率独立，因此我们需要先求出0-9每个数各自被点亮的概率，然后才能求出两排显示器显示出a，b的概率，

首先用二进制存储点亮每个数字需要的灯管编号，1为需要0为不需要，当第i根灯管需要点亮则将当前数字点亮的概率乘上这根灯管被点亮的概率，反之则乘上他不亮的概率，在求出0-9被点亮的概率后，题目要求的a+b=c，令b=c-a，则可以让a从0-c遍历，将组成数字a的概率乘以组成数字b的概率再与总概率相加即可。对于逆元的处理我使用了快速幂与逆元的板子。注意取模带来的一些问题：（

代码：

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 998244353;
int per[10], chan[10];
int fpow(int a, int x)
{
    int _res = a % N, _ans = 1;
    while (x)
    {
        if (x & 1)_ans = _ans * _res % N;
        _res = _res * _res % N;
        x >>= 1;
    }
    return _ans;
}
int inv(int a)
{
    return fpow(a, N - 2);
}
signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    string num[20];
    num[0] = "1110111";
    num[1] = "0010010";
    num[2] = "1011101";
    num[3] = "1011011";
    num[4] = "0111010";
    num[5] = "1101011";
    num[6] = "1101111";
    num[7] = "1010010";
    num[8] = "1111111";
    num[9] = "1111011";
    int T = 1; cin >> T;
    while (T--)
    {
        for (int i = 0; i < 10; i++)
        {
            chan[i] = 1;
        }
        int c; cin >> c;
        for (int i = 0; i < 7; i++)
        {
            cin >> per[i];
            per[i] =per[i]* inv(100) % N;
            for (int j = 0; j < 10; j++)
            {
                if (num[j][i] == '1')chan[j] *= per[i];
                else chan[j] *= (1+N - per[i]);
                chan[j] %= N;
            }
        }
        int chc = 0;
        for (int i = 0; i <= c; i++)
        {
            int a = i;
            int b = c - i; int cha = 1;
            for (int j = 0; j < 4; j++)
            {
                cha *= chan[a % 10] % N;
                cha *= chan[b % 10] % N;
                a /= 10, b /= 10;
            }
            chc += cha % N;
            chc %= N;
        }
        cout << chc << endl;
    }
    return 0;
}

题目描述

\hspace{15pt}小红在黑板上写了一个计算式，具体来讲是 nnn 个数字 a1,a2,…,ana_1,a_2,\dots,a_na1,a2,…,an，其中间由 n−1n-1n−1 个加号（‘+’\texttt{+'}‘+’）连接组成：a1+a2+⋯+ana_1+a_2+\cdots+a_na1+a2+⋯+an。 \hspace{15pt}现在小苯想去擦去黑板上的一些 ‘+’\texttt{+'}‘+’ 运算符，但他擦得很不干净，只擦去了加号中的横线（‘-’\texttt{-'}‘-’），剩下的部分就是一个竖线（‘|’\texttt{|'}‘|’）了。巧合的是，∣|∣ 恰好也是一个运算符：按位或 or\rm oror。 \hspace{15pt}小苯想知道，有多少种不同的擦黑板方式，能使得按照新算式进行计算，结果和擦黑板前的算式计算结果相同，请你帮他算一算。注意，不擦黑板也是一种方案。由于答案可能很大，请将答案对 998 244 353998\,244\,353998244353 取模后输出。

【注】 \hspace{15pt}特别的，**在本题中我们认为 or\rm oror 运算符的优先级大于加法运算 ‘+’\texttt{+'}‘+’**。 \hspace{15pt}两种擦黑板方式不同当且仅当存在至少一个运算符位置，其在其中一个方式中为 ‘+’\texttt{+'}‘+’，而在另一个方式中为 ‘|’\texttt{`|'}‘|’（即按位或 or\rm oror）。

题解：由于或运算只会使a|b<=a+b，因此i+1以前的位置的状态不会影响i+1，考虑dp，从a|b=a+b的前提为a&b=0入手，从i向前寻找一段最长的区间使得区间内所有数|的值与+相等，更新i的方案数为从区间左端点的方案数到区间右端点的方案数之和，为了降低时间复杂度可以使用前缀和进行维护，ai为0时跳过，由于一遍遍用i--的方式去找区间左端点太费时间，因此我们需要在输入时存储每一个数字的上一个非0数的位置来降低时间复杂度；

代码：#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 998244353;
signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T = 1; cin >> T;
    while (T--)
    {
        int n,now=0; cin >> n;
        vector<int> arr(n+5),dad(n+5),dp(n + 5), sum(n + 5);
        dp[1] = 1, sum[1] = 1;
        for (int i = 1; i <= n; i++)
        {
            cin >> arr[i];
            dad[i]=now;
            if(arr[i]!=0)
            {
                now=i;
            }
            int j = i;
            int wor = 0;
            for (j; (j > 0) && ((wor & arr[j]) == 0);)
            {
                wor |= arr[j];
                j=dad[j];
            }
            dp[i+1] = (sum[i] - sum[j]+N) % N;
                sum[i+1] = (sum[i] + dp[i+1]) % N;
        }
        cout << dp[n+1] << endl;
    }
    return 0;
}