logoChat01.ai

JATC любит Бань-ми (вьетнамское блюдо). Его привяз...

Creado el: 10 de agosto de 2026

Respondido usando GPT-5.6 Thinking por Chat01

Pregunta

JATC любит Бань-ми (вьетнамское блюдо). Его привязанность к Бань-ми настолько велика, что он ест Бань-ми каждый день на завтрак. Сегодня утром, как обычно, он купил Бань-ми, но собирается насладиться им необычным образом.

Сначала, он разбивает Бань-ми на n
кусочков, выкладывает их в ряд и нумерует от 1
до n
. Для каждого кусочка i
он определяет его вкусность как xi∈{0,1}
. JATC собирается съесть все кусочки один за другим. Каждый раз он выбирает произвольный из оставшихся кусочков и съедает его. Пусть этот кусочек был под номером i
, тогда его удовольствие от Бань-ми увеличивается на xi
, вкусность каждого из оставшихся кусочков также увеличивается на xi
. Изначально удовольствие JATC равно 0
.

Например, пусть есть 3
кусочка с вкусностями [0,1,0]
. Если JATC съест второй кусочек, то его удовольствие станет равно 1
, а вкусность оставшихся кусочков будет равна [1,,1]
. Затем, если он съест первый кусочек, то его удовольствие станет равна 2
, а вкусность оставшихся кусочков станет [,_,2]
. После того как JATC съест последний кусочек, его удовольствие станет равно 4
.

Однако JATC не хочет съесть сразу все кусочки, оставив часть на будущее. Он дал вам q
запросов, каждый из которых задаётся двумя целыми числам li
и ri
. Для каждого запроса выясните какое наибольшее удовольствие он может получить, если съест все кусочки в отрезке [li,ri]
в каком-то порядке.

Все запросы независимы друг от друга. Так как ответ на запрос может быть очень большим, выведите его по модулю 109+7
.

Входные данные
Первая строка содержит два целых числа n
и q
(1≤n,q≤100000
).

Вторая строка содержит строку из n
символов, каждый из которых равен или '0' или '1'. Символ под номером i
определяет вкусность i
-го кусочка.

Каждая из следующих q
строк содержит по два целых числа li
или ri
(1≤li≤ri≤n
) — отрезок соответствующего запроса.

Выходные данные
Выведите q
строчек, где i
-я из них содержит одно целое число — ответ на i
-й запрос по модулю 109+7
.

Примеры
Входные данныеСкопировать
4 2
1011
1 4
3 4
Выходные данныеСкопировать
14
3
Входные данныеСкопировать
3 2
111
1 2
3 3
Выходные данныеСкопировать
3
1
Примечание
В первом примере:

В запросе 1
, одним из оптимальных порядков поедания является следующий: 1
, 4
, 3
, 2
.
В запросе 2
: и порядок 3
, 4
, и порядок 4
, 3
приводят к одному и тому же ответу.
Во втором примере любой порядок поедания кусочков приведёт к одному и тому же ответу.

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

using i128 = __int128;
using ld = long double;
const int INF = 1e15;
const int N = 1e6 + 7;
const int MOD = 1e9 + 7;

void solve() {
int n, q;
cin >> n >> q;
string s;
cin >> s;
vector< int > pref(n + 1);
for (int i = 1; i <= n; i++) {
pref[i] = pref[i - 1] + (s[i - 1] - '0');
}

while (q--) {
int l, r;
cin >> l >> r;
int x = r - l + 1;
int y = x - (pref[r] - pref[l - 1]);
cout << ((x * (x + 1) * (x + 2) / 6) - (y * (y + 1) / 2)) % MOD << "\n";
}
}

int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
srand(time(0));
int tests = 1;
//cin >> tests;
while (tests--) {
solve();
}

return 0;
}
в формуле есть небольшая ошибка исправь ошибку не меняя рнешения и решая формулой + минимально изменить элементы в коде

Pensamiento

Deriving the formula

I’m modeling each eaten piece’s value as its initial bit plus the accumulated total. This doubles the running score, so ordering all ones first maximizes it, giving 2m−2m−k2^m-2^{m-k}, where kk is the number of ones.

Derived the formula

Worked for 11s

Respuesta

У тебя сама идея с префиксными суммами правильная: для каждого запроса достаточно знать длину отрезка и количество нулей/единиц. Ошибка только в формуле ответа.

Если до поедания очередного кусочка текущее удовольствие равно S, а исходная вкусность кусочка равна a ∈ {0,1}, то при его поедании:

Snew=S+(a+S)=2S+a.S_{\text{new}}=S+(a+S)=2S+a.

Поэтому единицы выгодно есть раньше нулей. Если длина отрезка x, а количество нулей y, то количество единиц равно x-y, и максимальный ответ:

2x−2y.2^x-2^y.

Например, для 1011: x=4, y=1:

24−21=16−2=14.2^4-2^1=16-2=14.

Минимально исправленный код:

cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;

using i128 = __int128;
using ld = long double;
const int INF = 1e15;
const int N = 1e6 + 7;
const int MOD = 1e9 + 7;

void solve() {
  int n, q;
  cin >> n >> q;
  string s;
  cin >> s;

  vector<int> pref(n + 1);
  for (int i = 1; i <= n; i++) {
    pref[i] = pref[i - 1] + (s[i - 1] - '0');
  }

  // единственное необходимое добавление
  vector<int> pw(n + 1, 1);
  for (int i = 1; i <= n; i++) {
    pw[i] = pw[i - 1] * 2 % MOD;
  }

  while (q--) {
    int l, r;
    cin >> l >> r;

    int x = r - l + 1;
    int y = x - (pref[r] - pref[l - 1]);

    cout << (pw[x] - pw[y] + MOD) % MOD << "\n";
  }
}

int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  int tests = 1;
  while (tests--) {
    solve();
  }

  return 0;
}

То есть твоя строка

cpp
cout << ((x * (x + 1) * (x + 2) / 6) - (y * (y + 1) / 2)) % MOD << "\n";

заменяется на

cpp
cout << (pw[x] - pw[y] + MOD) % MOD << "\n";

Остальная логика решения остаётся той же: prefix sums + O(1) на запрос, итоговая сложность O(n + q).

Compartir este Q&A