結果

問題 No.1546 [Cherry 2nd Tune D] 思ったよりも易しくない
コンテスト
ユーザー ningenMe
提出日時 2021-04-22 04:09:08
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 551 ms / 2,000 ms
コード長 7,075 bytes
コンパイル時間 8,452 ms
コンパイル使用メモリ 203,540 KB
最終ジャッジ日時 2025-01-20 22:34:35
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 53
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using int64   = long long;
constexpr int64 MOD = 998244353;

/*
 * @title ModInt
 * @docs md/util/ModInt.md
 */
template<long long mod> class ModInt {
public:
    long long x;
    constexpr ModInt():x(0) {}
    constexpr ModInt(long long y) : x(y>=0?(y%mod): (mod - (-y)%mod)%mod) {}
    ModInt &operator+=(const ModInt &p) {if((x += p.x) >= mod) x -= mod;return *this;}
    ModInt &operator+=(const long long y) {ModInt p(y);if((x += p.x) >= mod) x -= mod;return *this;}
    ModInt &operator+=(const int y) {ModInt p(y);if((x += p.x) >= mod) x -= mod;return *this;}
    ModInt &operator-=(const ModInt &p) {if((x += mod - p.x) >= mod) x -= mod;return *this;}
    ModInt &operator-=(const long long y) {ModInt p(y);if((x += mod - p.x) >= mod) x -= mod;return *this;}
    ModInt &operator-=(const int y) {ModInt p(y);if((x += mod - p.x) >= mod) x -= mod;return *this;}
    ModInt &operator*=(const ModInt &p) {x = (x * p.x % mod);return *this;}
    ModInt &operator*=(const long long y) {ModInt p(y);x = (x * p.x % mod);return *this;}
    ModInt &operator*=(const int y) {ModInt p(y);x = (x * p.x % mod);return *this;}
    ModInt &operator^=(const ModInt &p) {x = (x ^ p.x) % mod;return *this;}
    ModInt &operator^=(const long long y) {ModInt p(y);x = (x ^ p.x) % mod;return *this;}
    ModInt &operator^=(const int y) {ModInt p(y);x = (x ^ p.x) % mod;return *this;}
    ModInt &operator/=(const ModInt &p) {*this *= p.inv();return *this;}
    ModInt &operator/=(const long long y) {ModInt p(y);*this *= p.inv();return *this;}
    ModInt &operator/=(const int y) {ModInt p(y);*this *= p.inv();return *this;}
    ModInt operator=(const int y) {ModInt p(y);*this = p;return *this;}
    ModInt operator=(const long long y) {ModInt p(y);*this = p;return *this;}
    ModInt operator-() const {return ModInt(-x); }
    ModInt operator++() {x++;if(x>=mod) x-=mod;return *this;}
    ModInt operator--() {x--;if(x<0) x+=mod;return *this;}
    ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }
    ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }
    ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }
    ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }
    ModInt operator^(const ModInt &p) const { return ModInt(*this) ^= p; }
    bool operator==(const ModInt &p) const { return x == p.x; }
    bool operator!=(const ModInt &p) const { return x != p.x; }
    ModInt inv() const {int a=x,b=mod,u=1,v=0,t;while(b > 0) {t = a / b;swap(a -= t * b, b);swap(u -= t * v, v);} return ModInt(u);}
    ModInt pow(long long n) const {ModInt ret(1), mul(x);for(;n > 0;mul *= mul,n >>= 1) if(n & 1) ret *= mul;return ret;}
    friend ostream &operator<<(ostream &os, const ModInt &p) {return os << p.x;}
    friend istream &operator>>(istream &is, ModInt &a) {long long t;is >> t;a = ModInt<mod>(t);return (is);}
};
using modint = ModInt<MOD>;

/*
 * @title DisjointSparseTable
 * @docs md/segment/DisjointSparseTable.md
 */
template<class Operator> class DisjointSparseTable{
public:
	using TypeNode = typename Operator::TypeNode;
	size_t depth;
	size_t length;
	vector<TypeNode> node;
	vector<size_t> msb;

	DisjointSparseTable(const vector<TypeNode>& vec) {
		for(depth = 0;(1<<depth)<=vec.size();++depth);
		length = (1<<depth);
		
		//msb
		msb.resize(length,0);
		for(int i = 0; i < length; ++i) for(int j = 0; j < depth; ++j) if(i>>j) msb[i] = j;

		//init value
		node.resize(depth*length,Operator::unit_node);
		for(int i = 0; i < vec.size(); ++i) node[i] = vec[i];

		for(int i = 1; i < depth; ++i) {
			for(int r = (1<<i),l = r-1; r < length; r += (2<<i),l = r-1){
				//init accumulate
				node[i*length+l] = node[l];
				node[i*length+r] = node[r];
				//accumulate
				for(int k = 1; k < (1<<i); ++k) {
					node[i*length+l-k] = Operator::func_node(node[i*length+l-k+1],node[l-k]);
					node[i*length+r+k] = Operator::func_node(node[i*length+r+k-1],node[r+k]);
				}
			}
		}
	}

	//[l,r)
	TypeNode get(int l,int r) {
		r--;
		return (l>r||l<0||length<=r) ? Operator::unit_node: (l==r ? node[l] : Operator::func_node(node[msb[l^r]*length+l],node[msb[l^r]*length+r]));
	}
};

