結果

問題 No.1546 [Cherry 2nd Tune D] 思ったよりも易しくない
ユーザー ningenMeningenMe
提出日時 2021-04-22 04:09:08
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 165 ms / 2,000 ms
コード長 7,075 bytes
コンパイル時間 2,397 ms
コンパイル使用メモリ 207,996 KB
実行使用メモリ 89,940 KB
最終ジャッジ日時 2023-08-21 10:51:52
合計ジャッジ時間 11,462 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 1 ms
4,376 KB
testcase_03 AC 1 ms
4,384 KB
testcase_04 AC 1 ms
4,376 KB
testcase_05 AC 2 ms
4,376 KB
testcase_06 AC 1 ms
4,380 KB
testcase_07 AC 1 ms
4,376 KB
testcase_08 AC 2 ms
4,376 KB
testcase_09 AC 1 ms
4,376 KB
testcase_10 AC 1 ms
4,376 KB
testcase_11 AC 1 ms
4,376 KB
testcase_12 AC 2 ms
4,376 KB
testcase_13 AC 53 ms
23,100 KB
testcase_14 AC 152 ms
89,328 KB
testcase_15 AC 78 ms
44,148 KB
testcase_16 AC 76 ms
44,160 KB
testcase_17 AC 50 ms
23,104 KB
testcase_18 AC 97 ms
44,852 KB
testcase_19 AC 92 ms
44,980 KB
testcase_20 AC 108 ms
45,316 KB
testcase_21 AC 5 ms
4,376 KB
testcase_22 AC 98 ms
45,080 KB
testcase_23 AC 85 ms
44,412 KB
testcase_24 AC 16 ms
7,752 KB
testcase_25 AC 155 ms
89,232 KB
testcase_26 AC 160 ms
89,888 KB
testcase_27 AC 78 ms
44,208 KB
testcase_28 AC 162 ms
89,568 KB
testcase_29 AC 161 ms
89,548 KB
testcase_30 AC 160 ms
89,780 KB
testcase_31 AC 161 ms
89,636 KB
testcase_32 AC 159 ms
89,632 KB
testcase_33 AC 160 ms
89,724 KB
testcase_34 AC 161 ms
89,696 KB
testcase_35 AC 161 ms
89,672 KB
testcase_36 AC 160 ms
89,676 KB
testcase_37 AC 161 ms
89,632 KB
testcase_38 AC 162 ms
89,940 KB
testcase_39 AC 165 ms
89,724 KB
testcase_40 AC 161 ms
89,620 KB
testcase_41 AC 162 ms
89,768 KB
testcase_42 AC 162 ms
89,756 KB
testcase_43 AC 141 ms
89,660 KB
testcase_44 AC 146 ms
89,624 KB
testcase_45 AC 140 ms
89,628 KB
testcase_46 AC 142 ms
89,716 KB
testcase_47 AC 140 ms
89,560 KB
testcase_48 AC 162 ms
89,600 KB
testcase_49 AC 159 ms
89,836 KB
testcase_50 AC 2 ms
4,380 KB
testcase_51 AC 2 ms
4,380 KB
testcase_52 AC 1 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

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