10-11 класс

(Сиқырлы матрица)

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

2 seconds

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

256 megabytes

Жас сиқыршы Асхат жаңа сиқырдың жаңа түрін ойлап тапты — енді ол кез келген матрицаны оның префикс қосындысымен ауыстыра алады!
   Жаңадан меңгерген қабілетіне сенімді болу үшін, ол біраз жаттығамын деп шешті. Ол өлшемдері шексіз үлкен, барлық элементтері $1$ саны болатын матрицаны алып, сол матрицаға өте көп рет жоғарыда айтылған сиқырды қолданды.
   Бұл есепте сіз өзіңіздің бағдарламалау қабілетіңіз сиқырдан еш кем емес екенін дәлелдеу. Сізге саны өте көп сұраулар беріледі. Солардың әрқайсысына бастапқы матрицаға жоғарыда келтірілген сиқырды $k$ рет қолданғаннан кейін, матрицаның $i$-жолындағы және $j$-қатарындағы тұрған санның мәнін анықтаңыз. Ол сан өте үлкен болуы мүмкін болғандықтан 1000000007-ге бөлгендегі қалдығын шығарыңыз.

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

Бірінші жолда жалғыз оң сан $Q \; (1 <= Q <= 10^5)$ берілген — сіздің бағдарламаңызға берілетін сұраулардың саны.
   Келесі берілген $Q$ жолдың әрқайсысы бағдарламаға келген кезекті сұрауды үш сан арқылы сипаттайды: сәйкесінше жол нөмірі $i$, қатар нөмірі $j$ және сиқырдың неше рет қолданылғанын көрсететін сан $k$ $(1 <= i, j, k <= 10^5)$.

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

Келесі $Q$ жолдың әрқайсысында бір саннан шығарыңыз — сиқырды $k$ рет қолданғаннан кейін, матрицаның $i$-жолындағы және $j$-қатарындағы тұрған санның мәннің 1000000007-ге бөлгендегі қалдығы.

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

1-бөлім (10 ұпай) — $1 <= Q <= 10, 1 <= i, j, k <= 100$ 2-бөлім (10 ұпай) — $1 <= i, j, k <= 100$ \par 3-бөлім (10 ұпай) — $1 <= i, j, k <= 10^3$ \par 4-бөлім (10 ұпай) — $i = 1$ немесе $j = 1$ \par 5-бөлім (10 ұпай) — $k = 1$ \par 6-бөлім (50 ұпай) — қосымша шарттарсыз.

Примеры:

\exmpfile{example.01}{example.01.a}% \exmpfile{example.02}{example.02.a}%

Замечание

   Еске сала кетсек, матрица — бүтін сандардан тұратын екі өлшемді массив (басқаша айтқанда, кесте). Мысалы, өлшемі 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();
    }
}