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)代码