結果

問題 No.3247 Multiplication 8 2
コンテスト
ユーザー 沙耶花
提出日時 2025-08-22 23:27:47
言語 C++17
(gcc 15.2.0 + boost 1.90.0)
コンパイル:
g++-15 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 448 ms / 4,000 ms
+ 117µs
コード長 2,008 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,215 ms
コンパイル使用メモリ 289,092 KB
実行使用メモリ 45,348 KB
最終ジャッジ日時 2026-07-14 09:24:55
合計ジャッジ時間 15,784 ms
ジャッジサーバーID
（参考情報） 		judge3_1 / judge2_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 28
権限があれば一括ダウンロードができます
コンパイルメッセージ
In file included from /home/linuxbrew/.linuxbrew/Cellar/gcc@15/15.3.0/include/c++/15/vector:67,
                 from /usr/include/atcoder/convolution.hpp:8,
                 from /usr/include/atcoder/convolution:1,
                 from /usr/include/atcoder/all:1,
                 from main.cpp:2:
In function '_ForwardIterator std::uninitialized_copy(_InputIterator, _InputIterator, _ForwardIterator) [with _InputIterator = atcoder::static_modint<998244353>*; _ForwardIterator = atcoder::static_modint<998244353>*]',
    inlined from '_ForwardIterator std::__uninitialized_copy_a(_InputIterator, _Sentinel, _ForwardIterator, allocator<_Tp>&) [with _InputIterator = atcoder::static_modint<998244353>*; _Sentinel = atcoder::static_modint<998244353>*; _ForwardIterator = atcoder::static_modint<998244353>*; _Tp = atcoder::static_modint<998244353>]' at /home/linuxbrew/.linuxbrew/Cellar/gcc@15/15.3.0/include/c++/15/bits/stl_uninitialized.h:637:37,
    inlined from 'std::vector<_Tp, _Alloc>& std::vector<_Tp, _Alloc>::operator=(const std::vector<_Tp, _Alloc>&) [with _Tp = atcoder::static_modint<998244353>; _Alloc = std::allocator<atcoder::static_modint<998244353> >]' at /home/linuxbrew/.linuxbrew/Cellar/gcc@15/15.3.0/include/c++/15/bits/vector.tcc:257:35,
    inlined from 'std::vector<atcoder::static_modint<998244353> > get(std::vector<int>)' at main.cpp:35:8:
/home/linuxbrew/.linuxbrew/Cellar/gcc@15/15.3.0/include/c++/15/bits/stl_uninitialized.h:273:31: warning: 'void* __builtin_memcpy(void*, const void*, long unsigned int)' writing between 1 and 32 bytes into a region of size 0 overflows the destination [-Wstringop-overflow=]
  273 |               __builtin_memcpy(std::__niter_base(__result),
      |               ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  274 |                                std::__niter_base(__first),
      |                                ~~~~~~~~~~~~~~~~~~~~~~~~~~~
  275 |                                __n * sizeof(_ValT));
      |

ソースコード

diff #
raw source code 

#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