逆天組合意義。

題意

形式化題意：給定 \(n,m,u,v\) 求：

數(shù)據(jù)范圍： \(1\le m\le 2\times 10^5,1\le n\le 10^{18},0\le u,v \le 10^9\)。

題解

考慮組合意義，假設(shè)我們現(xiàn)在有一些小球，一共有 \(m\) 類編號，\(\forall i<m\)，編號為 \(i\) 的小球有 \(u\) 種，編號為 \(m\) 的小球有 \(u+v\) 種。
我們?nèi)デ鬂M足以下條件的小球序列的數(shù)量（允許相同編號的同一種球出現(xiàn)多次）：

1. 長度為 \(n+m-1\)。
2. \(\forall i<m\)，編號為 \(i\) 的球至少出現(xiàn)了一個。
3. 記 \(p_i\) 表示編號為 \(i\) 的球出現(xiàn)的第一個位置，特殊地，\(p_0=0,p_m=n+m\)，那么 \(\forall i<m,p_i<p_{i+1}\)。

考慮怎么算這個東西，枚舉 \(p\) 序列，那么：

• 在 \(p_1\) 之前，只能放編號為 \(m\) 的球，方案數(shù)是 \((u+v)^{p_1-1}\)。
• 在 \(p_1\) 這個位置上，只能放編號為 \(1\) 的球，方案數(shù)是 \(u\)。
• 在區(qū)間 \((p_1,p_2)\) ，只能放編號為 \(m\) 或 \(1\) 的球，方案數(shù)是 \((2u+v)^{p_2-p_1-1}\)。
• 在 \(p_2\) 這個位置上，只能放編號為 \(2\) 的球，方案數(shù)是 \(u\)。
  ...
• 在區(qū)間 \((p_{m-1},p_m)\)，什么球都可以放，方案數(shù)是 \((mu+v)^{p_m-p_{m-1}-1}\)。

所以對于一個序列 \(\{p_i\}\) 方案數(shù)是 \(u^{m-1}\prod_{i=1}^m (u\times i+v)^{p_i-p_{i-1}-1}\)。
如果令 \(k_i=p_i-p_{i-1}-1\)，會發(fā)現(xiàn)這個式子剛剛好是原題的答案乘上 \(u^{m-1}\)。

這個第 \(3\) 個限制非常煩人，考慮把它去掉。
注意到前 \(m-1\) 種編號的球除了編號不同外其余性質(zhì)完全一樣，所以任意一個只滿足前兩個限制的序列都可以通過重標號使得他滿足第三個限制。
所以滿足三個限制的序列個數(shù)就是只滿足前兩個限制的序列個數(shù)除以 \((m-1)!\)。

而只滿足前兩個限制的序列個數(shù)通過簡單容斥即可得到，復雜度 \(O(m\log n)\)，\(\log\) 來自快速冪。