歪比歪比¶
题意¶
求满足以下条件的序列对 (A,B) 的个数：
- A,B 中只含 -m 和 1
- A,B 中 -m 的个数的总和为 n
- A 中所有数的和为 S_A，B 中所有数的和为 S_B
- A,B 中任意位置的前缀和都大于 0
多组询问。
解析¶
对于一个只含负数和 1，且所有数总和为 S (S>0) 的 不循环 序列 A，其有恰好 S 个循环同构串的所有前缀和都大于 0。
证明
考虑将 A 循环地写出，即 B=[A_1,A_2,\ldots,A_{|A|},A_1,A_2,\ldots,A_{|A|},A_1,\ldots]。这个循环数列的前缀和可以表示为 s_1,s_2,\ldots,s_1+S,s_2+S,\ldots。
对于 i\in[0,n)，B 从 i+1 开始的长度为 |A| 的子串的所有前缀和都大于 0，当且仅当 \forall j>i,s_j> s_i。这一点很容易理解，因为 S>0，则 \forall j\in[i+1,i+n],s_j>s_i\iff\forall j>i,s_j>s_i。
若 \exists j>i,s_j\le s_i，则一定有 \exists j>i,s_j=s_i，因为 s 总体是增加的，而增加量总是为 1。于是，\forall j>i,s_j>s_i 与 \forall j>i,s_j\neq s_i 是等价的 (因为其中任意一个不成立时，另一个也不成立)。
于是 A 的所有前缀和都大于 0 的循环同构串的个数就是 \sum\limits_{i=0}^{|A|-1}[\forall j>i,s_j\neq s_i]。对于 [0,|A|-1] 范围的所有 s_i 模 S 同余的 i，它们中有且仅有一个能计入答案。因为对于每个 s_i，s_i+S,s_i+2S,s_i+3S,\ldots 总是会出现在前缀和的某个位置。而又由于 s 的增量至多为 1，于是所有 s_i\bmod S 正好构成 S 的完全剩余系，正好有 S 个计入答案。
我们要求出含 n 个 -m，总和为 S 且所有前缀和都大于 0 的序列 A 的个数。在所有含 n 个 -m 且总和为 S 的序列中，每个不循环序列会贡献 \frac{S}{|A|} 至答案，每个循环 x 的序列会贡献 \frac{\frac{S}{x}}{\frac{|A|}{x}}=\frac{S}{|A|} 至答案，故答案为 \frac{S}{|A|}\binom{|A|}{n}。
如果枚举 n 个 -m 中被分配到 A 的个数，我们就可以 O(n) 得到单组询问的答案了。不过我们还发现，每个含 n 个 -m，总和为 S_A+S_B 的合法序列都存在唯一的一个位置 i 满足 s_i=S_A,\forall j>i,s_j\neq S_A，从那里断开可以得到合法的 A 和 B。
实现¶
#include <bits/stdc++.h>
const int maxn = 3e7 + 19, mod = 998244353;
int qpow(int a, int b){
int res = 1;
while(b){
if(b & 1) res = (long long int)res * a % mod;
a = (long long int)a * a % mod, b >>= 1;
}
return res;
}
int fact[maxn], ifact[maxn];
void init(int n){
fact[0] = 1;
for(int i = 1; i <= n; ++i)
fact[i] = (long long int)fact[i - 1] * i % mod;
ifact[n] = qpow(fact[n], mod - 2);
for(int i = n - 1; i >= 0; --i)
ifact[i] = (long long int)ifact[i + 1] * (i + 1) % mod;
}
inline int inv(int n){
return (long long int)ifact[n] * fact[n - 1] % mod;
}
inline int binom(int n, int m){
return (long long int)fact[n] * ifact[n - m] % mod * ifact[m] % mod;
}
int main(){
init(3e7);
int T; std::scanf("%d", &T);
while(T--){
static int n, m, Sa, Sb;
std::scanf("%d%d%d%d", &n, &m, &Sa, &Sb);
int len = n * (m + 1) + Sa + Sb,
ans = (long long int)binom(len, n) * (Sa + Sb) % mod * inv(len) % mod;
std::printf("%d\n", ans);
}
}