fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
  5. #define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; i--)
  6.  
  7. using ll = long long;
  8.  
  9. template<typename X, typename Y>
  10. bool chmax(X& a, Y b) { return (a < b) ? a = b, 1 : 0; }
  11. template<typename X, typename Y>
  12. bool chmin(X& a, Y b) { return (a > b) ? a = b, 1 : 0; }
  13.  
  14. const int MOD = 1e9 + 7;
  15. inline ll Add(ll a, ll b) { return (a + b) % MOD; }
  16. inline ll Sub(ll a, ll b) { return (a - b + MOD) % MOD; }
  17. inline ll Mul(ll a, ll b) { return a * b % MOD; }
  18.  
  19. const int MAXN = 2e5 + 5;
  20. const int MAXK = 5;
  21.  
  22. int N, Q;
  23. ll A[MAXN];
  24.  
  25. ll C[MAXK+5][MAXK+5], bit[MAXK+5][MAXN];
  26.  
  27. void precompute() {
  28.     FOR(i, 0, MAXK) {
  29.         C[i][0] = 1;
  30.         FOR(j, 1, i) C[i][j] = Add(C[i - 1][j - 1], C[i - 1][j]);
  31.     }
  32. }
  33.  
  34. void add(int m, int p, ll v) {
  35.     v = (v % MOD + MOD) % MOD;
  36.     for (; p <= N; p += p & -p) bit[m][p] += v;
  37. }
  38.  
  39. ll get(int m, int p) {
  40.     ll res = 0;
  41.     for (; p > 0; p -= p & -p) res += bit[m][p];
  42.     return res;
  43. }
  44.  
  45. ll query(int m, int l, int r) {
  46.     return Sub(get(m, r), get(m, l - 1));
  47. }
  48.  
  49. void update(int i, ll x) {
  50.     x = (x % MOD + MOD) % MOD;
  51.     ll P = 1, V = 1;
  52.     FOR(m, 1, MAXK) {
  53.         P = Mul(P, A[i]);
  54.         V = Mul(V, x);
  55.         add(m, i, Sub(V, P));
  56.     }
  57.     A[i] = x;
  58. }
  59.  
  60. void solve() {
  61.     cin >> N >> Q;
  62.     FOR(i, 1, N) {
  63.         cin >> A[i];
  64.         A[i] = (A[i] % MOD + MOD) % MOD;
  65.         add(0, i, 1);
  66.         ll P = 1;
  67.         FOR(m, 1, MAXK) {
  68.             P = Mul(P, A[i]);
  69.             add(m, i, P);
  70.         }
  71.     }
  72.     while (Q--) {
  73.         int type; cin >> type;
  74.         if (type == 1) {
  75.             int i, v; cin >> i >> v;
  76.             update(i, v);
  77.         } else {
  78.             int l, r, k; cin >> l >> r >> k;
  79.             ll S[MAXK+5];
  80.             FOR(m, 0, k) S[m] = query(m, l, r);
  81.             ll ans = 0;
  82.             FOR(m, 0, k) ans = Add(ans, Mul(C[k][m], Mul(S[m], S[k - m])));
  83.             cout << ans << "\n";    
  84.         }
  85.     }
  86. }
  87.  
  88. int main() {
  89.     ios_base::sync_with_stdio(false); cin.tie(NULL);
  90.  
  91.     // freopen("SUM.INP", "r", stdin);
  92.     // freopen("SUM.OUT", "w", stdout);
  93.  
  94.     precompute();
  95.  
  96.     int tests = 1; // cin >> tests;
  97.     while (tests--) solve();
  98.  
  99.     #ifdef LOCAL
  100.     cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
  101.     #endif
  102.     return 0;
  103. }
  104.  
Success #stdin #stdout 0.01s 13752KB
comments (?)
stdin
copy 
3 3
1 2 3
2 1 3 1
1 2 0
2 1 2 2
stdout
copy 
36
6
https://ideone.com/nzpoHH
language:
C++14 (gcc 8.3)
created:
2 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!