提出 #68641795

---

ソースコード 拡げる

#include <bits/stdc++.h>
//#define int long long 
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define fr first
#define se second
#define endl '\n'
#define pb push_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
mt19937_64 rnd(time(0));

const int N = 2e5 + 10;

template<const int T>
struct ModInt {
	const static int mod = T;
	int x;
	ModInt(int x = 0) : x((x % mod + mod) % mod) {}
	ModInt(long long x) : x(int((x % mod + mod) % mod)) {} 
	int val() { return x; }
	ModInt operator + (const ModInt &a) const { int x0 = x + a.x; return ModInt(x0 < mod ? x0 : x0 - mod); }
	ModInt operator - (const ModInt &a) const { int x0 = x - a.x; return ModInt(x0 < 0 ? x0 + mod : x0); }
	ModInt operator * (const ModInt &a) const { return ModInt(1LL * x * a.x % mod); }
	ModInt operator / (const ModInt &a) const { return *this * a.inv(); }
	bool operator == (const ModInt &a) const { return x == a.x; };
	bool operator != (const ModInt &a) const { return x != a.x; };
	void operator += (const ModInt &a) { x += a.x; if (x >= mod) x -= mod; }
	void operator -= (const ModInt &a) { x -= a.x; if (x < 0) x += mod; }
	void operator *= (const ModInt &a) { x = 1LL * x * a.x % mod; }
	void operator /= (const ModInt &a) { *this = *this / a; }
	friend ModInt operator + (int y, const ModInt &a){ int x0 = y + a.x; return ModInt(x0 < mod ? x0 : x0 - mod); }
	friend ModInt operator - (int y, const ModInt &a){ int x0 = y - a.x; return ModInt(x0 < 0 ? x0 + mod : x0); }
	friend ModInt operator * (int y, const ModInt &a){ return ModInt(1LL * y * a.x % mod);}
	friend ModInt operator / (int y, const ModInt &a){ return ModInt(y) / a;}
	friend ostream &operator<<(ostream &os, const ModInt &a) { return os << a.x;}
	friend istream &operator>>(istream &is, ModInt &t){return is >> t.x;}

	ModInt power(int64_t n) const {
		ModInt res(1), mul(x);
		while(n){
			if (n & 1) res *= mul;
			mul *= mul;
			n >>= 1;
		}
		return res;
	}
	
	ModInt inv() const {
		int a = x, b = mod, u = 1, v = 0;
		while (b) {
			int t = a / b;
			a -= t * b; swap(a, b);
			u -= t * v; swap(u, v);
		}
		if (u < 0) u += mod;
		return u;
	}
};
constexpr int MOD = 998244353;
using Z = ModInt<MOD>;

struct Matrix{
	Z a[2][2];
	Matrix() {}

	void init_E(){
		a[0][0] = a[1][1] = 1;
		a[1][0] = a[0][1] = 0;
	}

	Matrix operator* (const Matrix& other) const{
		Matrix t; // 临时存储结果的矩阵
		for(int i = 0; i < 2; i ++){ 
			for(int j = 0; j < 2; j ++){
				for(int k = 0; k < 2; k ++){
					t.a[i][j] = (t.a[i][j] + a[i][k] * other.a[k][j]);	
				}
			}
		}
		return t;
	}
};

struct Node{
	int l, r;
	Matrix mat;

	Node(){
		mat.init_E();
	}
}tr[N << 2];

struct SegTree{
	#define lc p<<1
	#define rc p<<1|1

	void pushup(int p){
		tr[p].mat = tr[lc].mat * tr[rc].mat;
	}

	void build(int p, int l, int r){
		tr[p].l = l, tr[p].r = r;
		tr[p].mat.init_E();
		if(l == r) return;
		int mid = l + r >> 1;
		build(lc, l, mid);
		build(rc, mid + 1, r);
		pushup(p);
	}

	void update(int p, int l, int r, Matrix& mat){
		if(l == tr[p].l && tr[p].r == r){
			for(int i = 0; i < 2; i ++){
				for(int j = 0; j < 2; j ++){
					tr[p].mat.a[i][j] = mat.a[i][j];
				}
			}
			return;
		}
		int mid = tr[p].l + tr[p].r >> 1;
		if(l <= mid) update(lc, l, r, mat);
		if(r > mid) update(rc, l, r, mat);
		pushup(p);
	}
};

Z qpow(Z a, int b, int p)
{
    Z res = 1;
    while (b){ 
        if (b & 1) res = res * a;
        b >>= 1;
        a = a * a;
    }
    return res;
}

template<typename T>
struct Comb
{
    vector<T> fact;   // fact[i]存储i的阶乘
    vector<T> infact; // infact[i]存储i的阶乘的逆元

    explicit Comb(int n){
        init(n);
    }

