結果
| 問題 |
No.3247 Multiplication 8 2
|
| コンテスト | |
| ユーザー |
 GOTKAKO
|
| 提出日時 | 2025-08-22 23:51:15 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 1,078 ms / 4,000 ms |
| コード長 | 21,191 bytes |
| コンパイル時間 | 3,861 ms |
| コンパイル使用メモリ | 245,976 KB |
| 実行使用メモリ | 64,780 KB |
| 最終ジャッジ日時 | 2025-08-22 23:52:39 |
| 合計ジャッジ時間 | 23,321 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 28 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
//入力が必ず-mod<a<modの時.
template<const int mod>
struct modint{ //mod変更が不可能.
public:
long long v = 0;
static void setmod(int m){} //飾り.
static constexpr long long getmod(){return mod;}
modint(){v = 0;} modint(int a){v = a<0?a+mod:a;} modint(long long a){v = a<0?a+mod:a;}
modint(unsigned int a){v = a;} modint(unsigned long long a){v = a;}
long long val()const{return v;}
modint &operator=(const modint &b) = default;
modint operator+()const{return (*this);}
modint operator-()const{return modint(0)-(*this);}
modint operator+(const modint b)const{return modint(v)+=b;}
modint operator-(const modint b)const{return modint(v)-=b;}
modint operator*(const modint b)const{return modint(v)*=b;}
modint operator/(const modint b)const{return modint(v)/=b;}
modint operator+=(const modint b){
v += b.v; if(v >= mod) v -= mod;
return *this;
}
modint operator-=(const modint b){
v -= b.v; if(v < 0) v += mod;
return *this;
}
modint operator*=(const modint b){v = v*b.v%mod; return *this;}
modint operator/=(modint b){ //b!=0 mod素数が必須.
if(b == 0) assert(false);
int left = mod-2;
while(left){if(left&1) *this *= b; b *= b; left >>= 1;}
return *this;
}
modint operator++(){*this += 1; return *this;}
modint operator--(){*this -= 1; return *this;}
modint operator++(int){*this += 1; return *this;}
modint operator--(int){*this -= 1; return *this;}
bool operator==(const modint b)const{return v == b.v;}
bool operator!=(const modint b)const{return v != b.v;}
bool operator>(const modint b)const{return v > b.v;}
bool operator>=(const modint b)const{return v >= b.v;}
bool operator<(const modint b)const{return v < b.v;}
bool operator<=(const modint b)const{return v <= b.v;}
modint pow(long long n)const{
modint ret = 1,p = v;
if(n < 0) p = p.inv(),n = -n;
while(n){
if(n&1) ret *= p;
p *= p; n >>= 1;
}
return ret;
}
modint inv()const{return modint(1)/v;} //素数mod必須.
};
template<int idx> //modが入力で与えられる場合.
struct dynamic_modint{ //mod変更が可能 最初にsetmod必須 idxで複数個所持が可能.
private:
static int mod;
public:
long long v = 0;
static constexpr long long getmod(){return mod;}
static void setmod(int m){
assert(m > 0);
mod = m;
}
dynamic_modint(){v = 0;}
dynamic_modint(int a){v = a<0?a+mod:a;} dynamic_modint(long long a){v = a<0?a+mod:a;}
dynamic_modint(unsigned int a){v = a;}
dynamic_modint(unsigned long long a){v = a;}
long long val()const{return v;}
dynamic_modint &operator=(const dynamic_modint &b) = default;
dynamic_modint operator+()const{return (*this);}
dynamic_modint operator-()const{return dynamic_modint(0)-(*this);}
dynamic_modint operator+(const dynamic_modint b)const{return dynamic_modint(v)+=b;}
dynamic_modint operator-(const dynamic_modint b)const{return dynamic_modint(v)-=b;}
dynamic_modint operator*(const dynamic_modint b)const{return dynamic_modint(v)*=b;}
dynamic_modint operator/(const dynamic_modint b)const{return dynamic_modint(v)/=b;}
dynamic_modint operator+=(const dynamic_modint b){
v += b.v; if(v >= mod) v -= mod;
return *this;
}
dynamic_modint operator-=(const dynamic_modint b){
v -= b.v; if(v < 0) v += mod;
return *this;
}
dynamic_modint operator*=(const dynamic_modint b){v = v*b.v%mod; return *this;}
dynamic_modint operator/=(dynamic_modint b){ //b!=0 mod素数が必須.
if(b == 0) assert(false);
int left = mod-2;
while(left){if(left&1) *this *= b; b *= b; left >>= 1;}
return *this;
}
dynamic_modint operator++(){*this += 1; return *this;}
dynamic_modint operator--(){*this -= 1; return *this;}
dynamic_modint operator++(int){*this += 1; return *this;}
dynamic_modint operator--(int){*this -= 1; return *this;}
bool operator==(const dynamic_modint b)const{return v == b.v;}
bool operator!=(const dynamic_modint b)const{return v != b.v;}
bool operator>(const dynamic_modint b)const{return v > b.v;}
bool operator>=(const dynamic_modint b)const{return v >= b.v;}
bool operator<(const dynamic_modint b)const{return v < b.v;}
bool operator<=(const dynamic_modint b)const{return v <= b.v;}
dynamic_modint pow(long long n)const{
dynamic_modint ret = 1,p = v;
if(n < 0) p = p.inv(),n = -n;
while(n){
if(n&1) ret *= p;
p *= p; n >>= 1;
}
return ret;
}
dynamic_modint inv()const{return dynamic_modint(1)/v;} //素数mod必須.
};
template<int idx> int dynamic_modint<idx>::mod=998244353;
using mint = modint<998244353>;
//using mint = modint<1000000007>;
//using mint = dynamic_modint<0>;
namespace to_fold{
__int128_t safemod(__int128_t a,long long m){a %= m; if(a < 0) a += m; return a;}
pair<long long,long long> invgcd(long long a,long long b){
//return {gcd(a,b),x} (xa≡g(mod b))
a = safemod(a,b);
if(a == 0) return {b,0};
long long x = 0,y = 1,memob = b;
while(a){
long long q = b/a;
b -= a*q;
swap(x,y); y -= q*x;
swap(a,b);
}
if(x < 0) x += memob/b;
return {b,x};
}
template<long long mod>
long long Garner(const vector<long long> &A,const vector<long long> &M){
__int128_t mulM = 1,x = A.at(0)%M.at(0); //Mの要素のペア互いに素必須.
for(int i=1; i<A.size(); i++){
//assert(gcd(mulM,M.at(i-1)) == 1);
mulM *= M.at(i-1); //2乗がオーバーフローする時__int128_t
long long t = safemod((A.at(i)-x)*invgcd(mulM,M.at(i)).second,M.at(i));
x += t*mulM;
}
return x%mod;
}
int countzero(unsigned long long x){
if(x == 0) return 64;
else return __popcount((x&-x)-1);
}
template<typename mint>
struct fftinfo{
static bool First;
static mint g,sum_e[30],sum_ie[30]; //sum_e[i]=Π[j=0~i-1]ies[j] * es[i],sum_ie[i]=Π[i=0~j-1]es[j] * ies[i].
static mint divpow2[30]; //div[i] = 1/(2^i).
static mint Zeta[30];
fftinfo(){
if(!First) return;
First = false;
const long long mod = mint::getmod();
if(mod == 998244353) g = 3;
else if(mod == 754974721) g = 11;
else if(mod == 167772161) g = 3;
else if(mod == 469762049) g = 3;
else assert(false); //現状RE.
mint es[30],ies[30]; //es[i]^(2^(2+i))=1.
int cnt2 = countzero(mod-1);
mint e = g.pow((mod-1)>>cnt2),ie = e.inv();
for(int i=cnt2; i>=2; i--){ //e^(2^i)=1;
es[i-2] = e,e *= e;
ies[i-2] = ie,ie *= ie;
}
mint rot = 1;
for(int i=0; i<=cnt2-2; i++) sum_e[i] = es[i]*rot,rot *= ies[i];
rot = 1;
for(int i=0; i<=cnt2-2; i++) sum_ie[i] = ies[i]*rot,rot *= es[i];
mint div2n = 1,div2 = mint(1)/2;
for(int i=0; i<30; i++) divpow2[i] = div2n,div2n *= div2;
for(int i=0; i<=cnt2; i++) Zeta[i] = g.pow((mod-1)/(2<<i));
}
};
template<typename mint> bool fftinfo<mint>::First=true;
template<typename mint> mint fftinfo<mint>::g;
template<typename mint> mint fftinfo<mint>::sum_e[30];
template<typename mint> mint fftinfo<mint>::sum_ie[30];
template<typename mint> mint fftinfo<mint>::divpow2[30];
template<typename mint> mint fftinfo<mint>::Zeta[30];
template<typename mint>
void NTT(vector<mint> &A){ //ACLを超参考にしてる.
int n = A.size();
assert((n&-n) == n);
fftinfo<mint> info;
int h = countzero(n);
for(int ph=1; ph<=h; ph++){
int w = 1<<(ph-1),p = 1<<(h-ph);
mint rot = 1;
for(int s=0; s<w; s++){
int offset = s<<(h-ph+1);
for(int i=0; i<p; i++){
mint l = A.at(i+offset),r = A.at(i+offset+p)*rot;
A.at(i+offset) = l+r;
A.at(i+offset+p) = l-r;
}
rot *= info.sum_e[countzero(~(unsigned int)(s))];
}
}
}
template<typename mint>
void INTT(vector<mint> &A){
int n = A.size();
assert((n&-n) == n);
fftinfo<mint> info;
const unsigned int mod = mint::getmod();
int h = countzero(n);
for(int ph=h; ph>0; ph--){
int w = 1<<(ph-1),p = 1<<(h-ph);
mint irot = 1;
for(int s=0; s<w; s++){
int offset = s<<(h-ph+1);
for(int i=0; i<p; i++){
mint l = A.at(i+offset),r = A.at(i+offset+p);
A.at(i+offset) = l+r;
A.at(i+offset+p) = ((unsigned long long)(mod+(unsigned int)l.v-(unsigned int)r.v)*irot.v)%mod;
}
irot *= info.sum_ie[countzero(~(unsigned int)(s))];
}
}
mint divn = info.divpow2[h];
for(auto &a : A) a *= divn;
}
template<typename mint>
vector<mint> convolution(vector<mint> A,vector<mint> B){ //mintじゃないのを突っ込まないように!!!.
int siza = A.size(),sizb = B.size(),sizc = siza+sizb-1,N = 1;
if(siza == 0 || sizb == 0) return {};
if(min(siza,sizb) <= 60){ //naive.
vector<mint> ret(sizc);
if(siza >= sizb){for(int i=0; i<siza; i++) for(int k=0; k<sizb; k++) ret.at(i+k) += A.at(i)*B.at(k);}
else{for(int i=0; i<sizb; i++) for(int k=0; k<siza; k++) ret.at(i+k) += B.at(i)*A.at(k);}
return ret;
}
while(N < sizc) N <<= 1;
A.resize(N),B.resize(N);
NTT(A); NTT(B);
for(int i=0; i<N; i++) A.at(i) *= B.at(i);
INTT(A); A.resize(sizc);
return A;
}
vector<long long> convolution_ll(const vector<long long> &A,const vector<long long> &B){ //long longに収まる範囲.
int siza = A.size(),sizb = B.size(),sizc = siza+sizb-1;
if(siza == 0 || sizb == 0) return {};
vector<long long> ret(sizc);
if(min(siza,sizb) <= 200){ //naive 200はやばい?.
vector<long long> ret(sizc);
if(siza >= sizb){for(int i=0; i<siza; i++) for(int k=0; k<sizb; k++) ret.at(i+k) += A.at(i)*B.at(k);}
else{for(int i=0; i<sizb; i++) for(int k=0; k<siza; k++) ret.at(i+k) += B.at(i)*A.at(k);}
return ret;
}
const unsigned long long mod1 = 754974721,mod2 = 167772161,mod3 = 469762049;
const unsigned long long m1m2 = mod1*mod2,m2m3 = mod2*mod3,m3m1 = mod3*mod1,m1m2m3 = mod1*mod2*mod3;
const unsigned long long i1 = invgcd(m2m3,mod1).second,i2 = invgcd(m3m1,mod2).second,i3 = invgcd(m1m2,mod3).second;
assert(sizc <= (1<<24));
using mint1 = modint<mod1>;
using mint2 = modint<mod2>;
using mint3 = modint<mod3>;
vector<mint1> a1(siza),b1(sizb);
vector<mint2> a2(siza),b2(sizb);
vector<mint3> a3(siza),b3(sizb);
for(int i=0; i<siza; i++) a1.at(i) = A.at(i)%mod1;
for(int i=0; i<sizb; i++) b1.at(i) = B.at(i)%mod1;
vector<mint1> C1 = convolution(a1,b1);
for(int i=0; i<siza; i++) a2.at(i) = A.at(i)%mod2;
for(int i=0; i<sizb; i++) b2.at(i) = B.at(i)%mod2;
vector<mint2> C2 = convolution(a2,b2);
for(int i=0; i<siza; i++) a3.at(i) = A.at(i)%mod3;
for(int i=0; i<sizb; i++) b3.at(i) = B.at(i)%mod3;
vector<mint3> C3 = convolution(a3,b3);
vector<unsigned long long> offset = {0,0,m1m2m3,2*m1m2m3,3*m1m2m3};
for(int i=0; i<sizc; i++){
unsigned long long x = 0;
x += (C1.at(i).v*i1)%mod1*m2m3;
x += (C2.at(i).v*i2)%mod2*m3m1;
x += (C3.at(i).v*i3)%mod3*m1m2;
long long diff = C1.at(i).v-((long long)x+(long long)mod1)%mod1;
if(diff < 0) diff += mod1;
x -= offset.at(diff%5);
ret.at(i) = x;
}
return ret;
}
template<typename mint>
vector<mint> convolution_llmod(const vector<mint> &A,const vector<mint> &B){
int siza = A.size(),sizb = B.size(),sizc = siza+sizb-1;
if(siza == 0 || sizb == 0) return {};
vector<mint> ret(sizc);
if(min(siza,sizb) <= 200){
for(int i=0; i<siza; i++) for(int k=0; k<sizb; k++) ret.at(i+k) += A.at(i)*B.at(k);
return ret;
}
const long long mod1 = 754974721,mod2 = 167772161,mod3 = 469762049;
assert(sizc <= (1<<24));
using mint1 = modint<mod1>;
using mint2 = modint<mod2>;
using mint3 = modint<mod3>;
vector<mint1> a1(siza),b1(sizb);
vector<mint2> a2(siza),b2(sizb);
vector<mint3> a3(siza),b3(sizb);
for(int i=0; i<siza; i++) a1.at(i) = A.at(i).v%mod1;
for(int i=0; i<sizb; i++) b1.at(i) = B.at(i).v%mod1;
vector<mint1> C1 = convolution(a1,b1);
for(int i=0; i<siza; i++) a2.at(i) = A.at(i).v%mod2;
for(int i=0; i<sizb; i++) b2.at(i) = B.at(i).v%mod2;
vector<mint2> C2 = convolution(a2,b2);
for(int i=0; i<siza; i++) a3.at(i) = A.at(i).v%mod3;
for(int i=0; i<sizb; i++) b3.at(i) = B.at(i).v%mod3;
vector<mint3> C3 = convolution(a3,b3);
for(int i=0; i<sizc; i++){
vector<long long> A = {C1.at(i).v,C2.at(i).v,C3.at(i).v};
vector<long long> M = {mod1,mod2,mod3};
ret.at(i) = Garner<mint::getmod()>(A,M);
}
return ret;
}
vector<int> convolution_int(const vector<int> &A,const vector<int> &B){ //intに収まる範囲.
if(A.size() == 0 || B.size() == 0) return {};
vector<int> ret;
if(min(A.size(),B.size()) <= 60){
ret.resize(A.size()+B.size()-1);
for(int i=0; i<A.size(); i++) for(int k=0; k<B.size(); k++) ret.at(i+k) += A.at(i)*B.at(k);
}
else{
using mint1 = modint<998244353>;
vector<mint1> X(A.size()),Y(B.size()),Z;
for(int i=0; i<A.size(); i++) X.at(i) = A.at(i);
for(int i=0; i<B.size(); i++) Y.at(i) = B.at(i);
Z = convolution(X,Y);
ret.resize(Z.size());
for(int i=0; i<Z.size(); i++) ret.at(i) = Z.at(i).v;
}
return ret;
}
template<typename mint>
void NTTdoubling(vector<mint> &A){ //NTTの原理を忘れているため何やってるのか意味が分からない NTT-friendly専用.
//INTT->resize(2倍）->NTTの代わりにcopy->INTT->謎の操作->NTT->push sizeが小さい時は効率悪いらしいよ.
int n = A.size();
fftinfo<mint> info;
vector<mint> B = A;
INTT(B);
mint rot = 1,zeta = info.Zeta[countzero(n)];
for(auto &v : B) v *= rot,rot *= zeta;
NTT(B); A.reserve(n<<1);
for(auto &v : B) A.push_back(v);
}
bool isNTTfriendly(long long mod){
if(mod == 998244353 || mod == 754974721 || mod == 16777216 || mod == 469762049) return true;
return false; //現状false 原子根求める機能を追加してから.
int have2 = countzero(mod-1);
return have2 >= 20;//とりあえず2^20でokとする;
}
}
using namespace to_fold;
using SS = mint;
class SegmentTree{
public:
int siz = -1,n = -1;
vector<SS> dat;
SS op(SS a, SS b){return a+b;}
SS e(){return mint(0);}
void renew (SS &a,SS x){
a = op(a,x);
//a = x; //set(pos,x)で可能.
//その他.
}
SegmentTree(int N){init(N);}
SegmentTree(const vector<SS> &A){//長さ配列サイズに合わせる.
siz = 1; n = A.size();
while(siz < n) siz *= 2;
dat.resize(siz*2,e());
for(int i=0; i<n; i++) dat.at(i+siz) = A.at(i);
for(int i=siz-1; i>0; i--) dat.at(i) = op(dat.at(i*2),dat.at(i*2+1));
}
void init(int N){
//全要素単位元に初期化.
siz = 1; n = N;
while(siz < n) siz *= 2;
dat.assign(siz*2,e());
}
void init(const vector<SS> &A){//長さ配列サイズに合わせる.
siz = 1; n = A.size();
while(siz < n) siz *= 2;
dat.resize(siz*2,e());
for(int i=0; i<n; i++) dat.at(i+siz) = A.at(i);
for(int i=siz-1; i>0; i--) dat.at(i) = op(dat.at(i*2),dat.at(i*2+1));
}
void set(int pos,SS x){
pos = pos+siz;
dat.at(pos) = x;
while(pos != 1){
pos = pos/2;
dat.at(pos) = op(dat.at(pos*2),dat.at(pos*2+1));
}
}
void update(int pos,SS x){
pos = pos+siz;
renew(dat.at(pos),x);
while(pos != 1){
pos = pos/2;
dat.at(pos) = op(dat.at(pos*2),dat.at(pos*2+1));
}
}
SS findans(int l, int r){
SS retl = e(),retr = e();
l += siz,r += siz;
while(l < r){
if(l&1) retl = op(retl,dat.at(l++));
if(r&1) retr = op(dat.at(--r),retr);
l >>= 1; r >>= 1;
}
return op(retl,retr);
}
SS get(int pos){return dat.at(pos+siz);}
SS rangeans(int l, int r){return findans(l,r);}
SS allrange(){return dat.at(1);}
//rightは) leftは[で 渡す&返す.
int maxright(const function<bool(SS)> f,int l = 0){
//fを満たさない最小の箇所を返す なければn.
l += siz; int r = n+siz;
vector<int> ls,rs;
while(l < r){
if(l&1) ls.push_back(l++);
if(r&1) rs.push_back(--r);
l >>= 1; r >>= 1;
}
SS okl = e();
for(int i=0; i<ls.size(); i++){
l = ls.at(i);
SS now = op(okl,dat.at(l));
if(!f(now)){
while(l < siz){
l <<= 1;
now = op(okl,dat.at(l));
if(f(now)){okl = now; l++;}
}
return l-siz;
}
okl = now;
}
for(int i=rs.size()-1; i>=0; i--){
l = rs.at(i);
SS now = op(okl,dat.at(l));
if(!f(now)){
while(l < siz){
l <<= 1;
now = op(okl,dat.at(l));
if(f(now)){okl = now; l++;}
}
return l-siz;
}
okl = now;
}
return n;
}
int minleft(const function<bool(SS)> f,int r = -1){
//fを満たす最小の箇所を返す なければ0.
if(r == -1) r = n;
int l = siz; r += siz;
vector<int> ls,rs;
while(l < r){
if(l&1) ls.push_back(l++);
if(r&1) rs.push_back(--r);
l >>= 1; r >>= 1;
}
SS okr = e();
for(int i=0; i<rs.size(); i++){
r = rs.at(i);
SS now = op(dat.at(r),okr);
if(!f(now)){
while(r < siz){
r <<= 1; r++;
now = op(dat.at(r),okr);
if(f(now)){okr = now; r--;}
}
return r+1-siz;
}
okr = now;
}
for(int i=ls.size()-1; i>=0; i--){
r = ls.at(i);
SS now = op(dat.at(r),okr);
if(!f(now)){
while(r < siz){
r <<= 1; r++;
now = op(dat.at(r),okr);
if(f(now)){okr = now; r--;}
}
return r+1-siz;
}
okr = now;
}
return 0;
}
};
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
auto f = [&](vector<int> A) -> vector<mint> {
int N = A.size();
vector<int> two(N),minus(N);
for(int i=0; i<N; i++){
if(abs(A.at(i)) == 2) two.at(i)++;
if(A.at(i) < 0) minus.at(i)++;
}
for(int i=1; i<N; i++) two.at(i) += two.at(i-1),minus.at(i) ^= minus.at(i-1);
two.push_back(1001001001);
SegmentTree Z(N+2);
Z.update(0,1),Z.update(1,-1);
vector<mint> ret(N+1);
for(int i=0; i<N; i++){
int t = 0,m = 0;
if(i) t = two.at(i-1),m = minus.at(i-1);
if(m%2) continue;
auto v = Z.rangeans(0,i+1);
ret.at(i) = v;
int l = lower_bound(two.begin(),two.end(),t+3)-two.begin();
int r = lower_bound(two.begin(),two.end(),t+4)-two.begin();
Z.update(l+1,v),Z.update(r+1,-v);
}
ret.at(N) = Z.rangeans(0,N+1);
return ret;
};
int N,K; cin >> N >> K;
vector<int> A(N);
int two = 0,under0 = 0;
for(auto &a : A) cin >> a,two += abs(a)==2,under0 += a<0;
if(two == 0 || two%3 || under0%2){cout << "0\n"; return 0;}
vector<mint> powK(N+1);
for(int i=0; i<=N; i++) powK.at(i) = mint(i).pow(K);
auto B = A;
reverse(B.begin(),B.end());
auto L = f(A),R = f(B);
reverse(R.begin(),R.end());
vector<pair<int,int>> LR(two+1);
{
LR.at(0) = {0,1};
int pos = 0;
for(int i=0; i<N; i++){
if(abs(A.at(i)) == 2) pos++,LR.at(pos) = {i+1,i+2};
else LR.at(pos).second++;
}
}
mint answer = 0;
for(int i=0; i+3<=two; i++){
auto [l1,r1] = LR.at(i);
auto [l2,r2] = LR.at(i+3);
int n = r1-l1,m = r2-l2;
int len = l2-r1+1;
vector<mint> X(n),Y(m);
int pos = 0;
for(int p=r1-1; p>=l1; p--) X.at(pos) = L.at(p),pos++;
pos = 0;
for(int p=l2; p<r2; p++) Y.at(pos) = R.at(p),pos++;
auto Z = convolution(X,Y);
for(int p=0; p<Z.size(); p++) answer += powK.at(len+p)*Z.at(p);
}
cout << answer.v << endl;
}