Submission #331868

#	Time	Username	Problem	Language	Result	Execution time	Memory
331868		valerikk	Lucky Numbers (RMI19_lucky)	C++14	100 / 100	86 ms	17516 KiB

lucky

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int mod = 1e9 + 7;

void add(int &a, const int &b) {
  a += b;
  if (a >= mod) {
    a -= mod;
  }
}

int mul(const int &a, const int &b) {
  return ll(a) * b % mod;
}

struct mat {
  int x[4][4];

  mat() {
    memset(x, 0, sizeof(x));
  }
};

mat operator*(const mat &a, const mat &b) {
  mat res{};
  for (int i = 0; i < 4; ++i) {
    for (int j = 0; j < 4; ++j) {
      for (int k = 0; k < 4; ++k) {
        add(res.x[i][j], mul(a.x[i][k], b.x[k][j]));
      }
    }
  }
  return res;
}

mat get(int x) {
  mat res{};
  for (int i = 0; i < 4; ++i) {
    const int ls = (i & 1);
    const int last_one = (i >> 1) & 1;
    for (int d = 0; d < 10; ++d) {
      if ((d > x && !ls) || (last_one && d == 3)) {
        continue;
      }
      const int j = (ls | (d < x)) + 2 * (d == 1);
      ++res.x[i][j];
    }
  }
  return res;
}

const int N = (1 << 17);
mat E, D[10];

mat t[2 * N];
int a[N];

void build() {
  for (int i = 0; i < N; ++i) {
    t[i + N] = D[a[i]];
  }
  for (int i = N - 1; i != 0; --i) {
    t[i] = t[i << 1] * t[i << 1 | 1];
  }
}

void modify(int pos, int val) {
  a[pos] = val;
  pos += N;
  t[pos] = D[val];
  for (int i = pos; i != 1; i >>= 1) {
    t[i >> 1] = (i ^ 1) < i ? t[i ^ 1] * t[i] : t[i] * t[i ^ 1];
  }
}

int query(int l, int r) {
  mat resl = E, resr = E;
  l += N, r += N;
  while (l < r) {
    if (l & 1) {
      resl = resl * t[l++];
    }
    if (r & 1) {
      resr = t[--r] * resr;
    }
    l >>= 1;
    r >>= 1;
  }
  const mat res = resl * resr;
  int sum = 0;
  for (int i = 0; i < 4; ++i) {
    add(sum, res.x[0][i]);
  }
  return sum;
}

int main() {
#ifdef ONPC
  freopen("input.txt", "r", stdin);
#endif
  ios::sync_with_stdio(false);
  cin.tie(0);
  for (int i = 0; i < 4; ++i) {
    for (int j = 0; j < 4; ++j) {
      E.x[i][j] = i == j;
    }
  }
  for (int i = 0; i < 10; ++i) {
    D[i] = get(i);
  }
  int n, q;
  string s;
  cin >> n >> q >> s;
  for (int i = 0; i < n; ++i) {
    a[i] = s[i] - '0';
  }
  build();
  cout << query(0, n) << '\n';
  while (q--) {
    int type;
    cin >> type;
    if (type == 1) {
      int l, r;
      cin >> l >> r;
      --l;
      cout << query(l, r) << '\n';
    } else {
      int pos, val;
      cin >> pos >> val;
      --pos;
      modify(pos, val);
    }
  }
  return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 9 / 9
• Subtask 4: 27 / 27
• Subtask 5: 9 / 9
• Subtask 6: 27 / 27