XSY #2815 净空

题意

有$n$种不同的物品，每秒会随机产生一种，其中第$i$秒的代价是$i^k$。问收集到所有物品的期望代价和，答案模$998244353$。
$1\le n\le 100,0\le k\le 100$。

题解

显然是minmax容斥。
$ans={\sum }_{i=1}^n(?1{)}^{i+1}(\genfrac{}{}{0ex}{}{n}{i})f(\frac{i}{n},k)$。
这里$f(p,k)$表示每次试验成功概率为$p$，最早成功时间为$T$，${\sum }_{i=1}^T{i}^k$的期望。
$f(p,k)$是关于通常幂的式子，不好求，容易想到通过第二类斯特林数转成下降幂来算，具体的有$f(p,k)={\sum }_{i\ge 0}(1?p{)}^i(i+1{)}^k={\sum }_{i\ge 0}(1?p{)}^i{\sum }_{j=0}^{k}s(k,j)j!(\genfrac{}{}{0ex}{}{i+1}{j})$。
交换求和顺序有$f(p,k)={\sum }_{j=0}^{k}s(k,j)j!?g(1?p,j)$，其中$g(p,k)={\sum }_{i\ge 0}{p}^i\left(\genfrac{}{}{0ex}{}{i+1}{k}\right)$。
当$k=0$时，$g(p,0)={\sum }_{i\ge 0}{p}^i=\frac{1}{1?p}$。
当$k=1$时，$g(p,1)={\sum }_{i\ge 0}{p}^i\left(\genfrac{}{}{0ex}{}{i+1}{1}\right)=({\sum }_{i\ge 0}{p}^i?i)+p?({\sum }_{i\ge 0}{p}^i(\genfrac{}{}{0ex}{}{i+1}{1}))$，于是$g(p,1)=\frac{g(p,0)}{1?p}=\frac{1}{(1?p{)}^2}$。
当$k>1$时，$g(p,k)={\sum }_{i\ge 0}{p}^i\left(\genfrac{}{}{0ex}{}{i+1}{k}\right)={\sum }_{i\ge k?1}{p}^i\left(\genfrac{}{}{0ex}{}{i+1}{k}\right)=p?({\sum }_{i\ge k?2}{p}^i?(\genfrac{}{}{0ex}{}{i+1}{k?1}))+p?({\sum }_{i\ge k?1}{p}^i(\genfrac{}{}{0ex}{}{i+1}{k}))$，于是$g(p,k)=\frac{p?g(p,k?1)}{1?p}=\frac{p^{k?1}}{(1?p{)}^{k+1}}(k>1)$。
直接按式子计算即可，时间复杂度$O(nk)$。

#include <bits/stdc++.h>
#define MOD 998244353using namespace std;typedef long long ll;ll pow_mod(ll x,int k) {
    ll ans=1;while (k) {
    if (k&1) ans=ans*x%MOD;x=x*x%MOD;k>>=1;}return ans;
}ll C[105][105],strl[105][105],facd[105];void pre(int n) {
    for(int i=0;i<=n;i++) C[i][0]=1;for(int i=1;i<=n;i++)for(int j=1;j<=i;j++) C[i][j]=(C[i-1][j-1]+C[i-1][j])%MOD;strl[0][0]=1;for(int i=1;i<=n;i++)for(int j=1;j<=i;j++) strl[i][j]=(strl[i-1][j-1]+j*strl[i-1][j])%MOD;facd[0]=1;for(int i=1;i<=n;i++) facd[i]=facd[i-1]*i%MOD;
}int main() {
    int n,k;scanf("%d%d",&n,&k);pre(max(n,k));ll ans=0;for(int i=1;i<=n;i++) {
    ll p=i*pow_mod(n,MOD-2)%MOD,q=(1LL-p+MOD)%MOD;p=pow_mod(p,MOD-2);ll cur=p,s=0;for(int j=0;j<=k;j++) {
    s=(s+cur*strl[k][j]%MOD*facd[j])%MOD;if (j) cur=cur*p%MOD*q%MOD;else cur=cur*p%MOD;} ans=(ans+s*C[n][i]%MOD*((i&1)?1:MOD-1))%MOD;}printf("%lld\n",ans);return 0;
}

附记

这是一个水题。
为什么要为这个题写博呢？因为我闹了笑话。
今天模拟赛出了这题，然后我花了5min秒了，然后dcx也秒了。后来他找我说他觉得数据错了，我跟他对了一下100 100的输出，是一样的，于是找到zjt要求改数据。然而场上并没有其他人写了正解或是自以为正解的东西，于是就照我们的做法造了数据。
晚上被zjt找到我们，要我们测测1 1的数据，结果发现输出了0。
这是怎么回事呢？冷静推演了很久，发现我在推式子的时候把$(i+1{)}^k$当做了$i^k$来算，大体上是一样的（可以自己推推）。唯一区别是在$k=1$时，并不需要特判，也就是$g(p,k)=\frac{p^k}{(1?p{)}^{k+1}}(k>0)$。
为什么输出会撞上呢？问了问dcx，虽然我们推的式子不同，可是都把$(i+1{)}^k$当成了$i^k$。
最后发现原来的数据是对的，感觉极度尴尬。
自闭了。

扩展

稍微推导一下，发现运用等幂和其实可以做到$O(nlo{g}^{2}n)$的复杂度。代码还没有。