题目大意
一个长度为 $n$ 的排列 $\{P_i\}$ 的价值为
$$\sum_{i=2}^n|P_i-P_{i-1}| $$
给定 $n,m,k$ ，求出长度为 $n$ ，价值不小于 $m$ 的排列的频率，保留小数点后 $k$ 位。
$n\le 100$ .
思路
不难想到用 DP 实现。暂且先考虑设 $f_{i,j}$ 表示填了 $i$ 个位置，且价值达到 $j$ 的方案数。然而这样不能维护转移，不好维护选了哪些数。
实际上，我们只关心数字的相对大小而不关心具体选了哪些数，这或许能够成为突破口。因而我们把状态设为一个数集 $S$ ，表示选了的数。转移时，相对大小为主元，故考虑不断加入更大（或更小，它们地位相同，以更大为例）的数，而且是逐个连续加入，那么以 $1$ 开始从小到大加入即可。于是设 $f_{i,j}$ 表示选择了前 $i$ 个数，且价值达到 $j$ 的方案数。
继续考虑转移。这个状态仍然不好维护价值变化。试把选择了的 $i-1$ 个数分散到各个位置，再加入 $i$ 。发现 $i-1$ 个数形成若干个块，而围绕这些块，转移有几种情况：
- $i$ 新开一块（可以和边界连或否）；
- $i$ 一端连旧有的块，一端连空白或边界；
- $i$ 与两个旧块相连，它们合并。
由此我们可以设出最终的状态： $f_{i,j,k,l}$ 表示加入了前 $i$ 个数，存在 $j$ 个块，价值达到 $k$ ，且占了 $l$ 个端点的方案数。
根据上面的分列，不难推出转移方程。
时间复杂度 $\mathcal{O}(n^4)$ 。
代码
思路锻炼很好，但代码实现有点难受，不知道考察的目的。高精度常数好大，压位也不能解决，很痛苦，学习了 double 和 __float128 切换的实现。
滚动数组优化空间。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 110, K = 10010, mod = 998244353;
inline ll read() {
ll x = 0, f = 1;
char c = getchar();
while (c != '-' && (c < '0' || c > '9')) c = getchar();
if (c == '-') f = -f, c = getchar();
while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
return x * f;
}
namespace db{long double f[2][N][K][3];}
namespace ft{__float128 f[2][N][K][3];}
namespace Main {
int n, m, k;
/*
const int base = 1e7;
struct __int200{
const static int M = 11;
int d[M];
__int200() { memset(d, 0, sizeof d); }
__int200(int x) { for (memset(d, 0, sizeof d); x; d[++d[0]] = x % base, x /= base); }
};
__int200 operator + (__int200 a, __int200 b) {
int r = 0; a.d[0] = max(a.d[0], b.d[0]);
for (int i = 1; i <= max(1, a.d[0]); ++i) {
int x = a.d[i] + b.d[i] + r;
a.d[i] = x % base;
r = x / base;
a.d[0] += (i == a.d[0] && r);
}
return a;
}
void operator += (__int200 &a, __int200 b) {
a = a + b;
}
// __int200 operator * (__int200 a, int b) {
// int r = 0;
// for (int i = 1; i <= a.d[0]; ++i) {
// int m = a.d[i] * b + r;
// a.d[i] = m % 10;
// r = m / 10;
// a.d[0] += (i >= a.d[0] && r);
// }
// return a;
// }
__int200 operator * (__int200 a, __int200 b) {
__int200 c(0);
if (!a.d[0] || !b.d[0]) return c;
c.d[0] = a.d[0] + b.d[0];
for (int i = 1; i <= a.d[0]; ++i)
for (int j = 1; j <= b.d[0]; ++j)
c.d[i + j - 1] += a.d[i] * b.d[j];
for (int i = 1; i <= c.d[0]; ++i) {
c.d[i + 1] += c.d[i] / base;
c.d[0] += (i == c.d[0] && c.d[i] >= base);
c.d[i] %= base;
}
for (; !c.d[c.d[0]] && c.d[0] >= 0; c.d[0]--);
return c;
}
__int200 operator / (__int200 a, int b) {
__int200 c;
for (int i = a.d[0]; i; --i) {
int t = a.d[i] + a.d[i + 1] * base;
c.d[i] = t / b;
a.d[i] = t % b;
a.d[i + 1] = 0;
c.d[i] += (i == 0 && a.d[i] >= b / 2);
c.d[0] = (!c.d[0] && c.d[i])? i: c.d[0];
}
return c;
}
*/
const int zer = K / 2;
template < class T >
void write (T x) {
if(x + 1e-14 >= 1)cout << "1." << string(k, '0') << endl;
else {
cout << "0.", x *= 10;
for(int i = 1; i <= k; ++i)cout << (int)(x + (i == k ? 0.5 : 0)), x = (x - (int)x) * 10;
}
}
template < class T >
void solve(T f[][N][K][3]){
f[0][0][zer][0] = 1;
for (int i = 1; i <= n; i++) {
int now = i & 1;
memset(f[now], 0, sizeof f[now]);
for (int j = 0; j < i; ++j)
for (int k = 0; k < K; ++k)
for (int l = 0; l < 3; ++l)
if(f[now ^ 1][j][k][l]) {
if (j) f[now][j][k][l] += f[now ^ 1][j][k][l] * (j * 2 - l) / i;
if (k - 2 * i >= 0) f[now][j + 1][k - 2 * i][l] += f[now ^ 1][j][k][l] * (j + 1 - l) / i;
if (j >= 2 && k + 2 * i < K) f[now][j - 1][k + 2 * i][l] += f[now ^ 1][j][k][l] * (j - 1) / i;
if (l < 2) {
if (k - i >= 0) f[now][j + 1][k - i][l + 1] += f[now ^ 1][j][k][l] * (2 - l) / i;
if (j && k + i < K) f[now][j][k + i][l + 1] += f[now ^ 1][j][k][l] * (2 - l) / i;
}
}
}
T ans(0);
for (int i = m; i <= (n + 1) * n / 2; ++i) ans += f[n & 1][1][i + zer][2];
write(ans);
}
int main () {
n = read(), m = read(), k = read();
if (k <= 8) solve(db::f);
else solve(ft::f);
return 0;
}
}
int main () {
string str = "";
// freopen((str + ".in").c_str(), "r", stdin);
// freopen((str + ".out").c_str(), "w", stdout);
Main::main();
return 0;
}
EOF
题目大意
一个 $n\times m$ 的棋盘上填充着棋子，其中有一个空格。除了一些固定的棋子，空格相邻的棋子可以移动到空格上。一个棋盘上固定的棋子是确定的，给出 $q$ 个询问，对于每个询问回答，空格一开始在 $(ex,ey)$ 时， $(sx,sy)$ 上的指定棋子能否移动到 $(tx,ty)$ 和最少操作数。
$n,m\le30,q\le500$ .
思路
优先考虑初始位置就是目的地的特殊情况，操作数为零。再考虑通常情况，不难从“其实是空格在移动”的方向思考。
指定棋子到目的地的操作示例如图：
不难发现，路径其实分为两段：
- 空格移动到与指定棋子相邻处。若没有空格相邻，棋子肯定动不了，所以第一阶段必然是空格靠近指定棋子；
- 指定棋子与空格一起移动到目的地。由图，它们移动的方式是类似转着圈移动。
对于第一段，由于空格和指定棋子都不确定，每次询问时 BFS 即可。
对于第二段，它们运动的轨迹较为复杂，加之以固定棋子为障碍，或许不好直接“呆板的暴力”。注意到，两者的“一大步”是指定棋子替代空格的位置后，空格再找到合适的相邻处，这“一大步”的操作对于棋盘来说是确定的（可以预处理）。
以此为基础，我们以这“一大步”作为边，两者的位置一并看作点，“一大步”所需操作数为边权建立图论模型。这样，最短路即为第二段的答案。
复杂度 $\mathcal{O}(n^2m^2+qnm\log nm)$ 。
代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 40, mod = 998244353, inf = 1010580540;
inline ll read() {
ll x = 0, f = 1;
char c = getchar();
while (c != '-' && (c < '0' || c > '9')) c = getchar();
if (c == '-') f = -f, c = getchar();
while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
return x * f;
}
inline int add (int a, int b) { return a + b > mod? a + b - mod: a + b; }
inline int dec (int a, int b) { return a < b? a - b + mod: a - b; }
inline int mul (int a, int b) { return 1ll * a * b % mod; }
namespace Main {
int n, m;
bool a[N][N];
int rots[2][4] = {{0, 1, -1, 0}, {1, 0, 0, -1}};
bool border(int x, int y) { return 1 <= x && x <= n && 1 <= y && y <= m; }
bool able(int x, int y) { return border(x, y) && a[x][y]; }
int head[N * N * 4], etot;
struct edge { int to, nxt, w; } e[N * N * 32];
void add(int u, int v, int w) { e[++etot] = (edge){v, head[u], w}, head[u] = etot; }
struct node { int x, y, rot; };
int id[N][N][4];
int dis[N][N];
bool vis[N][N];
void bfs(int ix, int iy) {
queue<node> q;
q.push({ix, iy, -1});
memset(vis, 0, sizeof vis);
vis[ix][iy] = 1;
while (!q.empty()) {
node u = q.front(); q.pop();
for (int rot = 0; rot < 4; ++rot) {
int x = u.x + rots[0][rot], y = u.y + rots[1][rot];
if (able(x, y) && dis[x][y] > dis[u.x][u.y] + 1) {
dis[x][y] = dis[u.x][u.y] + 1;
if (vis[x][y]) continue; vis[x][y] = 1;
q.push({x, y, -1});
}
}
vis[u.x][u.y] = 0;
}
}
void prework() {
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
if (able(i, j))
for (int rot = 0; rot < 4; ++rot) {
int x = i + rots[0][rot], y = j + rots[1][rot];
if (able(x, y)) {
int u = (id[i][j][rot]? id[i][j][rot]: (id[i][j][rot] = ++etot));
a[x][y] = 0;
memset(dis, 60, sizeof dis);
dis[i][j] = 1;
// printf ("DEBUG P=(%d,%d)\n", i,j);
bfs(i, j);
for (int rot2 = 0; rot2 < 4; ++rot2) {
int nx = x + rots[0][rot2], ny = y + rots[1][rot2];
if (border(nx, ny) && dis[nx][ny] <= inf) {
int v = (id[x][y][rot2]? id[x][y][rot2]: (id[x][y][rot2] = ++etot));
add(u, v, dis[nx][ny]);
}
}
a[x][y] = 1;
}
}
}
bool vs[N * N * 4];
int dt[N * N * 4];
void spfa(int x, int y) {
queue<int>q;
memset(vs, 0, sizeof vs);
memset(dt, 60, sizeof(int) * (etot + 5));
for (int rot = 0, u; rot < 4; ++rot)
if (u = id[x][y][rot]) {
q.push(u);
dt[u] = dis[x + rots[0][rot]][y + rots[1][rot]];
vs[u] = 1;
}
while(!q.empty()) {
int u = q.front(); q.pop();
for (int i = head[u]; i; i = e[i].nxt) {
int v = e[i].to;
if (!(dt[v] > dt[u] + e[i].w)) continue;
dt[v] = dt[u] + e[i].w;
q.push(v);
}
vs[u] = 0;
}
}
int main () {
n = read(), m = read(); int T = read();
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j) a[i][j] = read();
// puts("DEBUG #1");
prework();
// puts("DEBUG #2");
for (; T--; ) {
int ex = read(), ey = read(), sx = read(), sy = read(), tx = read(), ty = read();
if (sx == tx && sy == ty) { puts("0"); continue;}
a[sx][sy] = 0;
memset (dis, 60, sizeof dis);
dis[ex][ey] = 0;
bfs(ex, ey);
a[sx][sy] = 1;
spfa(sx, sy);
int ans = inf;
for (int rot = 0; rot < 4; ++rot) ans = min(ans, dt[id[tx][ty][rot]]);
printf ("%d\n", (ans == inf? -1: ans));
}
return 0;
}
}
int main () {
string str = "";
// freopen((str + ".in").c_str(), "r", stdin);
// freopen((str + ".out").c_str(), "w", stdout);
Main::main();
return 0;
}
EOF
题目大意
有 $n$ 个人做报告，第 $i$ 个人会使兴奋度 $x$ 变成 $a_i\lvert x\rvert+b_ix+c_i$ 。
初始兴奋度为 $s$ ，调整报告顺序使得最后的兴奋度最大。
$n,s,|a_i|,|b_i|,|c_i|\le15$ .
思路
调整顺序，范围又很小，于是考虑状压 DP。
贡献是分段函数，可以看作是端点在 $y$ 轴上的两条射线，并不是 $x$ 值越大，函数值越大。
转移时对新函数的两条线分类讨论，斜率大于零我们希望他越大，反之亦然，则为了得到新状态的最大值，需要分别维护原有状态在 $y$ 轴两侧的（离 $y$ 轴的）最近最远值。而要维护这四值，又需要维护更多值。然而注意到数据范围很小，直接记录值域 $|V|\le15\times15$ 所有值的可达性即可。
启示：不要陷入复杂的零点、极值的讨论。
时间复杂度 $\mathcal{O}(2^nn^2|c|)$ 。
代码
#include <bits/stdc++.h>
#define ll long long
#define LL __int128
using namespace std;
const int N = 15, V = 250, mod = 998244353;
const int aV = 500;
const LL inf = 1e36;
inline ll read() {
ll x = 0, f = 1;
char c = getchar();
while (c != '-' && (c < '0' || c > '9')) c = getchar();
if (c == '-') f = -f, c = getchar();
while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
return x * f;
}
inline int add (int a, int b) { return a + b > mod? a + b - mod: a + b; }
inline int dec (int a, int b) { return a < b? a - b + mod: a - b; }
inline int mul (int a, int b) { return 1ll * a * b % mod; }
void write(LL x) {
if (x < 0) putchar('-'), x = -x;
if (x >= 10) write(x / 10);
putchar('0' + x % 10);
}
namespace Main {
int n, s;
int a[N], b[N], c[N];
struct state {
LL maxp, minp, maxn, minn;
bool vis[aV + 10];
state() {
for (int i = 0; i < aV; ++i) vis[i] = 0;
minn = maxp = 0; maxn = -inf, minp = inf;
}
void update(LL x) {
if (-V <= x && x <= V) vis[x + V] = 1;
if (x > 0) maxp = max(maxp, x), minp = min(minp, x);
else maxn = max(maxn, x), minn = min(minn, x);
}
} f[1 << N];
LL abs(LL x) { return x < 0? -x: x; }
LL val(LL x, int i) { return abs(x) * a[i] + x * b[i] + c[i];}
int main () {
n = read(), s = read();
for (int i = 0; i < n; ++i) a[i] = read(), b[i] = read(), c[i] = read();
f[0].update(s);
for (int S = 0; S < (1 << n); ++S) {
for (int i = 0; i < n; ++i) {
if (S >> i & 1) continue;
int nS = S | (1 << i);
for (int v = -V; v <= V; ++v) {
if (!f[S].vis[v + V]) continue;
f[nS].update(val(v, i));
}
if (f[S].minp <= f[S].maxp) f[nS].update(val(f[S].minp, i)), f[nS].update(val(f[S].maxp, i));
if (f[S].minn <= f[S].maxn) f[nS].update(val(f[S].minn, i)), f[nS].update(val(f[S].maxn, i));
}
}
int S = (1 << n) - 1;
LL ans = -inf;
for (int v = V; v >= -V; --v) if (f[S].vis[v + V]) ans = max(ans, (LL) v);
if (f[S].minp <= f[S].maxp) ans = max(ans, f[S].maxp);
if (f[S].minn <= f[S].maxn) ans = max(ans, f[S].maxn);
write(ans); putchar(10);
return 0;
}
}
int main () {
string str = "";
// freopen((str + ".in").c_str(), "r", stdin);
// freopen((str + ".out").c_str(), "w", stdout);
Main::main();
return 0;
}
EOF
题目大意
给定以 $1$ 为根结点的一棵树，有 $n(n\leq5\times10^5)$ 个节点，对于每个 $k\leq n$ ，求随机选取 $k$ 的结点的期望 LCA 深度，结果对 998244353 取模。
题解
考虑每个点 $u$ 的贡献为
$$\text{dep}(u)\left(\binom{|T_u|}{k}-\sum_{v\in\text{son}(u)}\binom{|T_v|}{k}\right) $$
注意到，子结点的深度是当前深度的后继，故对于一个 $k$ ，答案为
$$\frac{1}{\binom{n}{k}}\sum_{u=1}^n \binom{|T_u|}{k} $$
考虑优化。
二项式系数自带一个卷积的形式，考虑写成多项式的形式。记子树大小为 $|T_u|$ 的子树数量为 $a_i$ ，有
$$\sum_k \frac1{k!}\left(\sum_ia_ii!\cdot\frac1{(i-k)!}\right) $$
令 $j=i-k$ ，上式就是 $i-j=k$ 的减法卷积形式。减法卷积相当于 $i+(-j)$ ，负数下标对 $n$ 取模，即 $n-j$ ，也可以看作是翻转数组，然后平移。
代码
const int N = 5e5 + 10, pN = N << 3, mod = 998244353;
const int G = 3, invG = 332748118;
ll read() {
ll x = 0, f = 1;
char c = getchar();
while (c != '-' && (c < '0' || c > '9')) c = getchar();
if (c == '-') f = -f, c = getchar();
while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
return x * f;
}
int add(int a, int b) { return a + b > mod? a + b - mod: a + b; }
int dec(int a, int b) { return a > b? a - b: a - b + mod; }
int mul(int a, int b) { return 1ll * a * b % mod; }
#define clr(f, x) memset(f, 0, sizeof(int) * (x))
#define cpy(f, g, x) memcpy(f, g, sizeof(int) * (x))
namespace Main {
int n;
struct edge {
int to, nxt;
} e[N << 1];
int head[N], tot;
void add_edge (int u, int v) { e[++tot] = (edge) {v, head[u]}; head[u] = tot; }
int siz[N];
void dfs (int u, int fa) {
siz[u] = 1;
for (int i = head[u]; i; i = e[i].nxt) {
int v = e[i].to;
if (fa == v) continue;
dfs(v, u); siz[u] += siz[v];
}
}
int fac[N], ifac[N];
int qpow (int a, ll b) {
int ans = 1;
for (; b; b >>= 1, a = mul(a, a))
if (b & 1) ans = mul(ans, a);
return ans;
}
int binom(int n, int m) {
if (n < m) return 0;
return mul(fac[n], mul(ifac[m], ifac[n - m]));
}
int cnt[N];
int f[pN], g[pN];
struct poly {
int tr[pN];
void init(int n, int siz) {
for (int i = 0; i < n; ++i)
tr[i] = (tr[i >> 1] >> 1) | ((i & 1) << (siz - 1));
}
void NTT(int *f, int n, int op = 1) {
for (int i = 0; i < n; ++i)
if (i < tr[i]) swap(f[i], f[tr[i]]);
for (int p = 1; p < n; p <<= 1) {
int omega = qpow(op? G: invG, (mod - 1) / (p << 1));
for (int j = 0; j < n; j += p << 1)
for (int w = 1, k = 0; k < p; k++, w = mul(w, omega)) {
int x = f[j | k], y = mul(w, f[j | p | k]);
f[j | k] = add(x, y), f[j | p | k] = dec(x, y);
}
}
if (!op) {
int invn = qpow(n, mod - 2);
for (int i = 0; i < n; ++i) f[i] = mul(f[i], invn);
}
}
void times(int *f, int *g, int n, int m, int T) {
int lim = 1, lsiz = 0; for (; lim < n + m; lim <<= 1, lsiz++);
init(lim, lsiz);
static int tmp[pN]; clr(f + n, lim - n), cpy(tmp, g, m), clr(tmp + m, lim - m);
NTT(f, lim); NTT(tmp, lim);
for (int i = 0; i < lim; ++i) f[i] = mul(f[i], tmp[i]);
NTT(f, lim, 0);
clr(f + T, lim - 1), clr(tmp, lim);
}
}p;
int main () {
n = read();
for (int i = 1; i < n; ++i) {
int u = read(), v = read();
add_edge(u, v); add_edge(v, u);
}
dfs (1, 0);
for (int i = 1; i <= n; ++i) ++cnt[siz[i]];
fac[0] = 1;
for (int i = 1; i <= N - 10; ++i) fac[i] = mul(fac[i - 1], i);
ifac[N - 10] = qpow(fac[N - 10], mod - 2);
for (int i = N - 10; i; --i) ifac[i - 1] = mul(ifac[i], i);
int m = n + 1;
for (int i = 0; i < m; i++) {
f[i] = mul(cnt[i], fac[i]);
g[i] = ifac[m - i - 1];
}
p.times(f, g, m, m, m << 1);
for (int i = 0; i <= m; i++) f[i] = f[i + m - 1];
for (int k = 1; k <= n; ++k) {
int ans = qpow(binom(n, k), mod - 2);
//int ans = 1;
ans = mul(ans, ifac[k]);
ans = mul(ans, f[k]);
printf ("%d ", ans);
}
puts("");
return 0;
}
}
int main () {
string str = "";
// freopen((str + ".in").c_str(), "r", stdin);
// freopen((str + ".out").c_str(), "w", stdout);
Main::main();
return 0;
}
EOF
题目大意
$n$ 排两列，塞 $n$ 对情侣，求恰好 $k$ 对情侣没有被拆散的数量。对 $998244353$ 取模。
题解
注意到，答案表达式为
$$\binom{n}{k}\cdot n^{\underline{k}}\cdot 2^k\cdot f_{n-k} $$
其中 $f_i$ 是 $i$ 对情侣全被拆散的数量。有
$$f_i=4i(i-1)\left(f_{i-1}+2(i-1)f_{i-2}\right) $$
代码
const int N = 5e6 + 10, mod = 998244353;
inline ll read() {
ll x = 0, f = 1;
char c = getchar();
while (c != '-' && (c < '0' || c > '9')) c = getchar();
if (c == '-') f = -f, c = getchar();
while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
return x * f;
}
inline int add (int a, int b) { return a + b > mod? a + b - mod: a + b; }
inline int dec (int a, int b) { return a < b? a - b + mod: a - b; }
inline int mul (int a, int b) { return 1ll * a * b % mod; }
namespace Main {
int n, k;
int f[N];
int fac[N], ifac[N], p2[N];
int qpow (int a, int b) {
int ans = 1;
for (; b; b >>= 1, a = mul(a, a))
if (b & 1) ans = mul(ans, a);
return ans;
}
int binom(int n, int m) {
if (m > n) return 0;
return mul(fac[n], mul(ifac[m], ifac[n - m]));
}
int main () {
fac[0] = p2[0] = 1;
f[0] = 1, f[1] = 0;
for (int i = 1; i <= N - 10; i++) {
fac[i] = mul(fac[i - 1], i), p2[i] = mul(p2[i - 1], 2);
if (i > 1) f[i] = add(mul(mul(mul(4, i), i - 1), f[i - 1]),
mul(mul(mul(mul(8, i), i - 1), i - 1), f[i - 2]));
}
ifac[N - 10] = qpow (fac[N - 10], mod - 2);
for (int i = N - 10; i; --i) ifac[i - 1] = mul(ifac[i], i);
for (int t = read(); t--; ) {
n = read(), k = read();
int ans = mul(binom(n, k), mul(p2[k], mul(fac[n], ifac[n - k])));
ans = mul(ans, f[n - k]);
printf ("%d\n", ans);
}
return 0;
}
}
int main () {
string str = "";
// freopen((str + ".in").c_str(), "r", stdin);
// freopen((str + ".out").c_str(), "w", stdout);
Main::main();
return 0;
}
EOF