yukicoder : No.1239 Multiplication -2

Multiplicationシリーズ何個あるんだ。
https://yukicoder.me/problems/no/1239

問題

• 2～2の範囲の整数からなるN要素の数列が与えられる。

この数列をいくつかの部分列に分ける方法は2^(N-1)通りある。
それぞれにおいて、要素の積が-2となる部分列の数の総和を求めよ。

解法

f(n,v) := Aをn要素目まで見たとき、最後の部分列の積がvである
というような状態をもってDPする。
ただしvは1,-1,2,-2,その他(0または絶対値3以上)の5通りだけ考えればよい。いったん積がその他の範囲に入ると、以後どうやっても-2にはなりえないためである。
f(n,v)から以下のように遷移しよう。

• いったんn番目で部分列を打ち切る場合、f(n,-2)*2^(N-n-1)を解に計上する。末尾の2の累乗は、以降の要素で部分列の分割が発生する回数。
• 部分列を継続する場合、f(n,v)をf(n+1,v*A[n+1])に加算する。

class CannonballPyramids {
	public:
	vector <int> build(int B) {
		vector<pair<int,ll>> P;
		ll sum=0;
		int i;
		for(i=0;i<=10000;i++) {
			sum+=i*i;
			P.push_back({i,sum});
			if(sum>B) break;
		}
		
		vector<vector<int>> cand={
			{0,0,0},
			{0,1,1},
			{0,2,5},
			{1,1,2},
			{1,2,6},
			{2,2,10},
		};
		
		map<int,pair<int,int>> C;
		FORR(p,P) FORR(q,P) {
			ll s=p.second+q.second;
			C[s]={p.first,q.first};
			
			FORR(c,cand) {
				ll lef=B-(s+c[2]);
				if(C.count(lef)) {
					vector<int> ret;
					ret.push_back(p.first);
					ret.push_back(q.first);
					ret.push_back(C[lef].first);
					ret.push_back(C[lef].second);
					ret.push_back(c[0]);
					ret.push_back(c[1]);
					
					sort(ALL(ret));
					while(ret[0]==0) ret.erase(ret.begin());
					return ret;
					
				}
				
			}
			
			
		}
		
		return {};
		
	}
}

まとめ

int N;
const ll mo=998244353;

ll dp[202020][6]; // -2 -1 0 1 2
ll p2[303030];
void solve() {
int i,j,k,l,r,x,y; string s;

cin>>N;

p2[0]=1;
FOR(i,N) p2[i+1]=p2[i]*2%mo;

dp[0][3]=1;
ll ret=0;
FOR(i,N) {
cin>>x;
// sp
(ret+=dp[i][0]*p2[N-1-i])%=mo;
if(x==0) {
// con
dp[i+1][2]=(dp[i][0]+dp[i][1]+dp[i][2]+dp[i][3]+dp[i][4])%mo;
// new
(dp[i+1][2]+=(dp[i][0]+dp[i][1]+dp[i][2]+dp[i][3]+dp[i][4]))%=mo;
}
if(x==1) {
// con
dp[i+1][0]=dp[i][0];
dp[i+1][1]=dp[i][1];
dp[i+1][2]=dp[i][2];
dp[i+1][3]=dp[i][3];
dp[i+1][4]=dp[i][4];
// new
(dp[i+1][3]+=(dp[i][0]+dp[i][1]+dp[i][2]+dp[i][3]+dp[i][4]))%=mo;
}
if(x==-1) {
// con
dp[i+1][0]=dp[i][4];
dp[i+1][1]=dp[i][3];
dp[i+1][2]=dp[i][2];
dp[i+1][3]=dp[i][1];
dp[i+1][4]=dp[i][0];
// new
(dp[i+1][1]+=(dp[i][0]+dp[i][1]+dp[i][2]+dp[i][3]+dp[i][4]))%=mo;
}
if(x==2) {
// con
dp[i+1][0]=dp[i][1];
dp[i+1][2]=(dp[i][0]+dp[i][2]+dp[i][4])%mo;
dp[i+1][4]=dp[i][3];
// new
(dp[i+1][4]+=(dp[i][0]+dp[i][1]+dp[i][2]+dp[i][3]+dp[i][4]))%=mo;
}
if(x==-2) {
// con
dp[i+1][0]=dp[i][3];
dp[i+1][2]=(dp[i][0]+dp[i][2]+dp[i][4])%mo;
dp[i+1][4]=dp[i][1];
// new
(dp[i+1][0]+=(dp[i][0]+dp[i][1]+dp[i][2]+dp[i][3]+dp[i][4]))%=mo;
}
}
(ret+=dp[N][0])%=mo;

FOR(i,N) ret=ret*(mo+1)/2%mo;

cout<

まとめ

途中、全部分列が-2になるケースを数え上げようとして唸ってた。