結果

問題 No.510 二次漸化式
コンテスト
ユーザー Haar
提出日時 2020-02-09 20:24:06
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 484 ms / 3,000 ms
コード長 9,173 bytes
コンパイル時間 2,268 ms
コンパイル使用メモリ 207,360 KB
最終ジャッジ日時 2025-01-08 23:22:11
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

#ifdef DEBUG
#include <Mylib/Debug/debug.cpp>
#else
#define dump(...) ((void)0)
#endif


template <std::uint32_t M> class ModInt{
public:
  std::uint64_t val;
  ModInt(): val(0){}
  ModInt(std::int64_t n){
    if(n >= M) val = n % M;
    else if(n < 0) val = n % M + M;
    else val = n;
  }
  
  inline constexpr auto operator+(const ModInt &a) const {return ModInt(val + a.val);}
  inline constexpr auto operator-(const ModInt &a) const {return ModInt(val - a.val);}
  inline constexpr auto operator*(const ModInt &a) const {return ModInt(val * a.val);}
  inline constexpr auto operator/(const ModInt &a) const {return ModInt(val * a.inv().val);}
  
  inline constexpr auto& operator=(const ModInt &a){val = a.val; return *this;}
  inline constexpr auto& operator+=(const ModInt &a){if((val += a.val) >= M) val -= M; return *this;}
  inline constexpr auto& operator-=(const ModInt &a){if(val < a.val) val += M; val -= a.val; return *this;}
  inline constexpr auto& operator*=(const ModInt &a){(val *= a.val) %= M; return *this;}
  inline constexpr auto& operator/=(const ModInt &a){(val *= a.inv().val) %= M; return *this;}

  inline constexpr bool operator==(const ModInt &a) const {return val == a.val;}
  inline constexpr bool operator!=(const ModInt &a) const {return val != a.val;}

  inline constexpr auto& operator++(){*this += 1; return *this;}
  inline constexpr auto& operator--(){*this -= 1; return *this;}

  inline constexpr auto operator++(int){auto t = *this; *this += 1; return t;}
  inline constexpr auto operator--(int){auto t = *this; *this -= 1; return t;}

  inline constexpr static auto frac(std::int64_t a, std::int64_t b){
    return ModInt(a) / ModInt(b);
  }
  
  inline constexpr static ModInt power(std::int64_t n, std::int64_t p){
    if(p < 0) return power(n, -p).inv();
    
    ModInt ret = 1, e = n;
    for(; p; e *= e, p >>= 1) if(p & 1) ret *= e;
    return ret;
  }

  inline constexpr auto power(std::int64_t p) const {return power(val, p);}
  
  inline constexpr ModInt inv() const {
    std::int64_t a = val, b = M, u = 1, v = 0;
    
    while(b){
      std::int64_t t = a/b;
      a -= t*b; std::swap(a,b);
      u -= t*v; std::swap(u,v);
    }
    u %= M;
    if(u < 0) u += M;
    
    return u;
  }
};

template <std::uint32_t M> auto operator-(const ModInt<M> &a){return ModInt<M>(-a.val);}

template <std::uint32_t M> auto operator+(std::int64_t a, const ModInt<M> &b){return ModInt<M>(a) + b;}
template <std::uint32_t M> auto operator-(std::int64_t a, const ModInt<M> &b){return ModInt<M>(a) - b;}
template <std::uint32_t M> auto operator*(std::int64_t a, const ModInt<M> &b){return ModInt<M>(a) * b;}
template <std::uint32_t M> auto operator/(std::int64_t a, const ModInt<M> &b){return ModInt<M>(a) / b;}

template <std::uint32_t M> std::istream& operator>>(std::istream &is, ModInt<M> &a){is >> a.val; return is;}
template <std::uint32_t M> std::ostream& operator<<(std::ostream &os, const ModInt<M> &a){os << a.val; return os;}



template <typename Semiring, int N> struct SquareMatrix{
  using value_type = typename Semiring::value_type;
  
  std::array<std::array<value_type, N>, N> matrix;
  
  SquareMatrix(){}
  SquareMatrix(std::initializer_list<std::initializer_list<value_type>> list){
    int i = 0;
    for(auto it1 = list.begin(); it1 != list.end(); ++it1, ++i){
      int j = 0;
      for(auto it2 = it1->begin(); it2 != it1->end(); ++it2, ++j){
        matrix[i][j] = *it2;
      }
    }
  }

  bool operator==(const SquareMatrix &val) const {return matrix == val.matrix;}
  bool operator!=(const SquareMatrix &val) const {return !(*this == val);}

  auto& operator=(const SquareMatrix &val){
    matrix = val.matrix;
    return *this;
  }

  auto& operator+=(const SquareMatrix &val){
    for(size_t i = 0; i < N; ++i){
      for(size_t j = 0; j < N; ++j){
        matrix[i][j] = Semiring::add(matrix[i][j], val[i][j]);
      }
    }
    return *this;
  }

  auto& operator*=(const SquareMatrix &val){
    std::array<std::array<value_type, N>, N> temp;
    for(size_t i = 0; i < N; ++i){
      for(size_t j = 0; j < N; ++j){
        for(size_t k = 0; k < N; ++k){
          temp[i][j] = Semiring::add(temp[i][j], Semiring::mul(matrix[i][k], val[k][j]));
        }
      }
    }
    std::swap(matrix, temp);
    return *this;
  }

  inline const auto& operator[](size_t i) const {return matrix[i];}
  inline auto& operator[](size_t i){return matrix[i];}
  inline int size() const {return N;}
  
  static auto make_unit(){
    SquareMatrix<Semiring, N> ret;
    for(size_t i = 0; i < N; ++i) ret[i][i] = Semiring::id_mul();
    return ret;
  }

  friend auto operator+(const SquareMatrix &a, const SquareMatrix &b){auto ret = a; ret += b; return ret;}
  friend auto operator*(const SquareMatrix &a, const SquareMatrix &b){auto ret = a; ret *= b; return ret;}

  friend auto power(SquareMatrix a, uint64_t p){
    if(p == 0) return make_unit();
    if(p == 1) return a;
  
    auto temp = power(a, p/2);
    auto ret = temp * temp;

    if(p & 1) ret *= a;
 
    return ret;
  }
};





