9 класс

Есеп A. Сиқыр

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

1 second

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

256 megabytes

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

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

Ең бірінші жолда бір бүтін сан $Q$ — сұраулар саны бар.
   Келесі $Q$ жолда кезекті сұрау сипатталады, әр сұрау екі бүтін сан — элементтің орны мен тізбекке орындалған сиқыр саны жазылған.

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

$Q$ бүтін сан, әр жолда бір-бірден — тізбектің $k$ сиқыр орындағаннан кейінгі $i$-ші 1000000007 санына модульденген элементтің мәнін шығарыңыз.

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

\par Бөлім 1 (10 ұпай) — $1 <= Q <= 10^5, 1 <= i, k <= 5$ \par Бөлім 2 (10 ұпай) — $1 <= Q <= 10^5, 1 <= i <= 10^5, k=1$ \par Бөлім 3 (20 ұпай) — $1 <= Q <= 10^5, 1 <= i, k <= 100$ \par Бөлім 4 (20 ұпай) — $1 <= Q <= 10^5, 1 <= i, k <= 10^3$ \par Бөлім 5 (40 ұпай) — $1 <= Q <= 10^5, 1 <= i, k <= 10^5$

Пример:

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

Замечание

   Ұзындығы 4 болатын сан тізбектің ықтимал түрі: \begin{center} \begin{tabular}{|c|c|c|c|} \hline 1 & 2 & 3 & 4\\ \hline \end{tabular} \end{center}
   Префикс соммасы — тізбектің әр элеметі алғашқы тізбектегі бірінші элементтен сол элементке дейінгі соммаға ауыстырылған сан тізбегі. Ресми түрде, $A$ тізбегінің префикс соммасын $B$ арқылы белгілегенде, әр $i > 0$ үшін $B_i = A_i + B_{i - 1}$ орындалады.
   Мысалға, мына тізбектің префикс соммасы \begin{center} \begin{tabular}{|c|c|c|c|} \hline 1 & 2 & 0 & 1\\ \hline \end{tabular} \end{center}
   Осы тізбек болады: \begin{center} \begin{tabular}{|c|c|c|c|} \hline 1 & 3 & 3 & 4\\ \hline \end{tabular} \end{center} ( Aisultan Kali )

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

кодты корсету/жасыру

#include <bits/stdc++.h>

#define ll long long
#define modw 1000000007

using namespace std;

ll fact[200100];

ll binpow(ll a, ll n)
{
    if(n == 0)
    {
        return 1ll;
    }
    if(n % 2 == 1)
    {
        return (binpow(a, n - 1) * a) % modw;
    }
    if(n % 2 == 0)
    {
        ll t = binpow(a, n / 2) % modw;
        return (t * t) % modw;
    }
}

ll obl(ll a)
{
    return binpow(a, modw - 2) % modw;
}

void factv()
{
    ll ans = 1;
    fact[0] = 1;
    for(ll i = 1; i <= 200005; i++)
    {
        ans = (ans * i) % modw;
        fact[i] = ans;
    }
}

int ff(int n, int k)
{
    return ((fact[n] * obl(fact[n - k])) % modw * obl(fact[k])) % modw;
}

int main()
{
	factv();
    int q;
    cin >> q;
    for(int i = 0; i < q; i++)
    {
        int n, m;
        cin >> n >> m;
        cout << ff(n + m - 1, n - 1) << endl;
    }
    return 0;
}

Докажите пожалуйста это решения

докажите решение

кодты корсету/жасыру

#include <bits/stdc++.h>
#define speed                   \
  ios_base::sync_with_stdio(0); \
  cin.tie(0);                   \
  cout.tie(0);
#define oprecision    \
  cout.precision(30); \
  cerr.precision(7);
#define ll long long
#define ld long double
#define ss string
#define pii pair<int, int>
#define pll pair<ll, ll>
#define forn(n) for (int i = 1; i <= n; i++)
#define forlr(l, r) \
  for (int i = l; (l > r ? i >= r : i <= r); (l > r ? i-- : i++))
#define pb push_back
#define pc __builtin_popcount
#define pcll __builtin_popcountll
#define mp make_pair
#define mt make_tuple
#define F first
#define S second
using namespace std;
const ll mod = 1000000007;
ll q, f[300005];
void init() {
  f[0] = 1;
  for (int i = 1; i <= 300000; i++) f[i] = (f[i - 1] * i) % mod;
}
ll bpow(ll x, ll y) {
  ll res = 1;
  x %= mod;
  while (y > 0) {
    if (y & 1) res = (res * x) % mod;
    y = y >> 1;
    x = (x * x) % mod;
  }
  return res;
}
ll inv(ll n) { return bpow(n, mod - 2); }
ll cnk(ll n, ll r) {
  return (f[n] * inv(f[r]) % mod * inv(f[n - r]) % mod) % mod;
}
int main() {
  speed;
  oprecision;
  // code
  init();
  cin >> q;
  while (q--) {
    ll x, y;
    cin >> x >> y;
    cout << cnk(x + y - 1, x - 1) << "\n";
  }
  // endl
#ifndef ONLINE_JUDGE
  cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
  return 0;
}