    void init(int n){
        fact.resize(n + 1);
        infact.resize(n + 1);

        fact[0] = infact[0] = 1;
        for (int i = 1; i <= n; i++){
            fact[i] = fact[i - 1] * i;
        }

        infact[n] = qpow(fact[n], MOD - 2, MOD);

        for (int i = n; i >= 1; i--){
            infact[i - 1] = infact[i] * i;
        }
    }

    T C(int a, int b){
        if (a < 0 || b < 0 || a < b)  return 0;
        return fact[a] * infact[a - b] * infact[b];
    }

    T Catalan(int n){
        return C(2 * n, n) * qpow(n + 1, MOD - 2, MOD);
    }
};

int n, q;
int a[N];
Z fib[N];
Comb<Z> comb(4e5);
SegTree seg;

Z noadj(int n, int r){ // n: 茶壶数量  r: 咖啡数量 
	return comb.C(n - (r - 1), r);
}

Matrix get_f(int n, int r){
	Matrix f;
	// f[0][0]
	f.a[0][0] = noadj(n - 1, r);
	// f[0][1]
	if(n == 1){
		f.a[0][1] = noadj(0, r - 1);
	}
	else{
		f.a[0][1] = noadj(n - 2, r - 1);
	}
	// f[1][0]
	if(n == 1){
		f.a[1][0] = noadj(0, r);
	}
	else{
		f.a[1][0] = noadj(n - 2, r);
	}
	// f[1][1]
	if(n == 1){
		f.a[1][1] = 0;
	}
	else if(n == 2){
		f.a[1][1] = noadj(0, r - 1);
	}
	else{
		f.a[1][1] = noadj(n - 3, r - 1);
	}
	return f;
}

// 默认a[0]=0
void solve()
{
	cin >> n >> q;
	a[0] = 0;
	for(int i = 1; i <= n; i ++){
		a[i] = -1;
	}
	fib[0] = 1;
	fib[1] = 2;
	for(int i = 2; i <= n; i ++){
		fib[i] = fib[i - 1] + fib[i - 2];
	}
	seg.build(1, 1, n);
	set<int> S; // 维护所有非-1的位置
	S.insert(0);

	Matrix temp;
	while(q --){
		int x, val; cin >> x >> val;
		if(a[x] == val){}
		else if(a[x] == -1){ // -1 => 非-1
			S.insert(x);
			a[x] = val;
			auto itl = S.lower_bound(x);
			auto itr = S.upper_bound(x);
			assert(itl != S.begin()); // 一定有0在
			itl --;
			int l = *itl;
			assert(a[l] != -1);
			temp = get_f(x - l, a[x] - a[l]);
			seg.update(1, x, x, temp);
			if(itr != S.end()){
				int r = *itr;
				assert(a[r] != -1);
				temp = get_f(r - x, a[r] - a[x]);
				seg.update(1, r, r, temp);
			}
		}
		else{
			auto itl = S.lower_bound(x);
			auto itr = S.upper_bound(x);
			assert(itl != S.begin()); // 一定有0在
			itl --;
			a[x] = val;
			if(val == -1){ // 非-1 => -1
				temp.init_E();
				seg.update(1, x, x, temp);
				if(itr != S.end()){
					int l = *itl, r = *itr;
					assert(a[l] != -1);
					assert(a[r] != -1);
					temp = get_f(r - l, a[r] - a[l]);
					seg.update(1, r, r, temp);
				}
				S.erase(x);
			}
			else{ // 非-1 => 非-1
				int l = *itl;
				assert(a[l] != -1);
				temp = get_f(x - l, a[x] - a[l]);
				seg.update(1, x, x, temp);
				if(itr != S.end()){
					int r = *itr;
					assert(a[r] != -1);
					temp = get_f(r - x, a[r] - a[x]);
					seg.update(1, r, r, temp);
				}
			}
		}
		int ed = *(--S.end());
		// cout << "ed = " << ed << endl;
		Matrix res = tr[1].mat;
		// cout << res.a[0][0] << " " << res.a[0][1] << endl;
		// cout << res.a[1][0] << " " << res.a[1][1] << endl;
		Z ans = res.a[0][0] * fib[n - ed] + res.a[0][1] * fib[max(0, n - ed - 1)];
		cout << ans << endl;
	}
}


signed main()
{
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	// int T=1; cin>>T; while(T--)
	solve();
	return 0;
}

提出情報

コンパイルエラー

Main.cpp: In member function ‘void SegTree::build(int, int, int)’:
Main.cpp:108:29: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
  108 |                 int mid = l + r >> 1;
      |                           ~~^~~
Main.cpp: In member function ‘void SegTree::update(int, int, int, Matrix&)’:
Main.cpp:123:35: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
  123 |                 int mid = tr[p].l + tr[p].r >> 1;
      |                           ~~~~~~~~^~~~~~~~~
Main.cpp: In function ‘Z qpow(Z, int, int)’:
Main.cpp:130:24: warning: unused parameter ‘p’ [-Wunused-parameter]
  130 | Z qpow(Z a, int b, int p)
      |                    ~~~~^

ジャッジ結果