【BZOJ 2142 】禮物

1.​​題目連結​​。首先物品總量大于等于需求就可滿足條件，否則才是Impossible。然後就是簡單的推理了，高中組合數問題： 首先給第一個人配置設定，C(n,w1),第二個人：C(n-w1,w2)....第i個人：C(n-sum(wi),wi+1).根據分步乘法，答案就是這些數乘起來。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int SIZE = 300;
ll A, B, Mod, m[SIZE], r[SIZE];
inline void input(void)
{
  scanf("%lld%lld%lld", &A, &B, &Mod);
  //計算C(A,B)%Mod
}
inline ll power(ll a, ll b, ll p)
{
  ll res = 1;
  while (b)
  {
    if (1 & b)res = res * a % p;
    b >>= 1;
    a = a * a % p;
  }
  return res;
}
inline ll Exeuclid(ll a, ll& x, ll b, ll& y, ll c)
{
  if (!b) { x = c / a, y = 0; return a; }
  else
  {
    ll p = Exeuclid(b, x, a % b, y, c);
    ll x_ = x, y_ = y;
    x = y_, y = x_ - a / b * y_;
    return p;
  }
}
inline ll inv(ll a, ll p)
{
  ll x_, y_;
  Exeuclid(a, x_, p, y_, 1);
  return (x_ + p) % p;
}
//計算x!中除去val後模p意義下的值,val是一個素數。
inline ll calc(ll x, ll val, ll p)
{
  if (!x)return 1;
  ll res = 1, last = x % p;
  for (ll i = 1; i <= p; i++)
    if (i % val)res = res * i % p;
  res = power(res, x / p, p);
  for (ll i = 1; i <= last; i++)
    if (i % val)res = res * i % p;
  return res * calc(x / val, val, p) % p;
}
//計算 C(A,B,prime,prime^k)
inline ll C(ll d, ll u, ll val, ll Pow)
{
  if (u > d)return 0;
  ll mulup = calc(d, val, Pow), k = 0;
  ll muldown1 = calc(u, val, Pow), muldown2 = calc(d - u, val, Pow);
  //計算該
  for (ll i = d; i; i /= val)k += i / val;
  for (ll i = u; i; i /= val)k -= i / val;
  for (ll i = d - u; i; i /= val)k -= i / val;
  //計算剩餘的val的指數
  return mulup * inv(muldown1, Pow) % Pow * inv(muldown2, Pow) % Pow * power(val, k, Pow) % Pow;
}
inline ll CRT(int cnt)
{
  ll m_ = Mod, M[SIZE] = {}, t[SIZE] = {}, res = 0;
  for (int i = 1; i <= cnt; i++)
    M[i] = m_ / m[i];
  for (int i = 1; i <= cnt; i++)
  {
    ll y;
    Exeuclid(M[i], t[i], m[i], y, 1);
    res = (res + r[i] % m_ * M[i] % m_ * t[i] % m_) % m_;
  }
  return (res % m_ + m_) % m_;
}
inline ll Exlucas(void)
{
  memset(m, 0, sizeof(m));
  memset(r, 0, sizeof(r));
  int temp = Mod, cnt = 0;
  for (ll i = 2; i * i <= Mod; i++)
  {
    if (temp % i == 0)
    {
      m[++cnt] = 1;
      while (temp % i == 0)
        temp /= i, m[cnt] *= i;
      r[cnt] = C(A, B, i, m[cnt]);
    }
  }
  if (temp > 1) m[++cnt] = temp, r[cnt] = C(A, B, temp, m[cnt]);
  return CRT(cnt);
}
int W[110];
int main()
{
  scanf("%d", &Mod);
  int n, m;
  scanf("%d%d", &n, &m);
  ll sum = 0;
  for (int i = 1; i <= m; i++)
  {
    scanf("%d", &W[i]);
    sum += W[i];
  }
  ll ans =1;
  A = n;
  if (sum > n)
  {
    puts("Impossible");
    return 0;
  }
  for (int i = 1; i <= m; i++)
  {
    B = W[i];
    ans = (ans*Exlucas()) % Mod;
    A -= W[i];
  }
  printf("%lld\n", ans % Mod);

  return 0;
}