kmjp's blog

競技プログラミング参加記です

AtCoder ABC #169 : F - Knapsack for All Subsets

Eで遠回りしすぎて、こちらは簡単だった。
https://atcoder.jp/contests/abc169/tasks/abc169_f

問題

整数列Aが与えられる。
Aの部分列A'に対し、f(A')はA'のこれまた部分列A''のうちsum(A'')=Sとなるものの数を指す。
A,Sに対しsum(f(A'))を求めよ。

解法

sum(A'')=SとなるA''があったとき、これがどの程度解に寄与するか考えよう。
Aの各要素は以下に分類できる。

  • A''に含まれる
  • A''に含まれない
    • A'に含まれる
    • A'にも含まれない

よってA''1個につき2^(|A|-|A''|)回カウントされる。
そこでナップサック問題でsum(A'')=SとなるA''を求める際、A''に含めない要素は、後者2通りで二重カウントするようにしてDPしていけばよい。

int N,S;
const ll mo=998244353;
ll dp[3030][3030];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>S;
	dp[0][0]=1;
	FOR(i,N) {
		cin>>x;
		FOR(j,S+1) {
			// not
			(dp[i+1][j]+=dp[i][j]*2)%=mo;
			if(j+x<=S) (dp[i+1][j+x]+=dp[i][j])%=mo;
		}
	}
	cout<<dp[N][S]<<endl;
}

まとめ

解法より問題を理解するのがややこしい。