T1
Description
给定一张 \(n\) 个点的有向图，每个点可能是黑色，白色，或者无色，一开始这张图没有边。你要将这张图补充完整：
- 把每个无色的点涂上黑色或白色。
- 对于 \(\forall 1\leq i<j\leq n\)，你可以选择连 \(i→j\) 的有向边或者不连。
定义一条路径是合法的，当且仅当路径上相邻的点的颜色不同，路径可以只经过一个点。
定义一张图是合法的，当且仅当这张图的合法路径数为奇数。
求有多少种补充的方案使得图合法，答案对 \(998244353\) 取模。
\(1\leq n\leq 2×10^5\)。
时空限制 \(1s/128MB\)。
Solution
我们记 \(g_i\) 表示以点 \(i\) 为结尾的合法路径条数 \(\%2\) 的结果。要使得图合法，就是使得 \(n\) 个点中 \(g_i=1\) 的个数为奇数。
显然 \(g_i=(\sum_{j=1}^{i-1}[color_i≠color_j]g_j)\%2\ xor\ 1\)。可以发现 \(g_i\) 只跟 \(i\) 连了几个 \(color_i≠color_j\) 且 \(g_j=1\) 的点有关。假设连了 \(k\) 个这样的点 \(j\)。若 \(k\) 是偶数，\(g_i=1\)，否则 \(g_i=0\)。
考虑 \(dp\)，记 \(f[i][j][a][b]\) 表示前 \(i\) 个点，\(g\) 的异或和是 \(j(j∈[0,1])\)，\(g=1\) 的点中，有 \(a\) 个是白色，\(b\) 个是黑色的方案数。
考虑从 \(f[i-1][j][a][b]\) 转移过来。我们枚举点 \(i\) 染成白色还是黑色。当点 \(i\) 可以染成白色（点 \(i\) 原来是无色或白色）时，枚举 \(i\) 连了这 \(b\) 个点中的 \(k\) 个，有如下转移：$$f[i][j\ xor\ 1][a+1][b]+=f[i-1][j][a][b]×h_0[b]$$$$f[i][j][a][b]+=f[i-1][j][a][b]×h_1[b]$$
其中 \(h_0[b]\) 表示在大小为 \(b\) 的集合中选出偶数个元素的方案数，\(h_1[b]\) 表示在大小为 \(b\) 的集合中选出奇数个元素的方案数。
显然有$$b=0:h_0[b]=1,h_1[b]=0$$$$b>0:h_0[b]=h_1[b]=2^{b-1}$$
因此记 \(f[i][j][c][d],c∈[0,1],d∈[0,1]\) 表示前 \(i\) 个点，\(g\) 的异或和为 \(j\)，是否 \(a>0\)，是否 \(b>0\) 的方案数。
时间复杂度 \(O(n)\)。
Code
#include <bits/stdc++.h>
using namespace std;
#define ll long long
template <class t>
inline void read(t & res)
{
char ch; bool fl = 0; res = 0;
while (ch = getchar(), !isdigit(ch) && ch != '-');
ch == '-' ? fl = 1 : res = ch ^ 48;
while (ch = getchar(), isdigit(ch))
res = res * 10 + (ch ^ 48);
fl ? res = ~res + 1 : 0;
}
const int e = 2e5 + 5, mod = 998244353;
int f[e][2][2][2], n, ans, col[e], p[e];
inline void add(int &x, int y)
{
(x += y) >= mod && (x -= mod);
}
inline int plu(int x, int y)
{
add(x, y);
return x;
}
inline int s(int x, int y)
{
x += y;
return min(x, 1);
}
inline int mul(int x, int y)
{
return (ll)x * y % mod;
}
int main()
{
read(n);
int i, j, a, b;
for (i = 1; i <= n; i++) read(col[i]);
p[0] = 1;
for (i = 1; i <= n; i++) p[i] = plu(p[i - 1], p[i - 1]);
f[0][0][0][0] = 1;
for (i = 1; i <= n; i++)
for (j = 0; j <= 1; j++)
for (a = 0; a <= 1; a++)
for (b = 0; b <= 1; b++)
if (f[i - 1][j][a][b])
{
int v = f[i - 1][j][a][b];
if (col[i] != 1)
{
if (b)
{
add(f[i][j ^ 1][s(a, 1)][b], mul(v, p[i - 2]));
add(f[i][j][a][b], mul(v, p[i - 2]));
}
else add(f[i][j ^ 1][s(a, 1)][b], mul(v, p[i - 1]));
}
if (col[i] != 0)
{
if (a)
{
add(f[i][j ^ 1][a][s(b, 1)], mul(v, p[i - 2]));
add(f[i][j][a][b], mul(v, p[i - 2]));
}
else add(f[i][j ^ 1][a][s(b, 1)], mul(v, p[i - 1]));
}
}
for (a = 0; a <= 1; a++)
for (b = 0; b <= 1; b++)
add(ans, f[n][1][a][b]);
cout << ans << endl;
fclose(stdin);
fclose(stdout);
return 0;
}
T2
Description
给定一张 \(n\) 个点，\(m\) 条边的无向图，现在你要给每条边定向。
定义一张有向图合法，当且仅当存在一个点 \(u\)，使得 \(1\) 能走到 \(u\) 且 \(2\) 能走到 \(u\)。
求 \(2^m\) 种定向方案中，有多少种定向之后的图是合法的。
答案对 \(10^9+7\) 取模，\(n\leq 15，m\leq\frac{n(n-1)}{2}\)。
时空限制 \(1s/128MB\)。
Solution
考虑补集转化，即求出不合法的定向方案数。
\(S\) 的导出子图包括 \(S\) 中的点，两点都在 \(S\) 中的边。
枚举集合 \(S,T\)，保证 \(1∈S,2∈T,S∩T=\varnothing\)。假设已经求出了： \(f[S]\) 表示给 \(S\) 的导出子图中的边定向，使得 \(1\) 能走到 \(S\) 中的所有点的方案数，\(g[T]\) 表示给 \(T\) 的导出子图中的边定向，使得 \(2\) 能走到 \(T\) 中的所有点的方案数。
我们强制 \(1\) 走不到 \(S\) 以外的点，\(2\) 走不到 \(T\) 以外的点。那么要保证不存在横跨 \(S,T\) 的边，且不属于 \(S∪T\) 的点和 \(S,T\) 中的点的连边的方向已经确定。设 \(\complement(S∪T)\) 的导出子图边数为 \(cnt\)，那么 $$ans+=f[S]×g[T]×2^{cnt}$$
接下来考虑怎么求 \(f[S]\)。\(g[T]\) 同理。
同样考虑补集转化，先令 \(f[S]=2^{S的导出子图边数}\)。接下来，枚举 \(S\) 的一个真子集 \(T\)，强制 \(1\) 只能走到 \(T\) 中的点。那么 \(T\) 和 \(S∩\complement T\) 之间的边的方向已经确定，设 \(S∩\complement T\) 的导出子图边数为 \(cnt\)，那么 $$f[S]-=f[T]×2^{cnt}$$ 时间复杂度 \(O(3^n)\)。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
template <class t>
inline void read(t & res)
{
char ch;
while (ch = getchar(), !isdigit(ch));
res = ch ^ 48;
while (ch = getchar(), isdigit(ch))
res = res * 10 + (ch ^ 48);
}
const int e = (1 << 15) + 5, mod = 1e9 + 7;
int f[e], g[e], h[e], n, m, ans, p[e], id, tmp;
inline void add(int &x, int y)
{
(x += y) >= mod && (x -= mod);
}
inline void del(int &x, int y)
{
(x -= y) < 0 && (x += mod);
}
inline int mul(int x, int y)
{
return (ll)x * y % mod;
}
int main()
{
read(n); read(m); read(id); tmp = 1 << n;
int i, x, y, s, t;
p[0] = 1;
for (i = 1; i <= m; i++)
{
read(x); read(y);
p[i] = 2ll * p[i - 1] % mod;
for (s = 0; s < tmp; s++)
if ((s & (1 << x - 1)) && (s & (1 << y - 1))) h[s]++;
}
ans = p[m];
f[1] = 1;
for (s = 2; s < tmp; s++)
if (s & 1)
{
f[s] = p[h[s]];
for (t = (s - 1) & s; t; t = (t - 1) & s)
del(f[s], mul(f[t], p[h[s ^ t]]));
}
g[2] = 1;
for (s = 3; s < tmp; s++)
if (s & 2)
{
g[s] = p[h[s]];
for (t = (s - 1) & s; t; t = (t - 1) & s)
del(g[s], mul(g[t], p[h[s ^ t]]));
}
for (i = 0; i < tmp; i++)
for (t = i; t; t = (t - 1) & i)
if (t & 2)
{
s = (tmp - 1) ^ i;
if (s & 1 && (h[s | t] - h[s] - h[t] == 0))
del(ans, mul(mul(f[s], g[t]), p[h[(tmp - 1) ^ (s | t)]]));
}
cout << ans << endl;
fclose(stdin);
fclose(stdout);
return 0;
}
T3
Description
给定一个长度为 \(n\) 的只包含小写英文字母的字符串 \(s\)，你需要找到一个最大的 \(k\)，使得存在：
（即 \(k\) 个区间 \([l_1,r_1][l_2,r_2]\dots[l_k,r_k]\) 的左右端点都递增且两两不相交）
使得对于每个 \(1\le i<k\)，都满足 \(s[l_{i+1}\dots r_{i+1}]\) 是 \(s[l_i\dots r_i]\) 的严格子串。
其中 \(s[l\dots r]\) 表示字符串 \(s\) 的第 \(l\) 到第 \(r\) 个字符组成的字符串。
字符串 \(A\) 是字符串 \(B\) 的严格子串，当且仅当从 \(B\) 的开头和结尾各删掉若干个字符（从开头和结尾删掉的字符个数都可以是零个，但删掉的字符个数之和必须大于 \(0\)）能够得到 \(A\)。
\(n\leq 5×10^5\)。
时空限制 \(2.5s/512MB\)。
Solution
首先要知道几个性质：
- 最优情况下，所有的 \(s[l_i\dots r_i]\) 都是 \(s[l_{i+1}\dots r_{i+1}]\) 在开头或结尾添加一个字符得到的，且 \(l_k=r_k\)。
- 记 \(f_i\) 表示 \(l_1=i\) 时，\(k\) 最大是多少，有 \(f_i\leq f_{i+1}+1\)
考虑证明性质 \(2\)，即 \(f_{i+1}\geq f_i-1\)。
假设已经得到一个 \(l_1=i\)，且 \(f_i=k\) 的划分方案。在这个方案中，若 \(s[l_j\dots r_j]\) 是 \(s[l_{j+1}\dots r_{j+1}]\) 在开头加字符得到的，记 \(a_j=0\)，否则 \(a_j=1\)。考虑去掉 \(s[l_1\dots r_1]\) 的第一个字符，即 \(l_1++\)。
接下来令 \(j=1\)，如果 \(a_j=1\)，那么令 \(l_{j+1}++,j++\)，继续循环。否则此时必有 \(s[l_j\dots r_j]=s[l_{j+1}\dots r_{j+1}]\)，那么把 \(s[l_{j+1}\dots r_{j+1}]\) 删掉即可。这样就得到了一个 \(f_{i+1}=k\) 的划分方案。
因此每次先令 \(f_i=f_{i+1}+1\)，判断这个 \(f_i\) 是否能取到，不能就 \(f_i--\)，直到 \(f_i=1\)。答案就是 \(max(f_i)\)。
问题转化为判断是否 \(f_i\leq mid\)。显然需要存在一个 \(j\) 满足下面 \(3\) 个条件：
- \(i+mid\leq j\leq n\)
- \(max(lcp(suf_i,suf_j),lcp(suf_{i+1},suf_j)\geq mid-1\)
- \(f_j\geq mid-1\)
求出 \(sa,rank\) 数组，那么条件 \(2\) 可以看作是 \(rank_j∈[l,r]\)，\([l,r]\) 可以用二分 + \(\text{RMQ}\) 求出。
那我们要求的就是满足 \(i+mid\leq j\leq n,rank_j∈[l,r]\) 的 \(max(f_j)\)。主席树即可，时间复杂度 \(O(n \log n)\)。
Code
#include <bits/stdc++.h>
using namespace std;
const int e = 1e6 + 5;
struct node
{
int l, r, w;
}c[e * 30];
char s[e];
int rk[e], h[e], w[e], sa[e], a[e], b[e], tot, tmp[e], f[e], n, ans = 1, d[e][20], rt[e];
int logn[e], pool;
inline void init()
{
int i, k, r = 0, j;
for (i = 1; i <= n; i++) w[s[i]]++;
for (i = 1; i <= 256; i++) w[i] += w[i - 1];
for (i = n; i >= 1; i--) sa[w[s[i]]--] = i;
for (i = 1; i <= n; i++)
if (s[sa[i - 1]] == s[sa[i]]) a[sa[i]] = r;
else a[sa[i]] = ++r;
for (k = 1; r < n; k <<= 1)
{
tot = 0;
for (i = n - k + 1; i <= n; i++) b[++tot] = i;
for (i = 1; i <= n; i++)
if (sa[i] > k) b[++tot] = sa[i] - k;
for (i = 1; i <= n; i++) w[a[b[i]]] = 0;
for (i = 1; i <= n; i++) w[a[b[i]]]++;
for (i = 2; i <= n; i++) w[i] += w[i - 1];
for (i = n; i >= 1; i--) sa[w[a[b[i]]]--] = b[i];
for (i = 1; i <= n; i++) tmp[i] = a[i];
r = 0;
for (i = 1; i <= n; i++)
if (tmp[sa[i]] == tmp[sa[i - 1]] && tmp[sa[i] + k] == tmp[sa[i - 1] + k])
a[sa[i]] = r; else a[sa[i]] = ++r;
}
for (i = 1; i <= n; i++) rk[sa[i]] = i;
for (i = 1; i <= n; i++)
{
if (rk[i] == 1) continue;
h[i] = max(0, h[i - 1] - 1);
int x = sa[rk[i] - 1];
while (s[i + h[i]] == s[x + h[i]] && max(i, x) + h[i] <= n) h[i]++;
}
logn[0] = -1;
for (i = 1; i <= n; i++) logn[i] = logn[i >> 1] + 1, d[i][0] = h[sa[i]];
for (j = 1; (1 << j) <= n; j++)
for (i = 1; i + (1 << j) - 1 <= n; i++)
d[i][j] = min(d[i][j - 1], d[i + (1 << j - 1)][j - 1]);
}
inline int ask(int l, int r)
{
if (l > r) swap(l, r);
if (l == r) return n - sa[l] + 1;
l++;
int k = logn[r - l + 1];
return min(d[l][k], d[r - (1 << k) + 1][k]);
}
inline void insert(int y, int &x, int l, int r, int s, int v)
{
c[x = ++pool] = c[y];
c[x].w = max(c[x].w, v);
if (l == r) return;
int mid = l + r >> 1;
if (s <= mid) insert(c[y].l, c[x].l, l, mid, s, v);
else insert(c[y].r, c[x].r, mid + 1, r, s, v);
}
inline int query(int x, int l, int r, int s, int t)
{
if (l == s && r == t) return c[x].w;
int mid = l + r >> 1;
if (t <= mid) return query(c[x].l, l, mid, s, t);
else if (s > mid) return query(c[x].r, mid + 1, r, s, t);
else return max(query(c[x].l, l, mid, s, mid),
query(c[x].r, mid + 1, r, mid + 1, t));
}
inline void upt(int &s, int &t, int x, int len)
{
int l = 1, pos = rk[x], r = pos;
s = pos;
while (l <= r)
{
int mid = l + r >> 1;
if (ask(mid, pos) >= len) s = mid, r = mid - 1;
else l = mid + 1;
}
t = pos;
l = pos; r = n;
while (l <= r)
{
int mid = l + r >> 1;
if (ask(pos, mid) >= len) t = mid, l = mid + 1;
else r = mid - 1;
}
}
inline bool check(int x, int mid)
{
int l, r, s = x + mid, t = n;
if (s > t) return 0;
upt(l, r, x, mid - 1);
if (query(rt[s], 1, n, l, r) >= mid - 1) return 1;
upt(l, r, x + 1, mid - 1);
return query(rt[s], 1, n, l, r) >= mid - 1;
}
int main()
{
cin >> n;
scanf("%s", s + 1);
n = strlen(s + 1);
init();
f[n] = 1;
int i;
insert(rt[n + 1], rt[n], 1, n, rk[n], 1);
for (i = n - 1; i >= 1; i--)
{
f[i] = f[i + 1] + 1;
while (f[i] > 1 && !check(i, f[i])) f[i]--;
ans = max(ans, f[i]);
insert(rt[i + 1], rt[i], 1, n, rk[i], f[i]);
}
cout << ans << endl;
fclose(stdin);
fclose(stdout);
return 0;
}