結果

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

ソースコード

diff #
raw source code 

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#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>;

modint inv2 = modint(2).inv();
modint inv4 = modint(4).inv();
modint inv6 = modint(6).inv();

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

//dstでサボらずに累積和でちゃんと計算するver.
int main() {
    cin.tie(0);ios::sync_with_stdio(false);
    int64 N; cin >> N;
    array<modint,300001> V,T,acc;
    for(int i=1;i<=N;++i) cin >> T[i] >> V[i];
    for(int i=1;i<=N;++i) acc[i]=acc[i-1]+T[i];

    // 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=1;i<=N;++i) {
        modint a = acc[i-1]+1;
        modint b = acc[i-1]+2;
        modint c = -T[i]-(acc[N]-acc[i]);
        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