logoChat01.ai

Гоша купил билет двоичной лотереи. На каждом её би...

Creado el: 20 de julio de 2026

Respondido usando GPT-5.6 Thinking por Chat01

Pregunta

Гоша купил билет двоичной лотереи. На каждом её билете изображена матрица n × m, заполненная единицами и нулями. Организаторы гарантируют, что в лотерее не найдётся двух билетов с
одинаково заполненными матрицами.
Билет считается выигрышным, если в его матрице есть хотя бы один столбец или хотя бы одна
строка, заполненные только единицами. Также выигрышным будет билет, где одновременно заполнены единицами один или несколько столбцов и одна или несколько строк.
Помогите Гоше посчитать, сколько всего есть выигрышных билетов в этой двоичной лотерее.
Так как ответ может быть слишком большим, выведите его по модулю 109 + 7 (то есть выведите
остаток от деления ответа на 109 + 7).
Формат входных данных
В единственной строке содержатся два целых числа n и m (1 ⩽ n, m ⩽ 103
) — размер матрицы
в лотерейном билете.
Формат выходных данных
В единственной строке выведите количество выигрышных билетов по модулю 109 + 7.
Система оценки
Подзадача Баллы Ограничения Необходимые подзадачи
1 5 n = 1, m = 1
2 10 n = 1 1
3 85 полные ограничения 1, 2
Примеры
стандартный ввод стандартный вывод
1 2 3
3 5 16687#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 = 1e3 + 7;
const int MOD = 1e9 + 7;

vector< int > bit(N);

int f(int i) {
return bit[i];
}

void solve() {
bit[1] = 1;
int st = 2;
for (int i = 2; i < N; i++) {
bit[i] = bit[i - 1] + st;
bit[i] %= MOD;
st *= 2;
st %= MOD;
}

int n, m;
cin >> n >> m;

int dp[n + 1][m + 1];
for (int i = 1; i <= n; i++) {
dp[i][1] = f(i);
}
for (int j = 1; j <= m; j++) {
dp[1][j] = f(j);
}

for (int i = 2; i <= n; i++) {
for (int j = 2; j <= m; j++) {
dp[i][j] = dp[i - 1][j] * f(j - 1) + dp[i][j - 1] * f(i - 1);
dp[i][j] %= MOD;
}
}

cout << dp[n][m];
}

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;
}
реши задачу минимально меняя код и надо именно дп

Python

python
MOD=10**9+7
def calc(n,m):
    from math import comb
    s=0
    for i in range(n+1):
        for j in range(m+1):
            if i+j==0: continue
            term=comb(n,i)*comb(m,j)*pow(2,(n-i)*(m-j),MOD)
            if (i+j)%2==1:s+=term
            else:s-=term
    return s%MOD
print(calc(1,2), calc(3,5))

Python

python
for n in range(1,4):
 for m in range(1,4):
  print(n,m,calc(n,m))

Python

python
MOD=10**9+7
def dpcalc(n,m):
    c=[[0]*(m+1) for _ in range(m+1)]
    c[0][0]=1
    for i in range(1,m+1):
        c[i][0]=c[i][i]=1
        for j in range(1,i):
            c[i][j]=(c[i-1][j-1]+c[i-1][j])%MOD
    bit=[0]*(m+1)
    st=1
    for i in range(1,m+1):
        st=st*2%MOD
        bit[i]=(st-1)%MOD
    dp=[0]*(m+1)
    for j in range(1,m+1):
        dp[j]=pow(bit[j],n,MOD)
        for k in range(1,j):
            dp[j]=(dp[j]-c[j][k]*dp[k])%MOD
    return (pow(2,n*m,MOD)-dp[m])%MOD
for n,m in [(1,2),(3,5),(2,2),(3,3)]:
    print(n,m,dpcalc(n,m),calc(n,m))

Pensamiento

Minimizing code changes while maintaining DP

I’m working to craft an answer with minimal changes to the existing code. The idea is to explain why the recurrence is wrong and properly define the DP. I'll switch to a one-dimensional combination array for efficiency, which will also help avoid stack issues with large 2D arrays. The new solution keeps the memory usage to O(m).

Thought for 1m 33s

Respuesta

Текущая рекуррентность пересчитывает матрицы, где одновременно есть единичная строка и единичный столбец. Удобнее посчитать проигрышные билеты с помощью DP.

Инвертируем элементы матрицы. Тогда проигрышный билет превращается в матрицу, в которой каждая строка и каждый столбец содержат хотя бы одну единицу.

Пусть dp[j] — количество таких матриц размера n × j.

Всего матриц без пустых строк:

(2j−1)n(2^j-1)^n

Если в матрице ровно k непустых столбцов, выбираем их C(j,k) способами, а заполнить их можно dp[k] способами. Поэтому:

dp[j]=(2j−1)n−∑k=1j−1C(j,k)⋅dp[k]dp[j]=(2^j-1)^n-\sum_{k=1}^{j-1}C(j,k)\cdot dp[k]

Ответ — все матрицы минус проигрышные.

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 = 1e3 + 7;
const int MOD = 1e9 + 7;

vector<int> bit(N);

int f(int i) {
  return bit[i];
}

int binpow(int a, int b) {
  int result = 1;

  while (b > 0) {
    if (b & 1) {
      result = result * a % MOD;
    }

    a = a * a % MOD;
    b >>= 1;
  }

  return result;
}

void solve() {
  bit[1] = 1;
  int st = 2;

  for (int i = 2; i < N; i++) {
    bit[i] = bit[i - 1] + st;
    bit[i] %= MOD;

    st *= 2;
    st %= MOD;
  }

  int n, m;
  cin >> n >> m;

  // dp[j] — количество n x j матриц
  // без пустых строк и пустых столбцов
  vector<int> dp(m + 1);

  // Текущая строка треугольника Паскаля:
  // c[k] = C(j, k)
  vector<int> c(m + 1);
  c[0] = 1;

  for (int j = 1; j <= m; j++) {
    for (int k = j; k >= 1; k--) {
      c[k] += c[k - 1];
      c[k] %= MOD;
    }

    dp[j] = binpow(f(j), n);

    for (int k = 1; k < j; k++) {
      dp[j] -= c[k] * dp[k] % MOD;

      if (dp[j] < 0) {
        dp[j] += MOD;
      }
    }
  }

  int answer = binpow(2, n * m) - dp[m];

  if (answer < 0) {
    answer += MOD;
  }

  cout << answer << '\n';
}

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

  int tests = 1;
  // cin >> tests;

  while (tests--) {
    solve();
  }

  return 0;
}

Сложность: O(m² + log(nm)), память: O(m).

Compartir este Q&A