Областная олимпиада по информатике 2019 год

Задача A. Волшебство на матрицах

Ограничение по времени:

2 секунды

Ограничение по памяти:

256 мегабайт

Юный волшебник Асхат научился новому заклинанию - теперь он умеет заменять любую матрицу ее префиксной суммой!
   Дабы закрепить новые знания, он решил немного попрактиковаться. Он раздобыл матрицу очень большого размера, каждый элемент которой равен $1$, и очень много раз применил к ней вышеописанное заклинание.
   В этой задаче вам предстоит показать, что ваши навыки программирования ничем не уступуают магии. На каждый соответствующий запрос, а их будет очень много, найдите чему было равно число в $i$-м ряду в $j$-й строке матрицы после $k$ применений заклинания. Поскольку эти числа могут быть довольно большими, выведите остаток от их деления на 1000000007.

Формат входного файла

Первая строка содержит целое положительное число $Q \; (1 <= Q <= 10^5)$ — количество запросов к вашей программе.
   Каждая из следующих $Q$ строк описывает очередной запрос и содержит три целых положительных числа — номер строки $i$, номер столбца $j$ и количество предварительных применений заклинания $k$ $(1 <= i, j, k <= 10^5)$ соответственно.

Формат выходного файла

Выведите $Q$ целых чисел, по одному в строке — значение в ячейке в $i$-м ряду в $j$-й строке матрицы после $k$ применений заклинания, взятое по модулю 1000000007.

Система оценки

Подзадача 1 (10 баллов) — $1 <= Q <= 10, 1 <= i, j, k <= 100$
Подзадача 2 (10 баллов) — $1 <= i, j, k <= 100$
Подзадача 3 (10 баллов) — $1 <= i, j, k <= 10^3$
Подзадача 4 (10 баллов) — $i = 1$ или $j = 1$
Подзадача 5 (10 баллов) — $k = 1$
Подзадача 6 (50 баллов) — без дополнительных ограничений

Примеры:

Вход

2
2 3 1
1 1 3

Ответ

6
1

Вход

3
4 5 7
3 3 3
2 1 10

Ответ

39600
100
11

Замечание

   Напомним, что матрица - это двумерный массив (иначе говоря, таблица) содержащий целочисленные значения. Один из возможных примеров матрицы 3x4 приведен ниже: \begin{center} \begin{tabular}{|c|c|c|c|} \hline 1 & 2 & 3 & 4\\ \hline 4 & 7 & 0 & -2\\ \hline 5 & 9 & 2 & 6\\ \hline \end{tabular} \end{center}
   Префиксной суммой называется матрица, где каждый элемент заменен на сумму чисел в соответствующуем ему прямоугольнике с противоположной вершиной в $(1, 1)$. Более формально, определим префиксную сумму матрицы $A$ как матрицу $B$ такую, что для любых $i > 0, \; j > 0$ выполняется \[B_{i, j} = A_{i, j} + B_{i - 1, j} + B_{i, j - 1} - B_{i - 1, j - 1}\]
   В то время как значения в ячейках $B$ с $i = 0$ или $j = 0$ равны нулю.
   Например перфиксной суммой данной матрицы \begin{center} \begin{tabular}{|c|c|c|c|} \hline 1 & 2 & 0 & 1\\ \hline 4 & 1 & 5 & 9\\ \hline 3 & 2 & 6 & 1\\ \hline 0 & 7 & 2 & 4\\ \hline \end{tabular} \end{center}
   Будет следующая матрица: \begin{center} \begin{tabular}{|c|c|c|c|} \hline 1 & 3 & 3 & 4\\ \hline 5 & 8 & 13 & 23\\ \hline 8 & 13 & 24 & 35\\ \hline 8 & 20 & 33 & 48\\ \hline \end{tabular} \end{center} ( Sanjar Bidaibek )

Комментарий/решение

eto zhe cnk + teorema ferma.

сореее(((

показать/скрыть код

#include <bits/stdc++.h>

using namespace std;

#define fori(x, y) for(int i = x; i<y; i++)
#define forj(x, y) for(int j = x; j<y; j++)

int main(){
	int t;
	cin >> t;
	while(t--){
		int n, m, k, ans = 0;
		cin >> n >> m >> k;
		vector<vector<int> > a(n, vector<int>(m, 1));
		
		
		while(k--){
				fori(0, n){
					forj(1, m){
						a[i][j] += a[i][j-1];
					}
				}
			
			fori(1, n){
				forj(0, m){
					a[i][j] += a[i-1][j];
				}
			}
			
			fori(0, n){
				forj(0, m){
					ans += a[i][j];
				}
			}
		}
		
		
		cout << a[n-1][m-1] << endl;
	}
}

$$ans = C_{i + k - 1}^{k} * C_{j + k - 1}^{k}$$

Конечно с остатком от деления 1000000007

показать/скрыть код

#include <bits/stdc++.h>

#define int long long
#define vt vector
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define ff first
#define ss second
#define dbg(x) cerr << #x << " = " << x << '\n'

using namespace std;
using ll = long long;
using pii = pair<int, int>
using vvi = vt< vt<int> >

const int N = 1e6 + 5, mod = 1e9 + 7, inf = 1e18 + 7, B = 500, LIM = (1ll << 60);
const double eps = 1e-6;

int fact[N], inv[N];

int bp (int n, int k) {
	int res = 1;
	while (k) {
		if (k & 1) res = (res % mod) * (n % mod) % mod;
		n = (n % mod) * (n % mod) % mod;
		k >>= 1;
	}
	return res;
}

int C (int n, int k) {
	if (n < k) return 0;
	if (k == 0) return 1;
	int x = fact[n];
	x = (x * inv[k]) % mod;
	x = (x * inv[n - k]) % mod;
	return x;
}

void solve () {
	int i, j, k;
	cin >> i >> j >> k;
	int x = C(j + k - 1, k);
	int y = C(i + k - 1, k);
	x = (x * y) % mod;
	cout << x;		
	cout << '\n';	
}

bool testcases = 1;

signed main() {
    cin.tie(0) -> sync_with_stdio(0);
    fact[0] = inv[0] = 1;
    for (int i = 1; i < N; i++) fact[i] = (fact[i - 1] * i) % mod;
    for (int i = 1; i < N; i++) inv[i] = bp(fact[i], mod - 2);
    int test = 1;
    if (testcases) cin >> test;
    for (int cs = 1; cs <= test; cs++) {
        solve();
    }
}