K xüsusi hüceyrə#11455

K xüsusi hüceyrə (Həll təhlili)

Güman edək ki, $w a y s (x, y)$ ways(x, y) matrisdə $(1, 1)$ hüceyrəsindən $(1 + x, 1 + y)$ (1 + x, 1 + y) hüceyrəsinə qədər olan yolların sayını təyin edir. Onda

w a y s (x, y) = C_{x + y}^{x} = C_{x + y}^{y}

ways(x, y) = C_{x + y}^x = C_{x + y}^y

$(1, 1)$ hüceyrəsindən $(n, m)$ hüceyrəsinə qədər xüsusi hüceyrə $(x, y)$ üzərindən keçən yolların sayı $w a y s (x - 1, y - 1) \cdot w a y s (n - x, m - y)$ ways(x - 1, y - 1) \cdot ways(n - x, m - y) bərabərdir. Bu sayını $p$ ilə çoxaltmaqla, $(x, y)$ hüceyrəsi üzərindən keçən bütün yolların cəmi gücünü tapırıq.

Xüsusi hüceyrələrdən keçən yolların gücünü toplamaq qalır. Cavab aşağıdakı cəmlə bərabər olacaq:

i = 1 \sum k w a y s (x_{i} - 1, y_{i} - 1) \cdot w a y s (n - x_{i}, m - y_{i}) \cdot p_{i}

\sum_{i = 1}^k ways(x_i - 1, y_i - 1) \cdot ways(n - x_i, m - y_i) \cdot p_i

Misal

Verilmiş misalda $k = 2$ k = 2 xüsusi hüceyrə müəyyən edilib.

Yalnız bir yol $4$ güclü hüceyrədən keçir.
Yalnız bir yol $7$ güclü hüceyrədən keçir.

Buna görə də, ümumi güc $4 + 7 = 11$ 4 + 7 = 11 bərabərdir.

Alqoritmın həyata keçirilməsi

Aşağıdakı massivləri elan edək:

$f a c t$ mod $M O D$ ilə ədədlərin faktoriallarını saxlayır,
$f a c t in v$ factinv bu faktorialların mod $M O D$ ilə əksini saxlayır:

f a c t [n] = n! m o d 1000000007 f a c t in v [n] = n!^{- 1} m o d 1000000007

fact[n] = n!~mod~1000000007 \\ factinv[n] = n!^{-1}~mod~1000000007

#define MAX 800001
ll fact[MAX], factinv[MAX];

pow funksiyası modül ilə ədədlərin qüvvətini hesablayır: $x^{n} m o d p$ x^n~mod~p.

ll pow(ll x, ll n, ll p)
{
    if (n == 0) return 1;
    if (n % 2 == 0) return pow((x * x) % p, n / 2, p);
    return (x * pow(x, n - 1, p)) % p;
}

inverse funksiyası $x$ ədədinin $p$ sadə modüllü əksini tapır. $p$ sadə ədəd olduğuna görə, kiçik Fermat teoreminə görə:

x^{p - 1} m o d p = 1 b u ¨ t u ¨ n 1 \leq x < p ha l ı n d a

x^{p-1}~mod~p~=~1~bütün~1~\le~x~<~p~halında

Bu $(x \cdot x^{p - 2}) m o d p = 1$ (x \cdot x^{p-2})~mod~p = 1 şəklində yazıla bilər, bu da $x$ -in əksinin $x^{p - 2} m o d p$ x^{p-2}~mod~p olduğunu göstərir.

ll inverse(ll x, ll p)
{
  return pow(x, p - 2, p);
}

Cnk funksiyası binomial əmsalı aşağıdakı formula əsasən hesablayır:

C_{n}^{k} = \frac{n !}{k ! ( n - k )!}

C_n^k = {n! \over k! (n - k)!}

ll Cnk(int n, int k)
{
  return ((fact[n] * factinv[k]) % MOD * factinv[n - k]) % MOD;
}

ways funksiyası $n \times m$ n \times m ölçülü şəbəkədə $(0, 0)$ -dan $(n, m)$ -yə olan yolların sayını hesablayır. Bu nöqtələr arasındakı hər bir yolun uzunluğu $n + m$ n + m-dir və yalnız $m$ üfüqi seqmentləri ehtiva edir, buna görə də yolların sayı $C_{n + m}^{m}$ C_{n+m}^m-dir.

ll ways(int n, int m)
{
  return Cnk(n + m, m);
}

Proqramın əsas hissəsi. Faktoriallar $f a c t$ və əks faktoriallar $f a c t in v$ factinv massivlərini doldururuq.

fact[0] = 1;
for (i = 1; i < MAX; i++)
  fact[i] = (fact[i - 1] * i) % MOD;

factinv[0] = 1;
for (i = 1; i < MAX; i++)
  factinv[i] = inverse(fact[i], MOD);

C++

$t es t s$ testlərini ardıcıllıqla emal edirik.

scanf("%d", &tests);
while (tests--)
{

Cari testin məlumatlarını oxuyuruq.

  scanf("%d %d %d", &n, &m, &k);

Toplanmış gücü $r es$ dəyişənində saxlayırıq.

  res = 0;

$k$ xüsusi hüceyrələri emal edirik.

  for (i = 0; i < k; i++)
  {
    scanf("%d %d %d", &x, &y, &p);
    res = (res + (ways(x - 1, y - 1) * 
                  ways(n - x, m - y)) % MOD * p) % MOD;
  }

Cari test üçün cavabı göstəririk.

  printf("%lld\n", res);
}