ABC310F Make 10 Again 题解

Coffee_zzz · 2023-07-16 10:53:37 · 题解

分析

看到求概率，想到概率 dp。

为了方便，我们令以下运算都在模 998244353 的意义下进行，同时令二进制数的最低位为第 0 位。

我们先求这个概率的分母。第 i 个骰子正面朝上的可能是 1\sim a_i，共有 a_i 中可能，所以这个概率的分母为 a_1 \times a_2 \times a_3 \times \cdots \times a_N，即 \prod\limits_{i=1}^N a_i。我们令其等于 den。

接下来我们求这个概率的分子。我们可以把“是否可以凑出 0,1,2\cdots,10” 都压进状态里，进行状压 dp。其中，对于状态 S，如果它在二进制表示下第 i 位为 0 则表示不能凑出 i，反之则表示可以凑出 i。容易发现有 0 \sim 2^{11}-1 共 2^{11} 种状态。为了方便表示，我们令 K=2^{11}。

• 状态定义：定义 dp 数组 dp_{i,S} 表示枚举到了第 i 个骰子且此时的状态为 S 的方案数。

• 初始状态：当什么还没有枚举时，骰子正面朝上的数的和就为 0，能够凑出的只有 0，所以它的状态在二进制表示下只有第 0 位为 1，可以得到状态为 1。所以 dp_{0,1}=1。

• 状态转移：

  • 我们从 1 到 N 枚举骰子 i，然后从 1 到 a_i 枚举点数 j，再从 0 到 K-1 枚举每一个转移来的状态 k，计算转移后的状态 s。

  • 如果 k 在二进制表示下第 p 位为 1，则根据状态定义可以知道，s 在二进制表示下的第 p 位和第 p+j 位需要为 1。由于我们只需要记录状态在二进制表示下的前 11 位，所以我们要将 s 对 K 取模。此时的 s 即转移后的状态。

  • 我们将 dp_{i,s} 增加 dp_{i-1,k}。这样做的总复杂度是 O(N\times a_i \times K \times D)，其中 D=11，无法接受，考虑优化。

  • 注意到我们只需要记录 s 的前 11 位，所以当 j 大于 10 时，无论什么状态，转移后的状态一定和转移前相同，所以可以一起处理。现在的复杂度为 O(N \times K \times D^2)，其中 D=11，可以接受。

• 最终答案：如果骰子的点数可以凑出 10，即状态在二进制表示下的第 10 位为 1，就都需要计入分子中，设分子为 num，则 num=dp_{N,K/2}+dp_{N,K/2+1}+\cdots+dp_{N,K-1}，即 \sum\limits^{K-1}_{S=K/2} dp_{N,S}。

输出 num\times den^{-1} 即可。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod=998244353,N=105,P=12,K=2048;
int ksm(int a,int b){
    int res=1;
    while(b){
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
int dp[N][1<<P],n,a[N],pro=1;
signed main(){
    int s;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i],pro=pro*a[i]%mod;
    dp[0][1]=1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=min(11ll,a[i]);j++){
            for(int k=0;k<K;k++){
                s=k;
                for(int p=0;p<=10;p++) if(k>>p&1) s=s|1<<(j+p);
                s=s%K;
                dp[i][s]=(dp[i][s]+dp[i-1][k])%mod;
            }
        }
        if(a[i]>10) for(int k=0;k<K;k++) dp[i][k]=(dp[i][k]+dp[i-1][k]*(a[i]-11))%mod;
    }
    int ans=0;
    for(int k=K/2;k<K;k++){
        ans=ans+dp[n][k];
        ans%=mod;
    }
    cout<<(ans*ksm(pro,mod-2))%mod;
    return 0;
}