• 白王正在挑选容器。

P6046 纯粹容器

#### 题解 ❓

$g[i][j]$ 为第$i$个容器前$j$轮被击倒的概率，$f[i][j]$ 为第$i$个容器第$j$轮被击倒的概率

$g[i][j] = clca(i - l[i] ,j) + clca(r[i] - i, j) - clca(r[i] - l[i] , j)$

$clca(i,j) = A_j^i \cdot (n−1−i)! / (n−1)!$

#### 代码

const double eps = 1e-8;
const int mod = 998244353;
const int N = 5e5+10;
ll a[N],l[N],r[N];
ll fac[N],inv[N],Finv[N];
struct
{
void init()
{
fac[0] = 1ll, Finv[0]=1ll,inv[1]=1ll;
for(int i=2;i<N;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod;
for(int i=1;i<N;i++)
{
fac[i]=fac[i-1]*i%mod;
Finv[i]=Finv[i-1]*inv[i]%mod;
}
}
ll C(ll n,ll m)
{
if(n<0||m<0||m>n) return 0;
if(n == m || m == 0) return 1;
return fac[n] * Finv[m] %mod * Finv[n-m] %mod;
}
ll A(ll n,ll m)
{
return fac[n] * Finv[n-m] % mod;
}
}O_O;
ll dp[55][55],n;
ll calc(ll x,ll y) // 前y个中选x个
{
if(x > y) return 0;
return fac[y] * Finv[y - x] % mod * fac[n-1-x] %mod * Finv[n-1] % mod;
}
int main()
{
//    __IN;__OUT;
O_O.init();
RLL(n);
FOR(i,1,n) RLL(a[i]);
FOR(i,1,n)
{
_FOR(j,i-1,1) if( a[j] > a[i] ) { l[i] = j;break;}
FOR(j,i+1,n) if( a[j] > a[i] ) { r[i] = j;break;}
}
FOR(i,1,n)
{
FOR(j, 1, n - 1) {
ll a = 0, b = 0;
if (l[i])a = calc(i - l[i], j);
if (r[i])b = calc(r[i] - i, j);
if (l[i] && r[i]) dp[i][j] = (a + b - calc(r[i] - l[i], j)  % mod + mod )%mod;
else dp[i][j] = a + b;
}
}

FOR(i,1,n)
{
if(!l[i] && !r[i]) PLP(n-1);
else
{
ll now = 0;
FOR(j, 1, n-1)
{
now += (dp[i][j] - dp[i][j - 1]) % mod * (j - 1) % mod;
now %= mod;
}
now += mod;
now %= mod;
PLP(now);
}
}
return 0;
}