题解：ABC310F Make 10 Again

atcoder.jp

然而已经很久没有写题解了，天天模拟赛挂大分（摆=__=）

随机选取幸运题目，然而是dp

---

思路

首先这道题的“概率”非常扯，因为和求这个概率 $\frac{a}{b}$ 就相当于分别求一下 $a$ ，$b$ 然后相除。

分母非常好算，就是所有掷骰子的方案总和，全部乘起来即可。

分子则需要考虑 万能的 动态规划。因为我们只考虑总点数为10以内的情况，所以所有点数大于10的情况实际上是等价且不会影响结果的，而10很小，因此考虑状压。

用数组 $dp[i][s]$ 表示枚举到第 $i$ 枚骰子，状态为 $s$ 的方案数，其中 $s$ 是一个11位二进制数，分别表示点数和为0~10的情况。分别枚举每一枚骰子掷出的所有点数，进行状态转移，而如果可以掷出大于10的点数，对转移没有影响，单独加起来即可。

代码

#include<bits/stdc++.h>

using namespace std;

#define ll long long

const ll mod=998244353;

ll n;
ll a[105];
ll dp[105][(1<<11)+5];

ll den=1,num; //den:分母 num:分子

ll qpow(ll a,ll b)
{
	ll ret=1;
	while(b)
	{
		if(b&1)
		{
			ret=ret*a%mod;
		}
		a=a*a%mod;
		b>>=1;
	}
	
	return ret;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);

	cin>>n;
	for(ll i=1;i<=n;i++)
	{
		cin>>a[i];
		den=den*a[i]%mod;
	}
	
	dp[0][1]=1; //第0枚骰子投出0的方案为1
	for(ll i=1;i<=n;i++) //第i枚骰子
	{
		for(ll j=1;j<=min(10ll,a[i]);j++) //第j种情况
		{
			for(ll s=0;s<(1<<11);s++) //原来的状态为s
			{
				ll s1=s; //现在的状态为s1
				for(ll k=0;k<11;k++) //对于原来状态的第k位
				{
					if(s&(1<<k))
					{
						s1=(s1|(1<<(j+k))); //用或运算表述取不取都可以
					}
				}
				s1%=(1<<11); //点数和超出10的舍掉
				dp[i][s1]=(dp[i][s1]+dp[i-1][s])%mod; //转移
			}
		}
		if(a[i]>10) //大于10
		{
			for(ll s=0;s<(1<<11);s++) //对于每个状态都有a[i]-10种方案（不取）
			{
				dp[i][s]=(dp[i][s]+dp[i-1][s]*(a[i]-10))%mod;
			}
		}
	}
	
	for(ll i=(1<<10);i<(1<<11);i++) //所有可以掷出10的方案和
	{
		num=(num+dp[n][i])%mod;
//		cout<<num<<"\n";
	}
	
	cout<<(num*qpow(den,mod-2)%mod)<<"\n"; //如题
	
	return 0;
}

---

好啦，你A了一道蓝题喵。时间复杂度 $O(100Sn)$ 其中 $S=2^{11}$ 。