[CTSC2018]假面

[CTSC2018]假面

题目

传送门 to UOJ

传送门 to usOJ

思路

数据范围其实真的挺小的……

对于每一个人，存储剩余血量为 i i i 的概率，总复杂度才 O ( q m ) mathcal O(qm) O(qm) 。热值乘以质量

在计算结界的时候，竟然不需要使用多项式进行乘法？为什么要用模数 998244353 998244353 998244353 骗人感情？

直接用背包，然后对于每一个人做一次退背包，本质是退去一个 ( d i e + a l i v e ⋅ x ) (die+alivecdot x) (die+alive⋅x) 的项。其中， d i e die die 表示已经死掉的概率， a l i v e alive alive 则正相反。要小心 d i e = 0 die=0 die=0 的情况！

我最开始认为这里要用 N T T NTT NTT 乱搞，没想到啊……然后就爆零了……

时间复杂度也才 O ( c n 2 log ⁡ P + q m ) mathcal O(cn^2log P+qm) O(cn2logP+qm) ，五秒七险过六秒时限。

另外：我求逆元的时候，竟然放在了循环内部……放在循环外会更快，不会那么险。

代码

#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
inline int readint(){int a = 0, f = 1; char c = getchar();for(; c<'0'||c>'9'; c=getchar())if(c == '-') f = -f;for(; '0'<=c&&c<='9'; c=getchar())a = (a<<3)+(a<<1)+(c^48);return a*f;
}
inline void writeint(long long x){if(x < 0) putchar('-'), x = -x;if(x > 9) writeint(x/10);putchar((x%10)^48);
}# define MB template < typename T >
MB void getMax(T &a,const T &b){ if(a < b) a = b; }
MB void getMin(T &a,const T &b){ if(b < a) a = b; }const int MaxN = 205, Mod = 998244353;inline int qkpow(long long base,int q=Mod-2){int ans = 1;for(; q; q>>=1,base=base*base%Mod)if(q&1) ans = ans*base%Mod;return ans;
}int dp[MaxN], inv[MaxN], n, gl[MaxN][MaxN], item[MaxN];int main(){n = readint(); inv[1] = 1;for(int i=2; i<=n; ++i)inv[i] = (0ll+Mod-Mod/i)*inv[Mod%i]%Mod;for(int i=1; i<=n; ++i)gl[i][readint()] = 1;for(int Q=readint(); Q; --Q){int opt = readint();if(opt == 0){int id = readint(), u = readint(), v = readint();u = 1ll*u*qkpow(v)%Mod; // 计算概率gl[id][0] = (1ll*gl[id][1]*u+gl[id][0])%Mod;for(int i=1; i<=MaxN-5; ++i){gl[id][i] = 1ll*gl[id][i]*(Mod+1-u)%Mod;gl[id][i] = (gl[id][i]+1ll*gl[id][i+1]*u)%Mod;}}if(opt == 1){int k = readint();for(int i=1; i<=k; ++i)dp[i] = 0;dp[0] = 1; // 无人生还for(int i=1; i<=k; ++i){const int &id = item[i] = readint();const int p = (Mod+1-gl[id][0])%Mod;for(int j=i; j; --j){dp[j] = 1ll*dp[j]*gl[id][0]%Mod;dp[j] = (1ll*dp[j-1]*p+dp[j])%Mod;}dp[0] = (1ll*dp[0]*gl[id][0])%Mod;}for(int i=1; i<=k; ++i){ // 退背包const int &id = item[i];const int p = (Mod+1-gl[id][0])%Mod;if(p == 1) for(int j=0; j<k; ++j)dp[j] = dp[j+1];else{dp[0] = 1ll*dp[0]*qkpow(gl[id][0])%Mod;for(int j=1; j<=k; ++j){dp[j] = (dp[j]-1ll*dp[j-1]*p)%Mod;if(dp[j] < 0) dp[j] += Mod;dp[j] = 1ll*dp[j]*qkpow(gl[id][0])%Mod;}}int res = 0;for(int j=0; j<k; ++j){res = (1ll*dp[j]*inv[j+1]+res)%Mod;// printf("dp[%d] = %dn",j,dp[j]);}res = 1ll*res*p%Mod;printf("%d ",res);for(int j=k; j; --j){dp[j] = 1ll*dp[j]*gl[id][0]%Mod;dp[j] = (1ll*dp[j-1]*p+dp[j])%Mod;}dp[0] = (1ll*dp[0]*gl[id][0])%Mod;}putchar('n');}}for(int i=1; i<=n; ++i){int res = 0;for(int j=1; j<=MaxN-5; ++j)res = (1ll*j*gl[i][j]+res)%Mod;printf("%d ",res);} putchar('n');return 0;
}