Submission #494476

#	Time	Username	Problem	Language	Result	Execution time	Memory
494476		Pety	Lucky Numbers (RMI19_lucky)	C++14	100 / 100	123 ms	26928 KiB

lucky

#include <bits/stdc++.h>
#define ll long long
#define ld long double

using namespace std;

const ll mod = 1e9 + 7;
const ll INF = 1e9;

int n;

struct node {
  bool has13;
  int st, dr;
  int cnt[4][4];
} aint[400002];

int v[100002];

int smaller[100002][4][4], q;

node merge (node fiu1, node fiu2) {
  node p;
  p.has13 = fiu1.has13 | fiu2.has13 | (v[fiu1.dr] == 1 && v[fiu2.st] == 3);
  /// caz1 prima bucata e mai mica
  memset(p.cnt, 0, sizeof(p.cnt));
  for (int i = 1; i <= 3; i++)
    for (int j = 1; j <= 3; j++)
      for (int k = 1; k <= 3; k++)
        for (int t = 1; t <= 3; t++) {
          if (j == 1 && k == 3)
            continue;
          p.cnt[i][t] += 1ll * fiu1.cnt[i][j] * smaller[fiu2.dr - fiu2.st + 1][k][t] % mod;
          // if (fiu1.dr == 2) {
          //   cout << i << " " << t << "\n";
          //   cout << i << " " << j << " " << fiu1.cnt[i][j] << "\n";
          //   cout << k << " " << t << " " << smaller[fiu2.dr - fiu2.st + 1][k][t] << "\n";
          //   cout << 1ll * fiu1.cnt[i][j] * smaller[fiu2.dr - fiu2.st + 1][k][t] << "\n\n";
          // }
          // assert(p.cnt[i][j] >= 0);
          if (p.cnt[i][t] >= mod)
            p.cnt[i][t] -= mod;
        }
  int c1 = v[fiu1.st];
  if (c1 != 1 && c1 != 3) c1 = 2;
  int c2 = v[fiu1.dr];
  if (c2 != 1 && c2 != 3) c2 = 2;
  if (fiu1.has13 == 0)
    for (int i = 1; i <= 3; i++)
      for (int j = 1; j <= 3; j++) {
        if (c2 == 1 && i == 3)
          continue;
        p.cnt[c1][j] += fiu2.cnt[i][j];
        if (p.cnt[c1][j] >= mod)
          p.cnt[c1][j] -= mod;
      }
 // int c3 = v[fiu2.dr];
  //if (c3 != 1 && c3 != 3) c3 = 2;
  //if (!p.has13) {
    //p.cnt[c1][c3]++;
    //if (p.cnt[c1][c3] >= mod) p.cnt[c1][c3] -= mod;
  //}
  p.st = fiu1.st;
  p.dr = fiu2.dr;
  return p;
}

void update (int nod, int st, int dr, int poz, int a) {
  if (st == dr) {
    memset(aint[nod].cnt, 0, sizeof(aint[nod].cnt));
    aint[nod].has13 = 0;
    for (int i = 0; i < a; i++)
      if (i == 1 || i == 3)
        aint[nod].cnt[i][i] = 1;
      else
        aint[nod].cnt[2][2]++;
    return;
  }
  int mid = (st + dr) / 2;
  if (poz <= mid)
    update(2 * nod, st, mid, poz, a);
  else
    update(2 * nod + 1, mid + 1, dr, poz, a);
  aint[nod] = merge(aint[2 * nod], aint[2 * nod + 1]);
}

void build (int nod, int st, int dr) {
  aint[nod].st = st;
  aint[nod].dr = dr;
  if (st == dr) {
    memset(aint[nod].cnt, 0, sizeof(aint[nod].cnt));
    aint[nod].has13 = 0;
    for (int i = 0; i < v[st]; i++)
      if (i == 1 || i == 3)
        aint[nod].cnt[i][i] = 1;
      else
        aint[nod].cnt[2][2]++;
    return;
  }
  int mid = (st + dr) / 2;
  build(2 * nod, st, mid);
  build(2 * nod + 1, mid + 1, dr);
  aint[nod] = merge(aint[2 * nod], aint[2 * nod + 1]);
}

node ans;

void query (int nod, int st, int dr, int a, int b) {
  if (a <= st && dr <= b) {
    if (ans.st == 0) 
      ans = aint[nod];
    else
      ans = merge(ans, aint[nod]);
    return;
  }
  int mid = (st + dr) / 2;
  if (a <= mid)
    query(2 * nod, st, mid, a, b);
  if (mid < b)
    query(2 * nod + 1, mid + 1, dr, a, b);
}

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  cin >> n >> q;
  smaller[1][1][1] = 1;
  smaller[1][3][3] = 1;
  smaller[1][2][2] = 8;
  for (int i = 2; i <= n; i++) {
    for (int j = 1; j <= 3; j++)
      for (int k = 1; k <= 3; k++)
        for (int t = 1; t <= 3; t++) {
          if (k == 1 && t == 3)
            continue;
          smaller[i][j][t] += 1ll * smaller[i - 1][j][k] * ((t == 1 || t == 3) ? 1 : 8) % mod;
          if (smaller[i][j][t] >= mod)
            smaller[i][j][t] -= mod;
          //assert(smaller[i][j][t] >= 0);
        }
  }
  string s;
  cin >> s;
  for (int i = 0; i < n; i++)
    v[i + 1] = s[i] - '0';
  build(1, 1, n);
  int sol = 0;
  for (int i = 1; i <= 3; i++)
    for (int j = 1; j <= 3; j++) {
     // assert(aint[1].cnt[i][j] >= 0);
      sol = (sol + aint[1].cnt[i][j]);
      if (sol >= mod) sol -= mod;
    }
  
  cout << (sol + !aint[1].has13) % mod << "\n";
 
  while (q--) {
    int t, x, y;
    cin >> t >> x >> y;
    if (t == 1) {
      ans.st = 0;
      query(1, 1, n, x, y);
      int sol = 0;
      for (int i = 1; i <= 3; i++)
        for (int j = 1; j <= 3; j++) {
          sol = (sol + ans.cnt[i][j]);
          if (sol >= mod) sol -= mod;
        }
      cout << (sol + !ans.has13) % mod << "\n";
    }
    else {
      v[x] = y;
      update(1, 1, n, x, y);
    }
  }
  
    
  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