題意

題目鏈接

分析

• 直接背包之后可以 \(O(n)\) 去除一個物品的影響。

• 注意特判 \([p==1]\) 的情況。

• 總時間復雜度為 \(O(n^2)\) 。

代碼

#include<bits/stdc++.h> using namespace std; #define go(u) for(int i=head[u],v=e[i].to;i;i=e[i].last,v=e[i].to) #define rep(i,a,b) for(int i=a;i<=b;++i) #define pb push_back typedef long long LL; inline int gi(){int x=0,f=1;char ch=getchar();while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-48;ch=getchar();}return x*f; } template<typename T>inline bool Max(T &a,T b){return a<b?a=b,1:0;} template<typename T>inline bool Min(T &a,T b){return b<a?a=b,1:0;} const int N=2004,mod=998244353; int n; LL p[4][N],w[4][4],f[N],tmp[N],ans[N]; LL Pow(LL a,LL b){LL res=1;for(;b;b>>=1,a=1ll*a*a%mod) if(b&1) res=res*a%mod;return res; } void solve(int k){memset(f,0,sizeof f);f[0]=1;rep(i,1,n){LL p=::p[k][i];for(int j=n;~j;--j)f[j]=((j-1>=0?f[j-1]:0)*p+f[j]*(1-p))%mod;}rep(i,1,n){LL p=::p[k][i];LL inv=Pow(1-p,mod-2);if(p^1){tmp[0]=f[0]*inv%mod;rep(j,1,n) tmp[j]=(f[j]-.tmp[j-1]*p)%mod*inv%mod;}elserep(j,0,n-1) tmp[j]=f[j+1];LL sum=0;for(int j=n/2+1;j<n;++j) (sum+=tmp[j])%=mod;rep(a,0,3)(ans[i]+=(sum+(k==a)*tmp[n/2])*::p[a][i]%mod*w[k][a]%mod)%=mod;} } int main(){n=gi();rep(i,1,n) rep(j,0,3) p[j][i]=gi();rep(i,0,3) rep(j,0,3) w[i][j]=gi();rep(k,0,3) solve(k);rep(i,1,n) printf("%lld\n",(ans[i]+mod)%mod);return 0; }

轉載于:https://www.cnblogs.com/yqgAKIOI/p/9829494.html

總結

以上是生活随笔為你收集整理的牛客网NOIP赛前集训营-提高组（第六场）B-选择题[背包]的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。