template <typename Monoid>
class SegmentTree{
  using value_type = typename Monoid::value_type;
  
protected:
  const int depth, size, hsize;
  std::vector<value_type> data;

public:
  SegmentTree(int n):
    depth(n > 1 ? 32-__builtin_clz(n-1) + 1 : 1),
    size((1 << depth) - 1),
    hsize(size / 2 + 1),
    data(size + 1, Monoid::id())
  {}

  inline auto operator[](int i) const {return at(i);}
  inline auto at(int i) const {return data[hsize + i];}
  
  inline auto get(int x, int y) const { // [x,y)
    value_type ret_left = Monoid::id();
    value_type ret_right = Monoid::id();
    
    int l = x + hsize, r = y + hsize;
    while(l < r){
      if(r & 1) ret_right = Monoid::op(data[--r], ret_right);
      if(l & 1) ret_left = Monoid::op(ret_left, data[l++]);
      l >>= 1, r >>= 1;
    }
    
    return Monoid::op(ret_left, ret_right);
  }

  inline void update(int i, const value_type &x){
    i += hsize;
    data[i] = x;
    while(i > 1) i >>= 1, data[i] = Monoid::op(data[i << 1 | 0], data[i << 1 | 1]);
  }

  template <typename T>
  inline void init_with_vector(const std::vector<T> &val){
    data.assign(size + 1, Monoid::id());
    for(int i = 0; i < (int)val.size(); ++i) data[hsize + i] = val[i];
    for(int i = hsize-1; i >= 1; --i) data[i] = Monoid::op(data[i << 1 | 0], data[i << 1 | 1]);
  }

  template <typename T>
  inline void init(const T &val){
    init_with_vector(std::vector<value_type>(hsize, val));
  }  

  const auto& debug() const {
    return data;
  }
};



template <typename T>
struct AddMulSemiring{
  using value_type = T;
  constexpr inline static value_type id_add(){return 0;}
  constexpr inline static value_type id_mul(){return 1;}
  constexpr inline static value_type add(const value_type &a, const value_type &b){return a + b;}
  constexpr inline static value_type mul(const value_type &a, const value_type &b){return a * b;}
};

template <typename T, typename = void>
struct ProductMonoid{
  using value_type = T;
  static value_type ONE;
  constexpr inline static value_type id(){return ONE;}
  constexpr inline static value_type op(const value_type &a, const value_type &b){return a * b;}
};

template <typename T>
struct ProductMonoid<T, typename std::enable_if<std::is_arithmetic<T>::value>::type>{
  using value_type = T;
  constexpr inline static value_type id(){return 1;}
  constexpr inline static value_type op(const value_type &a, const value_type &b){return a * b;}
};


template <typename Monoid>
struct DualMonoid{
  using value_type = typename Monoid::value_type;
  constexpr inline static value_type id(){return Monoid::id();}
  constexpr inline static value_type op(const value_type &a, const value_type &b){return Monoid::op(b, a);}
};






using mint = ModInt<1000000007>;
using Mat = SquareMatrix<AddMulSemiring<mint>, 4>;
using Mon = DualMonoid<ProductMonoid<Mat>>;

template <> Mat ProductMonoid<Mat>::ONE = Mat::make_unit();






int main(){
  int n, q;
  while(std::cin >> n >> q){

    SegmentTree<Mon> seg(n);
    std::vector<mint> x(n), y(n);

    for(int i = 0; i < n; ++i){
      Mat t = {
             {1, 0, x[i], 0},
             {0, y[i], 0, 1},
             {0, 2*y[i], y[i]*y[i], 1},
             {0, 0, 0, 1}
      };
      seg.update(i, t);
    }
    

    while(q--){
      char c; std::cin >> c;

      if(c == 'x'){
        int i, v; std::cin >> i >> v;
        x[i] = v;

        Mat t = {
               {1, 0, x[i], 0},
               {0, y[i], 0, 1},
               {0, 2*y[i], y[i]*y[i], 1},
               {0, 0, 0, 1}
        };

        seg.update(i, t);
        
      }else if(c == 'y'){
        int i, v; std::cin >> i >> v;
        y[i] = v;

        Mat t = {
               {1, 0, x[i], 0},
               {0, y[i], 0, 1},
               {0, 2*y[i], y[i]*y[i], 1},
               {0, 0, 0, 1}
        };

        seg.update(i, t);

      }else{
        int i; std::cin >> i;

        auto m = seg.get(0, i);
        mint ans = m[0][0] + m[0][1] + m[0][2] + m[0][3];
        
        std::cout << ans << std::endl;
      }
    }
    
    std::cerr << std::endl;
  }

  return 0;
}
0