yukicoder : No.868 ハイパー部分和問題

シンプルな問題設定。
https://yukicoder.me/problems/no/868

問題

N要素の整数列Aと、整数Kが与えられる。
以下のクエリに順次答えよ。

• 要素のうち1つの値を指定に基づき書き換える。その後、整数列の部分列のうち、値の総和がKとなるものが存在するか答えよ。

解法

クエリ毎にナップサック問題を解こうとすると間に合わない。
そこで戻すDPを解く。

理解を簡単にするために、DPを以下のように解釈しよう。
整数列Aに対し、多項式P(x) = (1+x^(A[0]))*(1+x^(A[1]))*....を考える。
元の問題で和が整数Kとなる部分列があるということは、P(x)のx^Kの係数が0ではないことを意味する。

よって、P(x)の係数のうちK次以下の物を求め、クエリ毎に更新していこう。
まず初期の入力に対しP(x)を求める。
Aの更新に対し、仮にA[i]=sだったものをA[i]=tに更新するなら、多項式を一旦(1+x^s)で割り、また(1+x^t)を掛ければよい。

普通の多項式の除算乗算と異なり、次数の低い順に処理していくので注意。
これによりK次より大きな次数の値を無視できる。
各項の係数を具体的に計算しようとすると桁数が大きくなるので、適当な素数でmodを取っておくとよい。

戻すDPと考えると状態遷移がややこしいが、多項式の乗算・除算と考えるとわかりやすい。

int N,K;
int A[151515];
ll dp[15151][3];
ll mo[3]={1000000007,1000000009,1000000021};
int Q;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(j,3) dp[0][j]=1;
	FOR(i,N) {
		cin>>A[i];
		if(A[i]) {
			for(x=15000-A[i];x>=0;x--) {
				FOR(j,3) {
					dp[x+A[i]][j]+=dp[x][j];
					if(dp[x+A[i]][j]>=mo[j]) dp[x+A[i]][j]-=mo[j];
				}
			}
		}
	}
	
	cin>>Q;
	while(Q--) {
		cin>>i>>y;
		i--;
		if(A[i]) {
			FOR(x,15000-A[i]+1) {
				FOR(j,3) {
					dp[x+A[i]][j]+=mo[j]-dp[x][j];
					if(dp[x+A[i]][j]>=mo[j]) dp[x+A[i]][j]-=mo[j];
				}
			}
		}
		A[i]=y;
		if(A[i]) {
			for(x=15000-A[i];x>=0;x--) {
				FOR(j,3) {
					dp[x+A[i]][j]+=dp[x][j];
					if(dp[x+A[i]][j]>=mo[j]) dp[x+A[i]][j]-=mo[j];
				}
			}
		}
		if(dp[K][0]||dp[K][1]||dp[K][2]) cout<<1<<endl;
		else cout<<0<<endl;
		
	}
	
}

まとめ

これは本番に解けて良かったね。