牛客网NOIP赛前集训营-提高组（第六场）B-选择题[背包]

题意

分析

直接背包之后可以 \(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;

		}else

			rep(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;

}

巴特西

牛客网NOIP赛前集训营-提高组（第六场）B-选择题[背包]

题意

分析

代码

最新文章

热门文章