哈哈输出大样例能得的分都比打了 3.5h 得分高。
A. 「清华集训 2017」小 Y 和恐怖的奴隶主
期望dp + 矩阵乘法
看完题之后比较晕，没有想到把 1，2，3 血的怪的数量都记录下来，整个 4 维期望 dp，直接跳过了，有点亏。
设状态 \(dp[i][a][b][c]\)，表示打了 \(i\) 次之后场上 1，2，3 血的怪物分别有 \(a, b, c\) 只。
暴力转移显然会 TLE。
不难发现，总共只有165 个状态，加上答案状态就是 166 个状态，所以可以编个号，然后压到一维里，使用矩乘加速。
code
#include <bits/stdc++.h>
#define ll long long
using namespace std;
namespace IO{
inline ll read(){
ll x = 0;
char ch = getchar();
while(!isdigit(ch)) ch = getchar();
while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
return x;
}
template <typename T> inline void write(T x){
if(x < 0) putchar('-'), x = -x;
if(x > 9) write(x / 10);
putchar(x % 10 + '0');
}
}
using namespace IO;
const int N = 210;
const int mod = 998244353;
int T, m, s, n;
int id[13][13][13], inv[N];
inline int add(int x) {return x >= mod ? x - mod : x;}
inline int qpow(int a, int b){
int res = 1;
while(b){
if(b & 1) res = 1ll * res * a % mod;
a = 1ll * a * a % mod, b >>= 1;
}
return res;
}
struct matrix{
int num[N][N];
matrix() {memset(num, 0, sizeof(num));}
void init() {for(int i = 1; i <= n; ++i) num[i][i] = 1;}
friend matrix operator * (matrix a, matrix b){
matrix c;
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j)
for(int k = 1; k <= n; ++k)
c.num[i][j] = add(c.num[i][j] + 1ll * a.num[i][k] * b.num[k][j] % mod);
return c;
}
}f[64];
int ans[N], t[N];
inline void Mul(int u){
for(int i = 1; i <= n; ++i) t[i] = 0;
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j)
t[i] = add(t[i] + 1ll * ans[j] * f[u].num[j][i] % mod);
for(int i = 1; i <= n; ++i) ans[i] = t[i];
}
int main(){
T = read(), m = read(), s = read();
for(int i = 1; i <= 9; ++i) inv[i] = qpow(i, mod - 2);
for(int i = 0; i <= s; ++i)
for(int j = 0; j <= (m >= 2 ? s - i : 0); ++j)
for(int k = 0; k <= (m == 3 ? s - i - j : 0); ++k)
id[i][j][k] = ++n;
n++;
f[0].num[n][n] = 1;
for(int a = 0; a <= s; ++a)
for(int b = 0; b <= (m >= 2 ? s - a : 0); ++b)
for(int c = 0; c <= (m == 3 ? s - a - b : 0); ++c){
int i = id[a][b][c], inv_i = inv[a + b + c + 1], t = (a + b + c < s);
if(a) f[0].num[i][id[a - 1][b][c]] = 1ll * a * inv_i % mod;
if(m == 2 && b) f[0].num[i][id[a + 1][b - 1 + t][c]] = 1ll * b * inv_i % mod;
if(m == 3 && b) f[0].num[i][id[a + 1][b - 1][c + t]] = 1ll * b * inv_i % mod;
if(m == 3 && c) f[0].num[i][id[a][b + 1][c - 1 + t]] = 1ll * c * inv_i % mod;
f[0].num[i][i] = f[0].num[i][n] = inv_i;
}
for(int i = 1; i <= 60; ++i) f[i] = f[i - 1] * f[i - 1];
while(T--){
ll x = read();
for(int i = 1; i <= n; ++i) ans[i] = 0;
ans[id[m == 1][m == 2][m == 3]] = 1;
for(int i = 0; i <= 60; ++i)
if((x >> i) & 1) Mul(i);
write(ans[n]), puts("");
}
return 0;
}
B. 「一本通 4.4 练习 4」跳跳棋
巨大难思维 + LCA
谁能想到这题跳棋的情况可以建成一棵树？？？
20pts bfs 暴力滚粗。
注意题目里：一次只允许跳过一个棋子。
（考场上虽然看到了，但是没反应过来，还以为是只能跳一次的意思……）
所以中间的点可以向两边跳，两边的点只有一个能往中间跳（只有距离中间那个点近的点可以向中间跳）。
把三个点的位置三元组 \((x, y, z)\) 存到一个节点里，那么是如何建树的呢？
把向中间跳的那个三元组当父亲节点，向外跳的两个当儿子节点，然后两点之间的距离就是跳的次数。
但是怎么快速求 LCA 呢？三元组普通的倍增什么的是不行的，所以先把深度大的点跳到跟另一个点深度相同的高度，然后二分向上跳的步数，再判断。
code
#include <bits/stdc++.h>
using namespace std;
namespace IO{
inline int read(){
int x = 0, f = 1;
char ch = getchar();
while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
return x * f;
}
template <typename T> inline void write(T x){
if(x > 9) write(x / 10);
putchar(x % 10 + '0');
}
}
using namespace IO;
struct node{
int x, y, z;
inline void init(){
if(x > y) swap(x, y);
if(x > z) swap(x, z);
if(y > z) swap(y, z);
}
friend bool operator != (node a, node b){
return (a.x ^ b.x) | (a.y ^ b.y) | (a.z ^ b.z);
}
friend bool operator == (node a, node b){
return (a.x == b.x) & (a.y == b.y) & (a.z == b.z);
}
}a, b, A, B, C;
int tot1, tot2, ans;
inline int dfs(int x, int y, int z){
int d1 = y - x, d2 = z - y, cnt = 0, d;
if(d1 > d2){
cnt = d1 / d2, d = d1 % d2;
if(!d) d += d2, cnt--;
cnt += dfs(x, x + d, x + d + d2);
}else if(d1 < d2){
cnt = d2 / d1, d = d2 % d1;
if(!d) d += d1, cnt--;
cnt += dfs(z - d - d1, z - d, z);
}else C = (node){x, y, z};
return cnt;
}
inline void update(int x, int y, int z, int step){
if(!step) return C = (node){x, y, z}, void();
int d1 = y - x, d2 = z - y, cnt = 0, d;
if(d1 > d2){
cnt = d1 / d2, d = d1 % d2;
if(!d) d += d2, cnt--;
if(step >= cnt) update(x, x + d, x + d + d2, step - cnt);
else update(x, x + d + d2 * (cnt - step), x + d + d2 * (cnt - step + 1), 0);
}else if(d1 < d2){
cnt = d2 / d1, d = d2 % d1;
if(!d) d += d1, cnt--;
if(step >= cnt) update(z - d - d1, z - d, z, step - cnt);
else update(z - d - d1 * (cnt - step + 1), z - d - d1 * (cnt - step), z, 0);
}else C = (node){x, y, z};
}
inline bool check(int step){
update(a.x, a.y, a.z, step), A = C;
update(b.x, b.y, b.z, step), B = C;
return A == B;
}
inline int solve(){
int l = 0, r = min(tot1, tot2), res;
while(l <= r){
int mid = (l + r) >> 1;
if(check(mid)) r = mid - 1, res = mid;
else l = mid + 1;
}
return (res << 1) + ans;
}
int main(){
a = (node){read(), read(), read()}, b = (node){read(), read(), read()};
a.init(), b.init();
tot1 = dfs(a.x, a.y, a.z), A = C;
tot2 = dfs(b.x, b.y, b.z), B = C;
// cout << tot1 << " " << tot2 << endl;
if(A != B) return puts("NO"), 0;
if(tot1 < tot2){
ans += tot2 - tot1;
update(b.x, b.y, b.z, tot2 - tot1), b = C;
}else if(tot1 > tot2){
ans += tot1 - tot2;
update(a.x, a.y, a.z, tot1 - tot2), a = C;
}
// cout << a.x << " " << a.y << " " << a.z << endl;
printf("YES\n%d\n", solve());
return 0;
}
C. Calc
dp + 拉格朗日插值
先考虑暴力 dp
设 \(dp_{i, j}\) 表示前 \(i\) 个数用了 \(1 \sim j\) 的和，转移方程比较显然：
我们只处理递增的序列，分类讨论第 \(i\) 个数取不取 \(j\)。
\[dp_{i, j} = dp_{i - 1, j - 1} \times j + dp_{i, j - 1} \]经过一系列推导，我们发现 \(dp_{n, i}\) 是关于 \(i\) 的一个 \(2n\) 次多项式，所以直接拉格朗日插值求一下 \(dp_{n, A}\) 即可。
code
#include <bits/stdc++.h>
#define ll long long
using namespace std;
namespace IO{
inline int read(){
int x = 0;
char ch = getchar();
while(!isdigit(ch)) ch = getchar();
while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
return x;
}
template <typename T> inline void write(T x){
if(x > 9) write(x / 10);
putchar(x % 10 + '0');
}
}
using namespace IO;
const int N = 510;
ll A, n, mod, ans;
ll fac[N], f[N][N << 1];
inline ll qpow(ll a, ll b){
ll res = 1;
while(b){
if(b & 1) res = res * a % mod;
a = a * a % mod, b >>= 1;
}
return res;
}
inline void lagrange(){
for(int i = 0; i <= (n << 1); ++i){
ll t1 = 1, t2 = 1;
for(int j = 0; j <= (n << 1); ++j)
if(i != j) t1 = t1 * (A - j + mod) % mod, t2 = t2 * (i - j + mod) % mod;
ans = (ans + f[n][i] * t1 % mod * qpow(t2, mod - 2) % mod) % mod;
}
}
int main(){
A = read(), n = read(), mod = read();
fac[0] = 1;
for(int i = 1; i <= n; ++i) fac[i] = fac[i - 1] * i % mod;
for(int i = 0; i <= (n << 1); ++i) f[0][i] = 1;
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= (n << 1); ++j)
f[i][j] = (f[i - 1][j - 1] * j % mod + f[i][j - 1]) % mod;
lagrange();
write(ans * fac[n] % mod), puts("");
return 0;
}