問題概要
$N$ 種類の1ドル切手と $ M $ 種類の2ドル切手が販売されている。丁度 $K$ ドル使うような切手の買い方の総数を素数 $ P $ で割った余りを求めよ。
ただしどの種類の切手も無限に存在するとして良い。
制約
- $1 \leq N,M \leq 300$
- $1 \leq K \leq 10^{12}$
- $3 \leq P \leq 10^{6}$
- $P$ は素数
前提知識
導入
数列 $ \{a _ {n} \} $ の第 $n$ 項 $ a _ {n} $ を $x ^ {n}$ の係数とする形式的冪級数
$$ F(x) = a _ {0} + a _ {1} x + a _ {2} x^{2} + \cdots + a _ {n} x^{n} + \cdots $$
を $ \{a _ {n} \} $ の(通常型)母関数と呼ぶ。
代表的な母関数の例として、数列 $\{1,1,\ldots , 1 , \ldots \}$ では
$$ 1 + x + x^{2} + \cdots + x ^ {n} + \cdots = \sum_{n=0}^{\infty} x^{n} = \frac{1}{1-x}$$
のように表される。
形式的冪級数は収束性の議論を無視する(詳しく勉強していないので適切な表現ではない可能性があります)ため、ここでは $ x $ は単なる変数に過ぎず、次のように様々な値への置換を考えることができる。
$x \rightarrow a x(a \neq 0)$ と置換することで、等比数列 $\{a^{0},a^{1},\ldots , a^{n} , \ldots \}$ では
$$ \sum_{n=0}^{\infty} (ax)^{n} = \frac{1}{1-ax}$$
同様に $x \rightarrow x^{k}(k \in \mathbb{N})$ への置換では
$$ \sum _ {n=0}^{\infty} x^{k n}=\frac{1}{1-x^{k}} $$
が得られる。
形式的冪級数 $F=\sum _ {n=0}^{\infty} a_{n} x^{n}$ に対して、形式微分 $ F^{\prime} $ を次のように定義する。
$$ F^{\prime}:=\sum _ {n=1}^{\infty} n \cdot a _ {n} x^{n-1} $$
負の二項係数
$$ \sum _ {n=0}^{\infty}\left(\begin{array}{c} m+n-1 \\ n \end{array}\right) x^{n}=\frac{1}{(1-x)^{m}} $$
が成立する。
証明
組み合わせ的解釈でも導出ができるが、ここでは微分を用いた帰納法で示す。
$ m=d $ での成立を仮定し、$ m=d+1 $ について考える。
$$ \sum _ {n=0}^{\infty}\left(\begin{array}{c} d+n-1 \\ n \end{array}\right) x^{n}=\frac{1}{(1-x)^{d}} $$
の両辺を微分すると、
$$ \sum _ {n=1}^{\infty} \left(\begin{array}{c} d+n-1 \\ n \end{array}\right) n x^{n-1} = \sum _ {n=0}^{\infty} \left(\begin{array}{c} d+n \\ n+1 \end{array}\right) (n+1) x^{n} = d \cdot \frac{1}{(1-x)^{d+1}} $$
より、
$$ \begin{eqnarray} \frac{1}{(1-x)^{d+1}} &=& \sum _ {n=0}^{\infty} \left(\begin{array}{c} d+n \\ n+1 \end{array}\right) \frac{n+1}{d} x^{n} \\ &=& \sum _ {n=0}^{\infty} \left(\begin{array}{c} d+n \\ n \end{array}\right) x^{n} \end{eqnarray} $$
となり、成立が確認できる。
この関係は二項係数から導かれる等式
$$ \sum _ {n=0}^{\infty}\left(\begin{array}{c} m \\ n \end{array}\right) (-x)^{n}= (1-x)^{m} $$
に対応させてしばしば負の二項係数と呼ばれる。
また、左辺に登場する二項係数 $\tbinom{m+n-1}{n}$ は、$ m $ 種類のものから重複を許して $ n $ 個選びとる、重複組合せの総数に対応する。
解法
求める切手の買い方の総数は、
$$ \begin{eqnarray} \frac{1}{(1-x)^{n} (1- x^{2})^{m}} &=& \frac{(1+x) ^ {n}}{(1-x)^{n} (1- x^{2})^{m} (1+x) ^ {n}} \\ &=& \frac{(1+x) ^ {n}}{(1- x^{2})^{n+m}} \\ &=& \sum _ {a=0}^{n} \dbinom{n}{a} x^{a} \sum _ {b=0}^{\infty} \dbinom{ n + m + b - 1}{ n + m - 1} x^{2b} \end{eqnarray} $$
の $ x^{K} $ の係数に等しい。
$a$ を固定して考えると、$b = \frac{K-a}{2}$ となりこれが整数になるような $a$ に対して、
$$ \sum _ {a=0}^{n} \dbinom{n}{a} \dbinom{ n + m + \frac{K-a}{2} - 1}{ n + m - 1} $$
を求めれば良い。
$ K $ が大きく $ P $ が小さいことを利用して Lucasの定理を用いるか、$ O(N+M) $ のループを回すかのいずれかで二項係数を計算する。
実装
#include <bits/stdc++.h> using namespace std; typedef long long int ll; ll mod_pow(ll x,ll n,ll Mod){ x%=Mod; ll res=1; while(n>0){ if(n&1LL)res=res*x%Mod; x=x*x%Mod; n>>=1LL; } return res; } struct perm{ private: int sz; ll mod; public: vector<ll> p,invp; perm(int n,ll Mod){ sz=n+1;mod=Mod; p.resize(sz),invp.resize(sz); p[0]=1; for(int i=1;i<=sz-1;i++){ p[i]=p[i-1]*i%mod; } invp[sz-1]=mod_pow(p[sz-1],mod-2,mod); for(int i=sz-2;i>=0;i--){ invp[i]=invp[i+1]*(i+1)%mod; } } ll comb(ll x,ll y){ if(x<y||y<0)return 0; return (p[x]*invp[x-y]%mod)*invp[y]%mod; } ll comb(ll x,ll y,ll p){ // Lucasの定理 ll res=1; while(x>0 or y>0){ (res*=comb(x%p,y%p))%=p; x/=p; y/=p; } return res; } }; int main(){ int n,m; cin >> n >> m; ll k,p; cin >> k >> p; perm P(p-1,p); ll res=0; for(int i=0;i<=n;i++){ if((k-i)%2==0){ ll tmp=P.comb(n,i,p)*P.comb(n+m+(k-i)/2-1,n+m-1,p)%p; (res+=tmp)%=p; } } cout << res << endl; }
