T1 Article
给 $m$ 个好串，定义一个字符串分割方案是好的当且仅当它分割出来的子串中"是好串的子串"的串长占原串串长超过 85%，定义一个好的分割方案的权值为这种分割方案中每个"是好串的子串"的子串的最短长度，给 $n$ 个询问串，对每个询问串求最大权值
$n,m \leq 10^5, \sum |S|,\sum |T| \leq 10^6$
sol：
二分最短长度 $L$，做一个 dp
$f_i$ 表示前 $i$ 位字符串最多的"是好串的子串"的长度和是多少，转移就是 $f_i = max\{f_j + (i - j)\} (S[j+1,i] 是好串的子串，i-j \geq L)$
由于 $S[j+1,i]$ 的右端单调递增，可以用后缀自动机来预处理每一个 $S[1,i]$ 最大匹配长度，最大匹配长度显然是单调的，所以可以用单调队列维护 $i+f_i$
然后还要注意一点是这题 85% 以上就行，所以还要加一个 $f_i = f_{i-1}$ 的转移，最后判一下 $f_{len}$ 是否超过原串的 85%
#include <bits/stdc++.h>
#define LL long long
#define rep(i, s, t) for(register int i = (s), i##end = (t); i <= i##end; ++i)
#define dwn(i, s, t) for(register int i = (s), i##end = (t); i >= i##end; --i)
using namespace std;
inline int read() {
int x = , f = ; char ch = getchar();
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -f;
for(; isdigit(ch); ch = getchar()) x = * x + ch - '';
return x * f;
}
const int maxn = ;
int m, n;
char s[maxn];
int f[maxn];
int root, last, dfn;
int tr[maxn][], fa[maxn], mxlen[maxn], Q[maxn];
inline void extend(int c) {
int p = last, np = last = ++dfn;
mxlen[np] = mxlen[p] + ;
for(; p && !tr[p][c]; p = fa[p]) tr[p][c] = np;
if(!p) fa[np] = root;
else {
int q = tr[p][c];
if(mxlen[q] == mxlen[p] + ) fa[np] = q;
else {
int nq = ++dfn;
mxlen[nq] = mxlen[p] + ;
fa[nq] = fa[q]; fa[q] = fa[np] = nq;
memcpy(tr[nq], tr[q], sizeof(tr[q]));
for(; p && tr[p][c] == q; p = fa[p]) tr[p][c] = nq;
}
}
}
int chk(int mid) {
int len = strlen(s + );
int p = root, cl = , HD = , TL = ;
rep(i, , len) {
int c = s[i] - 'a';
if(tr[p][c]) p = tr[p][c], cl++;
else {
for(; p && !tr[p][c]; p = fa[p]);
if(!p) cl = , p = root;
else cl = mxlen[p] + , p = tr[p][c];
}
f[i] = f[i - ];
int lf = i - cl, rig = i - mid;
if(rig < ) continue;
while(HD <= TL && f[Q[TL]] - Q[TL] < f[rig] - rig) --TL;
Q[++TL] = rig;
while(HD <= TL && Q[HD] < lf) ++HD;
if(HD <= TL)f[i] = max(f[i], i + f[Q[HD]] - Q[HD]);
}
return (f[len] * ) >= (len * );
}
int main() {
// freopen("article.in","r",stdin);
// freopen("article.out","w",stdout);
root = last = ++dfn;
n = read(), m = read();
rep(i, , m) {
scanf("%s", s + ); int len = strlen(s + );
last = ; rep(i, , len) extend(s[i] - 'a');
}
rep(i, , n) {
scanf("%s", s + ); int l = , r = strlen(s + ), ans = -;
while(l <= r) {
int mid = (l + r) >> ;
if(chk(mid)) l = mid + , ans = mid;
else r = mid - ;
} cout << ans << '\n';
}
}
/*
1 2
babba
aaaaabbba
babbaabbaa
*/
T2 work
Nick最近在玩一款很好玩的游戏，游戏规则是这样的：
有一个n*m的地图，地图上的每一个位置要么是空地，要么是炮塔，要么是一些BETA狗，Nick需
要操纵炮塔攻击BETA狗们。
攻击方法是：对于每个炮塔，游戏系统已经给出它可以瞄准的方向(上下左右其中一个），Nick需要
选择它的攻击位置，每一个炮塔只能够攻击一个位置，炮塔只能够向着它的瞄准方向上的某个位置发
动攻击，当然炮塔也可以不进行攻击。炮塔威力强大，它可以且仅可以消灭目标位置上所有的BETA狗。
出于安全考虑，游戏系统已经保证不存在一个炮塔能够瞄准另外一个炮塔，即对于任意一个炮
塔，它所有可能的攻击位置上不存在另外一个炮塔。而且，如果把炮塔的起点和终点称为炮弹的运行
轨迹，那么系统不允许两条轨迹相交f包括起点和终点）。
现在，选定目标位置以后，每一个炮塔同时开炮，你要告诉Nick，他最多可以干掉多少BETA狗。
$n,m \leq 50$
考场上 sb 了，一直觉得这题是个费用流，然后死磕，然后磕死
然后发现这是一个小清新最小割题...
考虑两个从 $A$,$B$ 出发“相交”的炮弹是什么样的，显然可以看成最多拐一个弯的连接 $A,B$ 的路径，任意一个合法方案必然不包含这样的路径，所以相当于割掉这条路径的一边，于是是最小割...
一开始搜出所有路径最大值，然后减去最小代价就是答案
“最多拐一个弯”可以这样：把一个点拆成纵和横，然后纵横分别连边，每个点纵向横连 inf 即可
#include <bits/stdc++.h>
#define LL long long
#define rep(i, s, t) for(register int i = (s), i##end = (t); i <= i##end; ++i)
#define dwn(i, s, t) for(register int i = (s), i##end = (t); i >= i##end; --i)
using namespace std;
inline int read() {
int x = , f = ; char ch = getchar();
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -f;
for(; isdigit(ch); ch = getchar()) x = * x + ch - '';
return x * f;
}
const int oo = , maxn = ;
struct Dinic {
int n, m, s, t;
int cur[maxn], head[maxn], nx[maxn];
struct Edge {
int from, to, caps;
Edge() {}
Edge(int _1, int _2, int _3) : from(_1), to(_2), caps(_3) {}
} es[maxn];
void add(int u, int v, int w) {
es[m] = Edge(u, v, w);
nx[m] = head[u];
head[u] = m++;
es[m] = Edge(v, u, );
nx[m] = head[v];
head[v] = m++;
}
Dinic() {
m = ;
memset(head, -, sizeof(head));
}
queue<int> q;
int dis[maxn];
int BFS() {
for (int i = ; i <= n; i++) dis[i] = ;
dis[t] = ;
q.push(t);
while (!q.empty()) {
int now = q.front();
q.pop();
for (int i = head[now]; i != -; i = nx[i]) {
Edge &e = es[i ^ ];
if (!dis[e.from] && e.caps) {
dis[e.from] = dis[now] + ;
q.push(e.from);
}
}
}
return (dis[s] > );
}
int DFS(int u, int a) {
if (u == t || !a)
return a;
int flow = , f;
for (int &i = cur[u]; i != -; i = nx[i]) {
Edge &e = es[i];
if (dis[e.to] == dis[u] - && (f = DFS(e.to, min(e.caps, a)))) {
flow += f;
a -= f;
e.caps -= f;
es[i ^ ].caps += f;
if (a == )
return flow;
}
}
return flow;
}
int MaxFlow(int _s, int _t) {
s = _s, t = _t;
int flow = , f;
while (BFS()) {
for (int i = ; i <= n; i++) cur[i] = head[i];
while (f = DFS(s, oo)) flow += f;
}
return flow;
}
} sol;
int pos[][][], dfn;
const int dx[] = {, -, , , };
const int dy[] = {, , , -, };
inline int t(int i, int j, int type) { return pos[i][j][type] ? pos[i][j][type] : (pos[i][j][type] = ++dfn); }
int n, m, S, T, ans;
int a[][];
int main() {
n = read(), m = read();
rep(i, , n) rep(j, , m) {
a[i][j] = read();
sol.add(t(i, j, ), t(i, j, ), oo);
} S = ++dfn, T = ++dfn;
rep(i, , n) rep(j, , m) {
if(a[i][j] >= ) continue;
int opt = -a[i][j]; a[i][j] = ;
int cx = i + dx[opt], cy = j + dy[opt], mx = ;
while(cx >= && cx <= n && cy >= && cy <= m) {
mx = max(mx, a[cx][cy]);
cx += dx[opt], cy += dy[opt];
}
ans += mx;
if(opt <= ) {
int cx = i + dx[opt], cy = j + dy[opt];
sol.add(S, t(i, j, ), oo);
while(cx >= && cx <= n && cy >= && cy <= m) {
sol.add(t(cx - dx[opt], cy - dy[opt], ), t(cx, cy, ), mx - a[cx - dx[opt]][cy - dy[opt]]);
cx += dx[opt], cy += dy[opt];
}
}
else {
int cx = i + dx[opt], cy = j + dy[opt];
sol.add(t(i, j, ), T, oo);
while(cx >= && cx <= n && cy >= && cy <= m) {
sol.add(t(cx, cy, ), t(cx - dx[opt], cy - dy[opt], ), mx - a[cx - dx[opt]][cy - dy[opt]]);
cx += dx[opt], cy += dy[opt];
}
}
} sol.n = dfn;
cout << ans - sol.MaxFlow(S, T) << endl;
}
T3 sej
一个长度为 $n$ 的排列 $\{a_i\}$，定义 $p_x = max_{i=1}^x a_i$，$s_x = max_{i=x}^n a_i$
对这个排列求出 $p$ 数组和 $s$ 数组，将 $p,s$ 分别去重、排序，求 $p,s$ 长度分别为 $a,b$ 的排列有多少个
$n,a,b \leq 100000$
sol：
发现 $p$ 数组和 $s$ 数组一定能变成一个峰，两边递减，而两边的情况是对称的，于是可以考虑枚举每次左边，右边峰的出现
记 $f_{(i,j)}$ 表示插入了前 $i$ 大的数，左边的峰改变了$j$ 次的排列数
考虑每次把 $1$ 加进去，就是 $f_{(i,j)} = f_{(i-1,j-1)} + (i-1) \times f_{(i-1,j)}$
因为左右时对称的，所以这也是右边的峰改变了 $j$ 次的排列数，由于最后一个 $n$ 和第一个 $1$ 会同时改变左右的峰，所以一共改变次数是 $a+b-2$
这 $a+b-2$ 中，有 $a-1$ 次是单独改左边（把 $1$ 和 $n$ 分配给左右边），考虑改的是哪几次，显然有 $\binom{a+b-2}{a-1}$ 种方法，于是答案就是 $f_{(n,a+b-2)} \times \binom{a+b-2}{a-1}$
然后发现 $f$ 就是第一类斯特林数，考虑第一类斯特林数的下降幂形式 $\prod\limits_{i=1}^{n-1} (x-i) = \sum\limits_{i=0}^n (-1)^{(n-i)} \times Stirling1(n,i) \times x^i$
右边是个生成函数，左边是 $n$ 个多项式相乘
所以分治+FFT即可
#include <bits/stdc++.h>
#define LL long long
#define rep(i, s, t) for(register int i = (s), i##end = (t); i <= i##end; ++i)
#define dwn(i, s, t) for(register int i = (s), i##end = (t); i >= i##end; --i)
using namespace std;
inline int read() {
int x = , f = ; char ch = getchar();
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -f;
for(; isdigit(ch); ch = getchar()) x = * x + ch - '';
return x * f;
}
const int mod = , maxn = ;
inline int inc(int x, int y) { x += y; if(x >= mod) x -= mod; return x; }
inline int dec(int x, int y) { x -= y; if(x < ) x += mod; return x; }
inline int mul(int x, int y) { return 1LL * x * y % mod; }
inline int ksm(int x, int t, int res = ) {
for(; t; x = mul(x, x), t = t >> )
if(t & ) res = mul(res, x); return res;
}
int f[maxn], fac[maxn], ifac[maxn], lg[maxn], r[maxn];
inline int C(int x, int y) { return mul(fac[x], mul(ifac[y], ifac[x - y])); }
vector<int> G[maxn];
int A[maxn], B[maxn], fnl[maxn];
inline void fft(int *a, int n, int f) {
rep(i, , n-) r[i] = (r[i >> ] >> ) | ((i & ) << (lg[n] - ));
rep(i, , n-) if(i < r[i]) swap(a[i], a[r[i]]);
for(register int i = ; i < n; i <<= ) {
int wn = ksm(, (mod - ) / (i << ));
if(f == -) wn = ksm(wn, mod - );
for(register int j = ; j < n; j += (i << )) {
int w = ;
for(register int k = ; k < i; ++k, w = mul(w, wn)) {
int x = a[j + k], y = mul(w, a[j + k + i]);
a[j + k] = inc(x, y);
a[j + k + i] = dec(x, y);
}
}
}
if(f == -) {
int inv_n = ksm(n, mod - );
rep(i, , n-) a[i] = mul(a[i], inv_n);
}
}
inline int mul(int wlen) {
fft(A, wlen, ); fft(B, wlen, );
rep(i, , wlen - ) A[i] = mul(A[i], B[i]);
fft(A, wlen, -); --wlen;
while(!A[wlen])--wlen; return wlen;
}
inline int Mul(int l, int r) {
if(l == r) return G[l].size() - ;
int mid = (l + r) >> ;
int ls = Mul(l, mid), rs = Mul(mid + , r);
int len = ; for(; len <= (ls + rs); len <<= );
rep(i, , ls) A[i] = G[l][i]; rep(i, ls+, len) A[i] = ;
rep(i, , rs) B[i] = G[mid+][i]; rep(i, rs+, len) B[i] = ;
G[l].clear(); G[mid+].clear(); len = mul(len);
rep(i, , len) G[l].push_back(A[i]);
return len;
}
int n, a, b;
int main() {
// freopen("sej.in","r",stdin);
// freopen("sej.out","w",stdout);
lg[] = -; rep(i, , maxn - ) lg[i] = lg[i >> ] + ;
n = read(), a = read(), b = read();
fac[] = fac[] = ifac[] = ifac[] = ;
rep(i, , a + b) fac[i] = mul(fac[i - ], i);
rep(i, , a + b) ifac[i] = mul(dec(, mod / i), ifac[mod % i]);
rep(i, , a + b) ifac[i] = mul(ifac[i], ifac[i - ]);
n--; rep(i, , n) G[i].push_back(dec(, i-)), G[i].push_back();
Mul(, n); rep(i, , G[].size() - ) fnl[i] = G[][i];
rep(i, , n) if((n-i) & ) fnl[i] = mul(fnl[i], dec(, ));
cout << mul(fnl[a + b - ], C(a + b - , a - )) << endl;
}