T21:Make 10 Again

1）题目意思

有 N 个骰子，第 i 个骰子掷出后会等概率得到 1..Ai 的一个整数。

掷完 N 个骰子后，你可以从这 N 个点数里选择若干个（至少 1 个也可以全选），问是否存在一种选择方式，使得选中的点数之和恰好等于 10。

要求输出：

“满足存在某个子集和等于 10”的概率，对 998244353 取模后的结果（按题目给的模意义输出）。

---

2）思路解析（状态压缩 DP：记录“能凑出哪些和”）

关键观察 1：只关心 0..10

我们只需要判断是否能凑出和为 10，所以只关心“当前能凑出哪些和（0 到 10）”。

用一个 11 位二进制掩码 mask 表示可达的子集和：

• 若 mask 的第 s 位为 1，表示能凑出和 s
• 初始时空集合可达：mask = 1<<0

如果当前骰子点数是 v，那么更新规则就是经典子集和：

• 新可达 = 旧可达 或者（旧可达整体左移 v 位，表示加上 v）
• 只保留 0..10 的位

也就是：

• nmask = mask | ((mask << v) & FULLMASK)

其中 FULLMASK = (1<<11)-1

关键观察 2：点数大于 10 的情况都等价

如果骰子掷出 v > 10，那么 mask<<v 的有效位（0..10）全都会被移出范围，对 0..10 没有任何贡献。

所以：

• v > 10 时，这个骰子对状态没有影响，相当于 “nmask = mask”。

因此每个骰子只需要考虑：

• v=1..min(10,Ai) 各 1 种结果
• “大于 10” 这一类合并成一类

DP 定义

• dp[mask]：处理完当前若干个骰子后，达到状态 mask 的概率（用模数表示）

每个骰子 i 的转移：

• 对 v=1..min(10,Ai)：概率都是 1/Ai
• 对 v>10：概率是 (Ai-10)/Ai（若 Ai<=10 则为 0）

最后答案是所有 mask 中 第 10 位为 1 的概率之和。

复杂度：

• 状态数 2^11 = 2048
• 每个骰子最多枚举 10 个 v
• 总复杂度约 N * 2048 * 10，N<=1000 完全可过。

---

3）代码

#include <bits/stdc++.h>
using namespace std;

const long long MOD=998244353;                          // 题目给定模数
const int S=10;                                         // 目标和为10
const int B=11;                                         // 需要记录0..10共11个和
const int FULLMASK=(1<<B)-1;                            // 11位全1的掩码，用于截断

long long qpow(long long a,long long e){                // 快速幂计算 a^e % MOD
    long long r=1;                                      // r为答案累乘
    while(e){                                           // 只要指数还没变成0
        if(e&1)r=r*a%MOD;                               // 若当前位为1则乘上a
        a=a*a%MOD;                                      // a自乘
        e>>=1;                                          // 指数右移一位
    }
    return r;                                           // 返回结果
}

int main(){                                             // 主函数入口
    ios::sync_with_stdio(false);                        // 加速输入输出
    cin.tie(nullptr);                                   // 加速输入输出

    int N;                                              // 骰子数量
    cin>>N;                                             // 读入N

    static long long dp[1<<B];                          // dp[mask]表示当前概率
    static long long ndp[1<<B];                         // ndp[mask]表示下一步概率

    for(int mask=0;mask<(1<<B);mask++)dp[mask]=0;       // 初始化dp数组为0
    dp[1<<0]=1;                                         // 初始只有和0可达（空集合）

    for(int i=1;i<=N;i++){                              // 依次处理每个骰子
        long long A;                                    // 当前骰子的面数Ai
        cin>>A;                                         // 读入Ai

        long long invA=qpow(A%MOD,MOD-2);               // invA为Ai在模MOD下的逆元
        int lim=(A<S? (int)A : S);                      // lim=min(10,Ai)
        long long psmall=invA;                          // 点数为1..lim的每个值概率都是1/Ai
        long long pbig=0;                               // 点数>10的合并概率
        if(A>S){                                        // 若Ai>10才存在大点数
            pbig=((A-S)%MOD)*invA%MOD;                  // pbig=(Ai-10)/Ai 取模
        }

        for(int mask=0;mask<(1<<B);mask++)ndp[mask]=0;  // 清空ndp

        for(int mask=0;mask<(1<<B);mask++){             // 枚举当前所有状态
            long long cur=dp[mask];                     // 取出当前状态概率
            if(cur==0)continue;                         // 概率为0就跳过

            if(pbig!=0){                                // 若存在v>10的情况
                ndp[mask]=(ndp[mask]+cur*pbig)%MOD;     // v>10时状态不变，累加到自身
            }

            for(int v=1;v<=lim;v++){                    // 枚举v=1..lim
                int shifted=(mask<<v)&FULLMASK;         // 把所有可达和整体+v，并截断到0..10
                int nmask=mask|shifted;                 // 新状态：原来能达 + 加v能达
                ndp[nmask]=(ndp[nmask]+cur*psmall)%MOD; // 按概率1/Ai累加
            }
        }

        for(int mask=0;mask<(1<<B);mask++)dp[mask]=ndp[mask]; // 把ndp拷回dp
    }

    long long ans=0;                                     // 最终答案
    for(int mask=0;mask<(1<<B);mask++){                  // 枚举所有终态
        if(mask&(1<<S)){                                 // 若能凑出和10
            ans=(ans+dp[mask])%MOD;                      // 累加其概率
        }
    }

    cout<<ans<<endl;                                     // 输出答案
    return 0;                                            // 程序结束
}