結果
| 問題 | No.2833 Count Taiko Results |
| コンテスト | |
| ユーザー |
 GOTKAKO
|
| 提出日時 | 2024-08-03 13:53:38 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 201 ms / 2,000 ms |
| コード長 | 6,057 bytes |
| コンパイル時間 | 2,271 ms |
| コンパイル使用メモリ | 201,588 KB |
| 最終ジャッジ日時 | 2025-02-23 20:50:40 |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 58 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
long long mod = 998244353;
//入力が必ずmod未満の時に使う.
struct mint{
long long v = 0;
mint(){} mint(int a){v = a;} mint(long long a){v = a;} mint(unsigned long long a){v = a;}
long long val(){return v;}
void modu(){v %= mod;}
mint repeat2mint(const long long a,long long b){
mint ret = 1,p = a;
while(b){
if(b&1) ret *= p;
p *= p; b >>= 1;
}
return ret;
};
mint operator+(const mint b){return mint(v)+=b;}
mint operator-(const mint b){return mint(v)-=b;}
mint operator*(const mint b){return mint(v)*=b;}
mint operator/(const mint b){return mint(v)/=b;}
mint operator+=(const mint b){
v += b.v; if(v >= mod) v -= mod;
return *this;
}
mint operator-=(const mint b){
v -= b.v; if(v < 0) v += mod;
return *this;
}
mint operator*=(const mint b){v = v*b.v%mod; return *this;}
mint operator/=(mint b){
if(b == 0) assert(false);
int left = mod-2;
while(left){if(left&1) *this *= b; b *= b; left >>= 1;}
return *this;
}
mint operator++(int){*this += 1; return *this;}
mint operator--(int){*this -= 1; return *this;}
bool operator==(const mint b){return v == b.v;}
bool operator!=(const mint b){return v != b.v;}
bool operator>(const mint b){return v > b.v;}
bool operator>=(const mint b){return v >= b.v;}
bool operator<(const mint b){return v < b.v;}
bool operator<=(const mint b){return v <= b.v;}
mint pow(const long long x){return repeat2mint(v,x);}
mint inv(){return mint(1)/v;}
};
using SS = mint;
class SegmentTree{
public:
int siz = 1,n;
vector<SS> dat;
SS op(SS a, SS b){return a*b;}
SS e(){return 1;}
void renew (SS &a,SS x){
//a = op(a,x);
a = x;
//その他.
}
void make(int N){
while(siz < N) siz *= 2;
n = N; dat.resize(siz*2,e());
}
void make2(int N,vector<SS> &A){
make(N);
for(int i=0; i<N; i++){
int pos = i+siz;
dat.at(pos) = 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 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){
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){
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;
}
}
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;
}
}
return 0;
}
//ノーマルセグ木.一年の時を経て漸く二分探索実装した.
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int N,K; cin >> N >> K;
vector<mint> A(N),B(N);
for(auto &a : A) cin >> a.v;
for(auto &a : B) cin >> a.v;
mint sum = 1;
SegmentTree Z; Z.make2(N,A);
vector<mint> dp(N+1);
dp.at(0) = 1;
for(int i=1; i<=N; i++){
mint a = A.at(i-1),b = B.at(i-1);
dp.at(i) = sum*b;
sum *= a; sum += dp.at(i);
if(i >= K) sum -= Z.rangeans(i-K,i)*dp.at(i-K);
}
sum = 0;
vector<mint> dp2(N+1);
for(int i=K; i<N; i++) dp2.at(i+1) = Z.rangeans(i-K,i)*dp.at(i-K)*B.at(i);
dp2.at(N) += Z.rangeans(N-K,N)*dp.at(N-K);
for(int i=1; i<=N; i++){
mint a = A.at(i-1),b = B.at(i-1);
dp2.at(i) += sum*b;
sum *= a; sum += dp2.at(i);
if(i >= K+1) sum -= Z.rangeans(i-K-1,i)*dp2.at(i-K-1);
}
cout << sum.v << endl;
}