//sum
template<class T> struct NodeSum {
	using TypeNode = T;
	inline static constexpr TypeNode unit_node = 0;
	inline static constexpr TypeNode func_node(TypeNode l,TypeNode r){return l+r;}
};
modint inv2 = modint(2).inv();
modint inv4 = modint(4).inv();
modint inv6 = modint(6).inv();

modint sigma_k1(modint n) {
    return n*(n+1)*inv2;
}
modint sigma_k2(modint n) {
    return n*(n+1)*(n*2+1)*inv6;
}
modint sigma_k3(modint n) {
    return n*n*(n+1)*(n+1)*inv4;
}

/**
 * @url 
 * @est
 */ 
int main() {
    cin.tie(0);ios::sync_with_stdio(false);
    int64 N; cin >> N;
    vector<modint> V(N),T(N);
    for(int i=0;i<N;++i) cin >> T[i] >> V[i];
    DisjointSparseTable<NodeSum<modint>> S(T);

    // V_{0,0},...,V_{0,T1-1},V_{1,0},...,V_{1,T2-1},...,V_{N-1,TN-1} とする
    // T_iの区間和をS[l,r)とする
    // V_{i,0} に関して
    // 係数が1になるときを考えると、右側にT_{i}+T_{i+1}+...+T_{N-1} = T_i + S[i+1,N) 通り存在するので
    // 1 * V_{i,0} * (T_i + S[i+1,N))
    // 係数が2になるときを考えると、
    // 2 * V_{i,0} * (T_i + S[i+1,N))
    // 一般のkに対して
    // k * V_{i,0} * (T_i + S[i+1,N))

    // ここでkは 1,2,...,S[0,i)+1の範囲を動くので、
    // V_{i,0}にかかる係数込みの数f(i,0)を考えると
    // f(i,0) = (S[0,i)+1)*(S[0,i)+2)/2 * V_{i,0} * (T_i + S[i+1,N))

    // ここでf(i,j)に関して考えると
    // f(i,j) = Σ k * V_{i,j} * Σ 1
    // ここで、i,jを固定したとき、右側のシグマ(Σ 1)に関しては、T_{i}-j + S[i+1,N) となるので
    // f(i,j) = Σ k * V_{i,j} * (T_{i}-j + S[i+1,N))
    // ここで、kは 1,2,...,S[0,i)+(j+1) の範囲を動くので、
    // f(i,j) = (S[0,i)+(j+1))*(S[0,i)+(j+1)+1)/2 * V_{i,j} * (T_{i}-j + S[i+1,N))
    // ここで、iに関して、V_{i,j}が定数V_iであることをふまえて、jに関して降べきの順になおすと
    // f(i,j) = (j+S[0,i)+1) * (j+S[0,i)+2) / 2 * V_i * (-j + T_{i}+S[i+1,N))
    // f(i,j) = (j+S[0,i)+1) * (j+S[0,i)+2) * (j - T_{i}-S[i+1,N)) *(-1) / 2 * V_i 
    // f(i,j) = (j+a)        * (j+b)        * (j + c)              * d
    // f(i,j) = (j*j*j + (a+b+c)*j*j + (ab+bc+ca)*j + abc)*d
    // ここでjを0からT_{i}-1までΣを取る計算がO(1)でできるようになる。
    // あとはこれをi=1,...,Nに関して計算する
    // 最終的な答えは ans = ΣΣf(i,j)である

    modint ans = 0;
    for(int i=0;i<N;++i) {
        modint a = S.get(0,i)+1;
        modint b = S.get(0,i)+2;
        modint c = -T[i]-S.get(i+1,N);
        modint d = inv2 * V[i] * (-1);
        modint cnt = 0;
        cnt += sigma_k3(T[i]-1);
        cnt += (a+b+c)*sigma_k2(T[i]-1);
        cnt += (a*b+b*c+c*a)*sigma_k1(T[i]-1);
        cnt += a*b*c*T[i];
        cnt *= d;
        ans += cnt;
    }
    cout << ans << endl;
    return 0;
}
0