AGC050D
grass8cow
·
·
题解
一年前觉得不太可做的题。
我们要算什么？每个人能拿物品的概率，所以 dp 的状态值肯定是某种概率。
事实上，如果一个人领到了物品，我们直接当成把他删掉，显然不影响答案。
考虑没有领到的物品的人，令当前是第 x 轮，显然他试过 x-1 个物品，那么就是在 k-(x-1) 个物品里随机选。
我们令现在剩下 m 个人，那么就只有 k-m 个物品是未选的，当前这个人能领到物品的概率就是 (k-m)/(k-x+1) 。
我们就针对一个人能选到的概率设计 dp ：
转移简单，复杂度 $O(n^4)$ 。
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,m,inv[60];
const int mod=998244353;
int dp[50][50][50][50];
int dfs(int x,int y,int z,int w){
if(dp[x][y][z][w]!=-1)return dp[x][y][z][w];
if(w>m||n-(x+y+1)>=m)return 0;
int I=inv[m-w+1],p=1ll*(m-n+x+y+1)*I%mod;
int as;
if(z==x+1)
as=(p+1ll*(1-p)*(y?dfs(x,y,z+1,w):dfs(x,y,1,w+1))%mod)%mod;
else if(z<=x)as=(1ll*p*dfs(x-1,y,z,w)%mod+1ll*(1-p)*dfs(x,y,z+1,w)%mod)%mod;
else{
if(z==x+y+1)as=(1ll*p*dfs(x,y-1,1,w+1)%mod+1ll*(1-p)*dfs(x,y,1,w+1)%mod)%mod;
else as=(1ll*p*dfs(x,y-1,z,w)%mod+1ll*(1-p)*dfs(x,y,z+1,w)%mod)%mod;
}
return dp[x][y][z][w]=(as+mod)%mod;
}
int main(){
inv[1]=1;
for(int i=2;i<=55;i++)inv[i]=mod-1ll*(mod/i)*inv[mod%i]%mod;
cin>>n>>m;
memset(dp,-1,sizeof(dp));
for(int i=1;i<=n;i++)
printf("%d\n",dfs(i-1,n-i,1,1));
return 0;
}
```