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; }
まとめ
解法より問題を理解するのがややこしい。