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

Задача A. Волшебство на последовательностях

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

1 секунда

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

256 мегабайт

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

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

Первая строка ввода содержит целое число $Q$ — количество запросов к вашей программе.
   Каждая из следующих $Q$ строк описывает очередной запрос и содержит два целых положительных числа — номер столбца и количество предварительных применений заклинания соответственно.

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

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

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

Подзадача 1 (10 баллов) — $1 <= Q <= 10^5, 1 <= i, k <= 5$
Подзадача 2 (10 баллов) — $1 <= Q <= 10^5, 1 <= i <= 10^5, k=1$
Подзадача 3 (20 баллов) — $1 <= Q <= 10^5, 1 <= i,k <= 100$
Подзадача 4 (20 баллов) — $1 <= Q <= 10^5, 1 <= i,k <= 10^3$
Подзадача 5 (40 баллов) — $1 <= Q <= 10^5, 1 <= i,k <= 10^5$

Пример:

Вход

2
2 1
1 3

Ответ

2
1

Замечание

   Напомним, что последовательность - это одномерный массив содержащий целочисленные значения. Один из возможных примеров последовательности размерностью 4 приведен ниже:

1

2

3

4

   Префиксной суммой называется последовательность, где каждый элемент заменен на сумму чисел в соответствующем ему подпоследовательности, с противоположной вершиной в ячейке $(1, 1)$. Формально, определим префиксную сумму последовательности $A$ как последовательность $B$ такую, что для любых $i > 0$ выполняется $$B_i = A_i + B_{i - 1}$$
   В то время как значения в ячейках $B$ с $i = 0$ равны нулю.
   Например префиксной суммой данной последовательности

1

2

0

1

   Будет следующая последовательность:

1

3

3

4

( 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;
}

C++

Copy

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

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

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

#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;
}

C++

Copy