結果

問題 No.3247 Multiplication 8 2
ユーザー 沙耶花
提出日時 2025-08-22 23:27:47
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 705 ms / 4,000 ms
コード長 2,008 bytes
コンパイル時間 5,024 ms
コンパイル使用メモリ 266,600 KB
実行使用メモリ 45,212 KB
最終ジャッジ日時 2025-08-22 23:28:11
合計ジャッジ時間 22,758 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>
#include <atcoder/all>
#include <bits/stdc++.h>
using namespace std;
using namespace atcoder;
using mint = modint998244353;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define Inf32 1000000005
#define Inf64 1000000000000000001LL

vector<mint> get(vector<int> a){
	int n = a.size();
	vector<mint> res(n+1,0);
	res[0] = 1;
	vector<int> t = {1,-1,2,-2,4,-4,8,-8};
	vector<mint> dp(8,0);
	dp[0] = 1;
	rep(i,n){
		vector<mint> ndp(8);
		rep(j,8){
			int x = a[i];
			x *= t[j];
			int nj = -1;
			rep(k,8){
				if (t[k] == x) {
					nj = k;
					break;
				}
			}
			if(nj==-1)continue;
			ndp[nj] += dp[j];
		}
		res[i+1] += ndp[6];
		ndp[0] += ndp[6];
		dp = ndp;
	}
	return res;
}

mint dp[1000000];
vector<mint> x,y;
vector<int> a;

void dfs(int l,int r){
	if(l==r)return;
	int m = (l+r)/2;
	dfs(l,m);
	dfs(m,r);
	
}

int main(){
	int N,K;
	cin>>N>>K;
	a.resize(N);
	rep(i,N)cin>>a[i];
	vector<int> sum(N+1);
	vector<int> sign(N+1);
	rep(i,N){
		if(abs(a[i])==2)sum[i+1]++;
		sum[i+1] += sum[i];
		if(a[i]<0)sign[i+1] = 1;
		sign[i+1] ^= sign[i];
	}
	auto x = get(a);
	reverse(a.begin(),a.end());
	auto y = get(a);
	reverse(a.begin(),a.end());
	rep(i,sum.back()+1){
		if(i<=2)continue;
		int d0 = distance(sum.begin(),lower_bound(sum.begin(),sum.end(),i-3));
		int d1 = distance(sum.begin(),lower_bound(sum.begin(),sum.end(),i));

		vector<vector<mint>> xs(2),ys(2);
		{
			int c = d0;
			while(c <= N && sum[c] == i-3){
				int t = sign[c];
				xs[t].push_back(x[c]);
				xs[t^1].push_back(0);
				c++;
			}
		}
		{
			int c = d1;
			while(c <= N && sum[c] == i){
				int t = sign[c];
				ys[t].push_back(y[N-c]);
				ys[t^1].push_back(0);
				c++;
			}
		}
		rep(ii,2){
			reverse(xs[ii].begin(),xs[ii].end());
			auto z = convolution(xs[ii],ys[ii]);
			rep(j,z.size()){
				int jj = j - ((int)xs[ii].size()-1);
				jj += d1;
				jj -= d0;
				if(jj<0)continue;
				dp[jj] += z[j];
			}
		}
	}
	
	mint ans = 0;
	rep(i,N+1){
		ans += dp[i] * mint(i).pow(K);
	}
	cout<<ans.val()<<endl;
}
0