T1、Count
求有多少有序 (k) 元组满足 (sum_{i = 1}^k a_i = n) 且不存在 (a_i equiv 0 mod m)，答案 (mod 998244353)。((n le 10^{18}, m leq 5 imes 10 ^3, k leq 2 imes 10 ^ 3))
(Sol)：
记 (A = sum_{i = 1}^{k} a_i mod m equiv n mod m)，由于 (a_i mod m) 不会超过 (m - 1)，所以 (sum_{i = 1} ^ k a_i) 不会超过 (k (m - 1))，那么 (A) 最多有 (k) 中取值，不妨枚举这 (k) 个 (A)。这样一来就有 ((n - A) / m) 个 (m) 可以随机分配，这个可以用隔板法计算；对于 (A) 的分配可以枚举有多少数大于 (m - 1) 来容斥。
时间复杂度 (O(km))。
(Source)：
#include <cstdio>
#include <cstring>
#include <algorithm>
typedef long long ll;
int in() {
int x = 0; char c = getchar(); bool f = 0;
while (c < '0' || c > '9')
f |= c == '-', c = getchar();
while (c >= '0' && c <= '9')
x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
return f ? -x : x;
}
ll lin() {
ll x = 0; char c = getchar(); bool f = 0;
while (c < '0' || c > '9')
f |= c == '-', c = getchar();
while (c >= '0' && c <= '9')
x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
return f ? -x : x;
}
template<typename T>inline void chk_min(T &_, T __) { _ = _ < __ ? _ : __; }
template<typename T>inline void chk_max(T &_, T __) { _ = _ > __ ? _ : __; }
const int N = 1e7 + 5, mod = 998244353;
ll n;
int m, k, fac[N], inv[N];
int qpow(int base, int b, int ret = 1) {
for (; b; b >>= 1, base = 1ll * base * base % mod)
if (b & 1)
ret = 1ll * ret * base % mod;
return ret;
}
void prep() {
fac[0] = inv[0] = 1;
for (int i = 1; i < N; ++i)
fac[i] = 1ll * fac[i - 1] * i % mod;
inv[N - 1] = qpow(fac[N - 1], mod - 2);
for (int i = N - 2; i; --i)
inv[i] = 1ll * inv[i + 1] * (i + 1) % mod;
}
inline int C(const int n, const int m) {
if (n < m)
return 0;
return 1ll * fac[n] * inv[m] % mod * inv[n - m] % mod;
}
int calc(int A) {
int ret = 0, lim = std::min(A / (m - 1), k);
for (int i = 0; i <= lim; ++i) {
ret += (i & 1 ? -1ll : 1ll) * C(k, i) * C(A - i * (m - 1) - 1, k - 1) % mod;
if (ret >= mod)
ret -= mod;
if (ret < 0)
ret += mod;
}
return ret;
}
int work() {
int ret = 0, tmp;
for (int A = n % m; A <= n && A <= k * (m - 1); A += m) {
tmp = inv[k - 1];
for (ll i = (n - A) / m + k - 1; i >= (n - A) / m + 1; --i)
tmp = i % mod * tmp % mod;
ret += 1ll * tmp * calc(A) % mod;
if (ret >= mod)
ret -= mod;
}
return ret;
}
int main() {
//freopen("in", "r", stdin);
freopen("count.in", "r", stdin);
freopen("count.out", "w", stdout);
n = lin(), m = in(), k = in();
prep();
printf("%d
", work());
return 0;
}
T2、普及组
给定一个数 (x) (数据中已给出)，(T (T leq 2 imes 10 ^ 5)) 组询问，每组询问求大小为 (n imes n (n leq 5 imes 10 ^ 6)) 的好矩阵，好矩阵需满足：
1、矩阵里的数都是整数；
2、(forall j, prod_{i = 1} ^ n a_{i , j} = x)；
3、(forall j, prod_{i = 1} ^ n a_{j , i} = x)。
答案 (mod 998244353)。
(Sol)：
观察(打表)发现，(x) 的质因子指数不超过 (2)。
因为每个质因子是独立的，单独考虑贡献。
若质因子指数不超过 (1)，则方案数显然为 (n!)；
否则可以将问题转化为：在 (n imes n) 的矩阵中填数字，保证每行每列和都为 (2)。
记 (f_i , g_i) 表示 (i imes i) 的矩阵中最后一列填了两个 (1) 或一个 (2) 的方案数。
转移时考虑多加一行一列；
(g) 的转移是显然的：
(f) 的转移可以考虑 (i imes i) 的矩阵中删掉一列一行 (不妨设是最后一列)：
答案即为 (f_n + g_n)。
时间复杂度 (O(T log_2 n + n))。
(Source)：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
typedef long long ll;
int in() {
int x = 0; char c = getchar(); bool f = 0;
while (c < '0' || c > '9')
f |= c == '-', c = getchar();
while (c >= '0' && c <= '9')
x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
return f ? -x : x;
}
ll lin() {
ll x = 0; char c = getchar(); bool f = 0;
while (c < '0' || c > '9')
f |= c == '-', c = getchar();
while (c >= '0' && c <= '9')
x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
return f ? -x : x;
}
template<typename T>inline void chk_min(T &_, T __) { _ = _ < __ ? _ : __; }
template<typename T>inline void chk_max(T &_, T __) { _ = _ > __ ? _ : __; }
const int N = 5e6 + 5, mod = 998244353;
ll x;
int T, n, f[N], g[N], fac[N], cnt[3];
int qpow(int base, int b, int ret = 1) {
for (; b; base = 1ll * base * base % mod, b >>= 1)
if (b & 1)
ret = 1ll * ret * base % mod;
return ret;
}
void prep() {
for (ll i = 2; i * i <= x; ++i)
if (x % i == 0) {
int tmp = 0;
while (x % i == 0)
x /= i, ++tmp;
++cnt[tmp];
}
if (x > 1)
++cnt[1];
g[1] = fac[0] = fac[1] = 1;
for (int i = 2; i < N; ++i) {
fac[i] = 1ll * fac[i - 1] * i % mod;
g[i] = 1ll * (g[i - 1] + f[i - 1]) * i % mod;
f[i] = 1ll * (1ll * f[i - 1] + f[i - 1] + g[i - 1]) * i % mod * (i - 1) % mod * 499122177ll % mod;
}
}
int main() {
//freopen("in", "r", stdin);
freopen("pj.in", "r", stdin);
freopen("pj.out", "w", stdout);
x = lin(), T = in();
prep();
while (T--) {
n = in();
printf("%lld
", 1ll * qpow(f[n] + g[n], cnt[2]) * qpow(fac[n], cnt[1]) % mod * qpow(2, 1ll * (n - 1) * (n - 1) % (mod - 1)) % mod);
}
return 0;
}
T3、提高组
求 (1) ~ (n (n leq 10 ^ 7）)的排列中，确定 (a_x = y) 后最长下降子序列不超过 (2) 的方案数，(T (T leq 10 ^ 6)) 组询问，答案对 (10 ^ 9 + 7) 取余。
(Sol)：
这个排列的前缀 (max) 序列一定与满足条件的排列一一对应，证明：
考虑对前缀 (max) 中发生变化的位置，这些位置上的数一定是递增的，对于其中一个位置上的数，在它之后出现比他小的数一定也是单调递增的，所以有：
1、一个排列一定对应它的前缀 (max) 序列；
2、排列中没有对前缀 (max) 序列造成影响的数也是确定的。
(QED)
分类讨论：
当(y geq x)，那么 (y) 一定对 (max) 造成影响，可以考虑反证：
假设 (y) 未造成影响，则在它之前一定有一个大于它的数；
为了满足题意，小于 (y) 的数一定在它之前，由于 (y - 1 > x - 2)，所以假设不成立。
当 (y < x)，显然 (y) 不对 (max) 造成影响；
可以考虑排列的逆转置 (A^{-1}[y] = x)，还是只用考虑 (y geq x) 的情况。
整理一下就是求：
1、(max_i geq i)
2、(max_i geq max_{i - 1})
3、(max_n = n)
(max) 的方案数，放在平面上折线法计数就行了。
时间复杂度 (O(n + T))。
(Source)：
#include <cstdio>
#include <cstring>
#include <algorithm>
typedef long long ll;
int in() {
int x = 0; char c = getchar(); bool f = 0;
while (c < '0' || c > '9')
f |= c == '-', c = getchar();
while (c >= '0' && c <= '9')
x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
return f ? -x : x;
}
ll lin() {
ll x = 0; char c = getchar(); bool f = 0;
while (c < '0' || c > '9')
f |= c == '-', c = getchar();
while (c >= '0' && c <= '9')
x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
return f ? -x : x;
}
template<typename T>void out(T _) {
if (_ > 9)
out(_ / 10);
putchar(_ % 10 + 48);
}
template<typename T>inline void out_ln(T _) {
out(_), putchar('
');
}
template<typename T>inline void chk_min(T &_, T __) { _ = _ < __ ? _ : __; }
template<typename T>inline void chk_max(T &_, T __) { _ = _ > __ ? _ : __; }
const int N = 2e7 + 5, mod = 1e9 + 7;
int n, x, y;
int fac[N], inv[N];
int qpow(int base, int b, int ret = 1) {
for (; b; b >>= 1, base = 1ll * base * base % mod)
if (b & 1)
ret = 1ll * ret * base % mod;
return ret;
}
void prep() {
fac[0] = inv[0] = 1;
for (int i = 1; i < N; ++i)
fac[i] = 1ll * fac[i - 1] * i % mod;
inv[N - 1] = qpow(fac[N - 1], mod - 2);
for (int i = N - 2; i; --i)
inv[i] = 1ll * inv[i + 1] * (i + 1) % mod;
}
inline int C(const int n, const int m) {
return n < m ? 0 : 1ll * fac[n] * inv[m] % mod * inv[n - m] % mod;
}
int main() {
//freopen("in", "r", stdin);
freopen("tg.in", "r", stdin);
freopen("tg.out", "w", stdout);
int T = in(), res = 0;
prep();
while (T--) {
n = in(), x = in(), y = in();
if (y < x)
std::swap(x, y);
res = 1ll * (C(x + y - 2, x - 1) - C(x + y - 2, x - 2)) * (C(n - x + n - y, n - x) - C(n - x + n - y, n - x + 1)) % mod;
if (res < 0)
res += mod;
out_ln(res);
}
return 0;
}