组合数3

• 卢卡斯定理

• 这里求 C 的算法比较朴素，就是我们日常求 C 的方法。比如 $C_4^2$ 就是 4 * 3 / (1 * 2) 。这里直接 for (int i = 1, j = a; i <= b; i ++ , j -- ) ，类似的思路，然后求 j * ksm(i, p - 2, p) 。也就是 j 乘上其逆元。

#include <iostream>
#include <stdio.h>
#include <string.h>

using namespace std;

typedef long long ll;
int p;

ll ksm(ll a, ll b)
{
  ll res = 1;
  while (b)
  {
      if (b & 1)
      {
          res = res * a % p;
      }
      b >>= 1;
      a = a * a % p;
  }

  return res;
}

ll C(int a, int b)
{
  ll res = 1;
  for (ll i = 1, j = a; i <= b; i ++ , j -- )
  {
      res = res * j % p;
      res = res * ksm(i, p - 2) % p;
  }

  return res;
}

ll lucas(ll a, ll b)
{
  if (a < p && b < p) return C(a, b);

  return C(a % p, b % p) % p * lucas(a / p, b / p) % p;
}

int main()
{
  int T;
  cin >> T;
  while (T -- )
  {
      ll a, b;
      cin >> a >> b >> p;
      cout << lucas(a, b) << endl;
  }

  return 0;
}