对不起~ 萌新选手第一次搬题, 出了好大的锅555

把题解搞过来了:

1

第 $x$ 条鱼的答案 =$\sum_{mx=1}^4\sum_{cx=1}^4w_{i,j}*p(x,mx,cx)$

其中 $p(x,mx,cx)$ 表示第 x 条鲳鱼被 第$cx$ 个神佬打死，且$cnt_{mx}>\lfloor \frac {n}{2} \rfloor$的概率

为了计算$p(x,mx,cx)$,我们需要定义一个$f(x,mx,cnt)$表示除了 x 以外的鱼中恰好有 $cnt$ 条鱼被第 $ mx $ 个神佬打死的概率

$p(x,mx,cx)$= $p_{x,cx}$*$\sum_{cnt=\lfloor \frac {n}{2} \rfloor}^nf(x,mx,cnt)$ $cx==mx$

​ $p_{x,cx}$*$\sum_{cnt=\lfloor \frac {n}{2} \rfloor+1}^nf(x,mx,cnt)$ $cx\not=mx$

下面考虑如何计算 $f(x,mx,cnt)$

​ 对于一个给定的 $ mx$ ，现在的问题相当于，第 $i$ 条鲳鱼有 $p_i $的概率被(第$mx$个神佬打死)，有 $1-p_i$ 的概率不被(第$mx$个神佬打死)，对 $x=1...n$，求除了第 $x$ 条鲳鱼以外恰好有 $cnt $ 条被神佬$mx$打死的概率。

​ 首先我们可以对每一条鱼做一遍dp

​ 枚举除了 $x$ 以外的每条鱼， $dp_{cnt}$ 表示当前集合(即所有已经枚举过的人)恰好杀 $cnt$ 条鱼的概率，假设新加进来的鱼有$p$的概率选，考虑如何更新$dp$数组

​ 令原来的数组为 $dp0$ ，加入这条鱼后的数组为 $dp'$ ，则

$dp'_{cnt}$= $p*dp0_{cnt-1}+(1-p)*dp0_{cnt}$ $cnt>=1$

​ $(1-p)*dp0_{cnt}$ $cnt==0$

​ 因为有 $p$ 的概率多杀了一条鱼，有$1-p$ 的概率不变。

​ 这样时间复杂度是 $O(n^3) $的，期望得分55。

​ 注意到我们不仅支持向集合中加入一条鱼后$O(n)$维护$dp$数组，还支持删除一条鱼后$O(n)$维护$dp$数组。

​ 也就是说，给定 $dp' $和$ p$ ，可以推 $dp0$ 。(注意p=1的情况需要特判)

$dp0_{cnt}$= $\frac {dp'_{cnt}}{1-p}$ $cnt==0$

​ $\frac {dp'_{cnt}-p*dp0_{cnt-1}}{1-p}$ $cnt>=1$

​ 所以先 $O(n^2)$ 求出全集的 $dp$ 数组，然后对每个 $x$ ，$O(n)$ 求出不含$ x$ 的 $dp$ 数组即可，期望得分100。

2

​ 对于一个神佬，$dp$ 求出 $pre_{i,j} $表示前 $i $ 条鱼恰杀 $j$ 条鱼的概率，$ suf_{i,j}$ 表示后 $i$ 条鱼恰杀 $j$ 条鱼的概率。 ​ 考虑求除第 $i$ 条鱼外杀 $>= j $ 条鱼的概率，只需对 $pre$ 求个后缀和，然后枚举即可，复杂度 $O(n^2)$

下面给出标程：

#include<bits/stdc++.h>
#define LL long long
#define clr(x,y) memset(x,y,sizeof(x))
#define FOR(x,l,r) for(int x=l,x##_=r;x<=x##_;x++)
#define FR(x,l,r) for(int x=l,x##_=r;x<x##_;x++)
#define DOR(x,r,l) for(int x=r,x##_=l;x>=x##_;x--)
using namespace std;
const int N=2005;
const int P=998244353;
int n,pos[N][4],A[4][4],dp[N][N],sum[N][N],ans[N];
inline void Add(int &x,int y) {
    x+=y;
    if(x>=P)x-=P;
}
int main() {
    freopen("revolution.in","r",stdin);
    freopen("revolution.out","w",stdout);
    scanf("%d",&n);
    FOR(i,1,n)FOR(j,0,3)scanf("%d",&pos[i][j]);
    FOR(i,0,3)FOR(j,0,3)scanf("%d",&A[i][j]);
    dp[0][0]=sum[n+1][0]=1;
    FOR(id,0,3) {
        FOR(i,1,n)FOR(j,0,i){
            dp[i][j]=(LL)dp[i-1][j]*(P+1-pos[i][id])%P;
            if(j)Add(dp[i][j],(LL)pos[i][id]*dp[i-1][j-1]%P);
        }
        DOR(i,n,1)FOR(j,0,n-i+1){
            sum[i][j]=(LL)sum[i+1][j]*(P+1-pos[i][id])%P;
            if(j)Add(sum[i][j],(LL)pos[i][id]*sum[i+1][j-1]%P);
        }
        FOR(i,1,n)DOR(j,n-i,0)Add(sum[i][j],sum[i][j+1]);
        FOR(i,1,n)FOR(j,0,i-1)FOR(k,0,3)Add(ans[i],(LL)dp[i-1][j]*pos[i][k]%P*A[id][k]%P*sum[i+1][max(0,n/2+1-j-(id==k))]%P);
    }
    FOR(i,1,n)printf("%d\n",ans[i]);
    return 0;
}