結果
| 問題 |
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 |
ソースコード
#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;
}
沙耶花