【HUST網賽 B】Balls

1.​​題目連結​​。距離比賽結束還有1.5H開始看這道題目，當時已經分析出來了是一個組合問題，但是思路錯了，最後找到一個可行的方法，驗證發現需要整數分解，就gg，沒有再仔細地思考下去。

2.分析：其實這個題目就是在說這樣一個事情：

#include<bits/stdc++.h>
using namespace std;
#pragma warning(disable:4996)
#define LL long long
#pragma warning(disable:4996)
const int N = 5e6+10;
LL fac[N];
LL qpow(LL a, LL b, LL mod)
{
  LL res = 1;
  while (b)
  {
    if (b & 1)
      res = res * a%mod;
    a = a * a%mod;
    b >>= 1;
  }
  return res;
}
LL Inv(LL a, LL mod)
{
  return qpow(a, mod - 2, mod);
}
LL C(int n, int m, int mod)
{
  if (m > n) return 0;
  LL ret = fac[n];
  ret *= Inv((fac[m] * fac[n - m]) % mod, mod);
  return ret % mod;
}
LL Lucas(LL n, LL m, LL mod)
{
  if (m == 0) return 1;
  return C(n%mod, m%mod, mod)*Lucas(n / mod, m / mod, mod) % mod;
}
int main()
{
  LL k, s, p;
  fac[0] = 1;
  while (~scanf("%lld%lld%lld",&k,&s,&p))
  {
    for (int i = 1; i <= p; i++) fac[i] = (fac[i - 1] * i) % p;
    printf("%lld\n", Lucas(s+k, 2*k, p));
  }
  return 0;
}