結果
問題 | No.1546 [Cherry 2nd Tune D] 思ったよりも易しくない |
ユーザー | ningenMe |
提出日時 | 2021-04-22 04:44:04 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 7,282 bytes |
コンパイル時間 | 2,691 ms |
コンパイル使用メモリ | 211,264 KB |
実行使用メモリ | 89,984 KB |
最終ジャッジ日時 | 2024-05-08 16:13:08 |
合計ジャッジ時間 | 10,815 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | WA | - |
testcase_03 | WA | - |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | WA | - |
testcase_11 | WA | - |
testcase_12 | WA | - |
testcase_13 | WA | - |
testcase_14 | WA | - |
testcase_15 | WA | - |
testcase_16 | WA | - |
testcase_17 | WA | - |
testcase_18 | WA | - |
testcase_19 | WA | - |
testcase_20 | WA | - |
testcase_21 | WA | - |
testcase_22 | WA | - |
testcase_23 | WA | - |
testcase_24 | WA | - |
testcase_25 | WA | - |
testcase_26 | WA | - |
testcase_27 | WA | - |
testcase_28 | WA | - |
testcase_29 | WA | - |
testcase_30 | WA | - |
testcase_31 | WA | - |
testcase_32 | WA | - |
testcase_33 | WA | - |
testcase_34 | WA | - |
testcase_35 | WA | - |
testcase_36 | WA | - |
testcase_37 | WA | - |
testcase_38 | WA | - |
testcase_39 | WA | - |
testcase_40 | WA | - |
testcase_41 | WA | - |
testcase_42 | WA | - |
testcase_43 | WA | - |
testcase_44 | WA | - |
testcase_45 | WA | - |
testcase_46 | WA | - |
testcase_47 | WA | - |
testcase_48 | WA | - |
testcase_49 | WA | - |
testcase_50 | AC | 2 ms
5,376 KB |
testcase_51 | WA | - |
testcase_52 | AC | 2 ms
5,376 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; using int64 = long long; // constexpr int64 MOD = 998244353; constexpr int64 MOD = 1000000007; /* * @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; } //mod間違えてるver. int main() { cin.tie(0);ios::sync_with_stdio(false); int64 N; cin >> N; assert(1<=N && N<=300000); vector<modint> V(N),T(N); for(int i=0;i<N;++i) { int64 t,v; cin >> t >> v; assert(1<=t && t<=1000000000000000000LL); assert(1<=t && v< 998244353); T[i]=t,V[i]=v; } 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; }