自嗨测试赛2 A 任意模数多项式乘法逆 B 明明的随机数 C 凯爹博弈 (Unaccepted)
题目大意 ： 求一个多项式乘法逆的n次项系数
-
看到这个题目和题面还以为是一个板子（而且还忘了怎么打），于是心里强烈谴责了出题人TheSure
-
后来发现不是这样，给出的多项式最高次不超过10，于是10n就能跑过去了
-
有亿点卡常，用矩阵快速幂的话可以极快得通过（不过我没写）
Code
Show Code
#include <cstdio>
using namespace std;
const int N = 1e7;
int n, k, M, f[N], a[15];
int main() {
freopen("poly.in", "r", stdin);
freopen("poly.out", "w", stdout);
scanf("%d%d%d", &n, &k, &M); f[0] = 1;
for (int i = 1; i <= k; ++i)
scanf("%d", &a[i]);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= k && i - j >= 0; ++j) {
long long x = 1ll * f[i-j] * a[j];
if (x >= M) x %= M;
if ((f[i] += x) >= M) f[i] -= M;
}
f[i] = M - f[i];
}
printf("%d
", f[n]);
return 0;
}
B 明明的随机数
题目大意 ： 生成有一个n行m列的矩阵，每个数为不超过c的正整数，行列去重之后剩下k1行k2列，问有多少种方案
- 设f[i]表示i行无限制，k2列两两不同的方案数，第一列有 (c_i) 中选法，以后的每一列都不能选前面的选法，所以可知
[f[i]=prod_{j=0}^{k2}c^i-j
]
- 设g[i]表示i行，k2列都两两不同的方案数， (left { ^n_k ight })表示第二类斯特林数
[f[i]=sum_{j=1}^{i}left { ^i_j
ight }g[j]
]
-
这个式子的含义大概就是枚举有多少种不同的，然后求个和，也不知道该咋解释
-
根据斯特林反演的式子可得
[g[i]=sum_{j=1}^{i}(-1)^{i-j}left { ^i_j
ight }f[j]
]
- 于是答案就出来了
[ans=g[k1]left { ^n_{k1}
ight }left { ^m_{k2}
ight }
]
- 求f[i]的时候可以 O(k2)，求g[k1]用时O(k)，第二类斯特林数可以用O(n)的通项公式求
Code
Show Code
#include <cstdio>
using namespace std;
const int N = 3005, M = 998244353;
int read(int x = 0, int f = 1, char c = getchar()) {
for (; c < '0' || c > '9'; c = getchar()) if (c == '-') f = -1;
for (; c >='0' && c <='9'; c = getchar()) x = x * 10 + c - '0';
return x * f;
}
int T, n, m, k1, k2, c, s[N][N], fac[N], inv[N], ans;
int Pow(int a, int k, int ans = 1) {
for (; k; k >>= 1, a = 1ll * a * a % M)
if (k & 1) ans = 1ll * ans * a % M;
return ans;
}
void Init(int n) {
s[0][0] = fac[0] = 1;
for (int i = 1; i <= n; ++i)
fac[i] = 1ll * fac[i-1] * i % M;
inv[n] = Pow(fac[n], M - 2);
for (int i = n; i >= 1; --i)
inv[i-1] = 1ll * inv[i] * i % M;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= i; ++j)
s[i][j] = (s[i-1][j-1] + 1ll * (i - 1) * s[i-1][j]) % M;
}
int S(int n, int k) {
int ans = 0;
for (int i = 0; i <= k; ++i)
ans = (ans + 1ll * Pow(i, n) * inv[i] % M * inv[k-i] % M * ((k - i) & 1 ? -1 : 1) + M) % M;
return ans;
}
int main() {
freopen("random.in","r",stdin);
freopen("random.out","w",stdout);
scanf("%d", &T); Init(N - 1);
while (T--) {
scanf("%d%d%d%d%d", &n, &m, &k1, &k2, &c);
int p = 1; ans = 0;
for (int i = 1; i <= k1; ++i) {
int f = 1; p = 1ll * p * c % M;
for (int j = 0; j < k2; ++j)
f = 1ll * f * (p - j) % M;
ans = (ans + 1ll * s[k1][i] * f % M * ((k1 - i) & 1 ? -1 : 1) + M) % M;
}
printf("%lld
", 1ll * ans * S(n, k1) % M * S(m, k2) % M);
}
return 0;
}
C 凯爹博弈 (Unaccepted)
题目大意 ：
Code
Show Code