T1 线性代数
实际上我们需要求解值域 \(\le n\) 的线性空间的个数，考虑将线性空间与线性基一一对应，为了使得一个线性基唯一对应一个线性空间，我们将主元列上的非主元全部消成 \(0\) ，发现此时将线性基全部异或得到的值为原集合的最大值，并且可以做到一一对应。（化简为最简阶梯形矩阵）
于是考虑进行 dp ，设 \(f_{i,j,k=0/1}\) 表示当前考虑到了第 \(i\) 位，总共有 \(j\) 个主元，是否卡到了上界的方案数，枚举第 \(i\) 位为 \(c\) ，考虑第 \(i\) 为是否为主元，如果为主元，则 \(f_{i+1,j,k}\to f_{i,j+1,[k\operatorname{and}c=bit_i]}\) ，如果不是主元，由于最大值是将所有数进行异或，假设当前第 \(i\) 位异或的结果为 \(c\) ，当 \(c\) 为 \(1\) 时，发现 \(\sum_{k=0}^{\infty}\binom{j}{2k}=2^{j-1}\) ，当 \(c\) 为 \(0\) 时，发现 \(\sum_{k=0}^{\infty}\binom{j}{2k+1}=2^{j-1}\) ，因此有转移 \(f_{i+1,j,k}\times 2^{j-1}\to f_{i,j,[k\operatorname{and}c=bit_i]}\) 。
code
#include <cstdio>
#include <algorithm>
using namespace std;
const int max1 = 45;
const int mod = 1e9 + 7;
int n, f[max1 + 5][max1 + 5][2], ans;
void Add ( int &x, int y )
{
x = x + y;
if ( x >= mod )
x = x - mod;
return;
}
int main ()
{
freopen("algebra.in", "r", stdin);
freopen("algebra.out", "w", stdout);
scanf("%d", &n);
f[30][0][1] = 1;
for ( int i = 29; i >= 0; i -- )
{
for ( int j = 0; j <= 30; j ++ )
{
for ( int k = 0; k < 2; k ++ )
{
int m = k ? ( n >> i & 1 ) : 1;
for ( int c = 0; c <= m; c ++ )
{
if ( c )
Add(f[i][j + 1][k && c == m], f[i + 1][j][k]);
if ( j > 0 || !c )
Add(f[i][j][k && c == m], ( 1LL << max(j - 1, 0) ) * f[i + 1][j][k] % mod);
}
}
}
}
for ( int j = 0; j <= 30; j ++ )
for ( int k = 0; k < 2; k ++ )
Add(ans, f[0][j][k]);
printf("%d\n", ans);
return 0;
}
T2 森林
容易发现联通块很难进行枚举，因此考虑枚举一条链，比较显然存在一种 \(O(n^2)\) 的做法：枚举根节点 \(i\) ，从 \(i\) 开始 Dfs ，考虑判断链 \(i\to u\) 上的点在第一棵树上是一个联通块，只需要判断这些点之间的连边个数 \(sum\) 等于链长 \(len\) 减一即可。
考虑优化枚举的过程，一个比较套路的想法是用点分治优化链的枚举，假设当前的分治重心为 \(x\) ，我们只考虑长度大于 \(1\) 的链，首先考虑查询，假设当前递归到的节点为 \(v\) ，假设之前扫过的点组成的集合为 \(S\) ，那么我们需要求解 \(\sum_{u\in S}f(u,v)\) ，其中当 \(u\to v\) 的链在第一棵树中为一个联通块时， \(f\) 函数返回 \(1\) ，否则返回 \(0\) 。发现对于一条链，链长减边数的最小值为 \(1\) ，也就是链长减边数取到最小值时合法，因此考虑用线段树维护区间最小值以及最小值的个数，由于 \(v\) 可以进行枚举，因此考虑在线段树第 \(u\) 个叶节点维护 \(f(u,v)\) 的值，假设当前我们已将加入了 \(father_v\) 到 \(x\) 的链所造成的贡献，考虑连接 \(v\) 所造成的影响，枚举第 \(1\) 棵树中与 \(v\) 相连的点 \(a\) ，如果 \(a\in S\) ，显然此时造成的影响是对 \(a\) 子树内所有点区间加，如果 \(a\) 位于 \(x\to v\) 的链上，那么会造成全局加的影响，如果是其他情况，那么没有贡献，很容易用线段树维护上述操作。
code
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int max1 = 1e5;
const int inf = 0x3f3f3f3f;
int T, n;
long long ans;
vector <int> edge[2][max1 + 5];
int siz[max1 + 5], root;
bool vis[max1 + 5], flag[max1 + 5], is_ancestor[max1 + 5];
int in[max1 + 5], out[max1 + 5], dfs_clock;
int val[max1 + 5];
struct Data
{
int min_val, cnt;
Data () {}
Data ( int __min_val, int __cnt )
{ min_val = __min_val, cnt = __cnt; }
Data operator + ( const Data &A ) const
{
if ( min_val < A.min_val )
return *this;
else if ( min_val > A.min_val )
return A;
return Data(min_val, cnt + A.cnt);
}
};
struct Segment_Tree
{
#define lson(now) ( now << 1 )
#define rson(now) ( now << 1 | 1 )
Data tree[max1 * 4 + 5];
int tag[max1 * 4 + 5];
void Push_Down ( int now )
{
if ( tag[now] )
{
tree[lson(now)].min_val += tag[now];
tree[rson(now)].min_val += tag[now];
tag[lson(now)] += tag[now];
tag[rson(now)] += tag[now];
tag[now] = 0;
}
return;
}
void Build ( int now, int l, int r )
{
tag[now] = 0;
if ( l == r )
{ tree[now] = Data(inf, 1); return; }
int mid = l + r >> 1;
Build(lson(now), l, mid);
Build(rson(now), mid + 1, r);
tree[now] = tree[lson(now)] + tree[rson(now)];
return;
}
void Insert ( int now, int l, int r, int pos, const Data &d )
{
if ( l == r )
{ tree[now] = d; return; }
Push_Down(now);
int mid = l + r >> 1;
if ( pos <= mid )
Insert(lson(now), l, mid, pos, d);
else
Insert(rson(now), mid + 1, r, pos, d);
tree[now] = tree[lson(now)] + tree[rson(now)];
return;
}
void Update ( int now, int l, int r, int ql, int qr, int x )
{
if ( l >= ql && r <= qr )
{
tree[now].min_val += x;
tag[now] += x;
return;
}
Push_Down(now);
int mid = l + r >> 1;
if ( ql <= mid )
Update(lson(now), l, mid, ql, qr, x);
if ( qr > mid )
Update(rson(now), mid + 1, r, ql, qr, x);
tree[now] = tree[lson(now)] + tree[rson(now)];
return;
}
}Tree;
void Get_Size ( int now, int fa )
{
siz[now] = 1;
for ( auto v : edge[1][now] )
{
if ( v == fa || vis[v] )
continue;
Get_Size(v, now);
siz[now] += siz[v];
}
return;
}
void Get_Root ( int now, int fa, int sum )
{
bool is_root = true;
for ( auto v : edge[1][now] )
{
if ( v == fa || vis[v] )
continue;
Get_Root(v, now, sum);
if ( siz[v] > sum >> 1 )
is_root = false;
}
if ( sum - siz[now] > sum >> 1 )
is_root = false;
if ( is_root )
root = now;
return;
}
void Clear ( int now, int fa )
{
in[now] = out[now] = 0;
flag[now] = true;
for ( auto v : edge[1][now] )
{
if ( v == fa || vis[v] )
continue;
Clear(v, now);
}
return;
}
void End_Flag ( int now, int fa )
{
flag[now] = false;
for ( auto v : edge[1][now] )
{
if ( v == fa || vis[v] )
continue;
End_Flag(v, now);
}
return;
}
void Query ( int now, int fa, int depth, int sum, int pre )
{
for ( auto v : edge[0][now] )
{
if ( flag[v] )
{
if ( in[v] )
Tree.Update(1, 1, sum, in[v], out[v], -1);
else if ( is_ancestor[v] )
Tree.Update(1, 1, sum, 1, pre, -1);
}
}
is_ancestor[now] = true;
Data d = Tree.tree[1];
if ( d.min_val == 1 - depth )
ans += d.cnt;
for ( auto v : edge[1][now] )
{
if ( v == fa || vis[v] )
continue;
Query(v, now, depth + 1, sum, pre);
}
is_ancestor[now] = false;
for ( auto v : edge[0][now] )
{
if ( flag[v] )
{
if ( in[v] )
Tree.Update(1, 1, sum, in[v], out[v], 1);
else if ( is_ancestor[v] )
Tree.Update(1, 1, sum, 1, pre, 1);
}
}
return;
}
void Update ( int now, int fa, int depth, int sum )
{
in[now] = ++dfs_clock;
val[now] = val[fa];
for ( auto v : edge[0][now] )
if ( is_ancestor[v] )
++val[now];
is_ancestor[now] = true;
Tree.Insert(1, 1, sum, in[now], Data(depth - val[now], 1));
for ( auto v : edge[1][now] )
{
if ( v == fa || vis[v] )
continue;
Update(v, now, depth + 1, sum);
}
out[now] = dfs_clock;
is_ancestor[now] = false;
return;
}
void Dfs ( int now, int sum )
{
Clear(now, 0);
dfs_clock = 0;
Tree.Build(1, 1, sum);
in[now] = out[now] = ++dfs_clock;
val[now] = 0;
is_ancestor[now] = true;
Tree.Insert(1, 1, sum, in[now], Data(1 - val[now], 1));
for ( auto v : edge[1][now] )
{
if ( vis[v] )
continue;
Query(v, now, 1, sum, out[now]);
Update(v, now, 2, sum);
out[now] = dfs_clock;
}
End_Flag(now, 0);
is_ancestor[now] = false;
vis[now] = true;
for ( auto v : edge[1][now] )
{
if ( vis[v] )
continue;
Get_Size(v, now);
Get_Root(v, now, siz[v]);
Dfs(root, siz[v]);
}
return;
}
void Work ()
{
scanf("%d", &n);
for ( int i = 1; i <= n; i ++ )
edge[0][i].clear(), edge[1][i].clear();
for ( int i = 1, u, v; i <= n - 1; i ++ )
{
scanf("%d%d", &u, &v);
edge[0][u].push_back(v);
edge[0][v].push_back(u);
}
for ( int i = 1, u, v; i <= n - 1; i ++ )
{
scanf("%d%d", &u, &v);
edge[1][u].push_back(v);
edge[1][v].push_back(u);
}
ans = 0;
for ( int i = 1; i <= n; i ++ )
vis[i] = is_ancestor[i] = flag[i] = false;
Get_Size(1, 0);
Get_Root(1, 0, siz[1]);
Dfs(root, siz[1]);
ans += n;
printf("%lld\n", ans);
return;
}
int main ()
{
freopen("forest.in", "r", stdin);
freopen("forest.out", "w", stdout);
scanf("%d", &T);
while ( T -- )
Work();
return 0;
}
T3 字符串
发现题解做法需要用 SAM ，考虑抛弃题解。
考虑用 SA 代替 SAM ，发现题解中 SAM 的主要作用是维护有序的 endpos 集合，设当前询问的区间为 \([l,r]\) ，由于与 \(s(l,n)\) 匹配长度大于 \(r-l+1\) 的后缀在 SA 上表现为一段连续的区间，因此可以用 SA + ST 表找到这段区间，此时我们只需要得到有序的 endpos 集合，显然可以用主席树进行维护。
首先考虑暴力的做法，假设得到询问串所匹配的 endpos 集合为 \(S\) ，如果在位置 \(x\) 之前插入 * ，那么所有包含 \(x-1\) 的区间都会无法匹配，因此设上一次在第 \(k\) 个位置前插入 * ，找到第一个区间左端点大于等于 \(k\) 的区间，此时贪心的在第 \(r\) 个位置之前插入 * 最优。
很容易发现这个过程可以用主席树优化，发现记忆化后复杂度正确，简单证明一下，我们取阀值 \(B=\sqrt{n}\) ，对于 \(len\le B\) 的询问，发现最多扫过 \(n\sqrt{n}\) 个区间，复杂度为 \(O(n\sqrt{n}\log n)\) ，对于 \(len> B\) 的询问，发现 \(res\le B\) ，因此复杂度为 \(O(q\sqrt{n}\log n)\) 。
code
#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>
#include <iostream>
using namespace std;
const int max1 = 1e5;
const int inf = 0x3f3f3f3f;
int n, q;
char s[max1 + 5];
int lim, x[max1 + 5], y[max1 + 5], bin[max1 + 5];
int sa[max1 + 5], rk[max1 + 5], height[max1 + 5];
map < pair <int, int>, int > Map;
void Suffix_Array ()
{
lim = 26;
for ( int i = 1; i <= n; i ++ )
x[i] = s[i] - 'a' + 1;
for ( int i = 1; i <= n; i ++ )
++bin[x[i]];
for ( int i = 1; i <= lim; i ++ )
bin[i] += bin[i - 1];
for ( int i = n; i >= 1; i -- )
sa[bin[x[i]]--] = i;
for ( int w = 1; w <= n; w <<= 1 )
{
int num = 0;
for ( int i = n - w + 1; i <= n; i ++ )
y[++num] = i;
for ( int i = 1; i <= n; i ++ )
if ( sa[i] > w )
y[++num] = sa[i] - w;
for ( int i = 1; i <= lim; i ++ )
bin[i] = 0;
for ( int i = 1; i <= n; i ++ )
++bin[x[i]];
for ( int i = 1; i <= lim; i ++ )
bin[i] += bin[i - 1];
for ( int i = n; i >= 1; i -- )
sa[bin[x[y[i]]]--] = y[i];
for ( int i = 1; i <= n; i ++ )
y[i] = x[i];
num = 1, x[sa[1]] = 1;
for ( int i = 2; i <= n; i ++ )
{
if ( y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + w] == y[sa[i] + w] )
x[sa[i]] = num;
else
x[sa[i]] = ++num;
}
lim = num;
if ( lim == n )
break;
}
for ( int i = 1; i <= n; i ++ )
rk[sa[i]] = i;
for ( int i = 1; i <= n; i ++ )
{
if ( rk[i] == 1 )
continue;
int k = height[rk[i - 1]];
if ( k )
--k;
while ( i + k <= n && sa[rk[i] - 1] + k <= n && s[i + k] == s[sa[rk[i] - 1] + k] )
++k;
height[rk[i]] = k;
}
return;
}
struct ST_List
{
int list[max1 + 5][20];
void Pre_Work ()
{
int now = 0;
for ( int i = 1; i <= n; i ++ )
list[i][0] = height[i];
for ( int j = 1; j < 20; j ++ )
for ( int i = 1; i + ( 1 << j ) - 1 <= n; i ++ )
list[i][j] = min(list[i][j - 1], list[i + ( 1 << j - 1 )][j - 1]);
return;
}
int Query_Pre ( int pos, int k )
{
for ( int i = 19; i >= 0; i -- )
if ( pos - ( 1 << i ) + 1 >= 1 && list[pos - ( 1 << i ) + 1][i] >= k )
pos -= 1 << i;
return pos;
}
int Query_Next ( int pos, int k )
{
++pos;
for ( int i = 19; i >= 0; i -- )
if ( pos + ( 1 << i ) - 1 <= n && list[pos][i] >= k )
pos += 1 << i;
return pos - 1;
}
}ST;
struct President_Tree
{
#define lson(now) tree[now].son[0]
#define rson(now) tree[now].son[1]
#define sum(now) tree[now].sum
struct Struct_President_Tree
{ int son[2], sum; } tree[max1 * 40 + 5];
int root[max1 + 5], total;
void Clear ()
{ root[0] = total = lson(0) = rson(0) = sum(0) = 0; return; }
int Insert ( int pre, int l, int r, int pos )
{
int now = ++total;
tree[now] = tree[pre];
++sum(now);
if ( l == r )
return now;
int mid = l + r >> 1;
if ( pos <= mid )
lson(now) = Insert(lson(pre), l, mid, pos);
else
rson(now) = Insert(rson(pre), mid + 1, r, pos);
return now;
}
void Insert ( int pos, int val )
{ root[pos] = Insert(root[pos - 1], 1, n, val); return; }
int Query ( int L, int R, int l, int r, int pos )
{
if ( !( sum(R) - sum(L) ) )
return inf;
if ( l == r )
return l;
int mid = l + r >> 1, res = inf;
if ( pos <= mid )
res = Query(lson(L), lson(R), l, mid, pos);
if ( res == inf )
res = Query(rson(L), rson(R), mid + 1, r, pos);
return res;
}
int Query ( int L, int R, int pos )
{ return Query(root[L - 1], root[R], 1, n, pos); }
}Tree;
void Solve ()
{
int l, r;
scanf("%d%d", &l, &r);
if ( l == r )
printf("-1\n");
else
{
int L = ST.Query_Pre(rk[l], r - l + 1), R = ST.Query_Next(rk[l], r - l + 1);
if ( Map.find(make_pair(L, r - l + 1)) != Map.end() )
printf("%d\n", Map[make_pair(L, r - l + 1)]);
else
{
int k = 0, res = 0;
while ( k < inf )
{
k = Tree.Query(L, R, k) + r - l;
++res;
}
Map[make_pair(L, r - l + 1)] = res - 1;
printf("%d\n", res - 1);
}
}
return;
}
int main ()
{
freopen("string.in", "r", stdin);
freopen("string.out", "w", stdout);
scanf("%d%d%s", &n, &q, s + 1);
Suffix_Array();
cerr << "Suffix" << endl;
ST.Pre_Work();
cerr << "ST" << endl;
Tree.Clear();
for ( int i = 1; i <= n; i ++ )
Tree.Insert(i, sa[i]);
cerr << "Tree" << endl;
while ( q -- )
Solve();
return 0;
}