T1 码灵鼠 \text{T1 码灵鼠} T1 码灵鼠

Description \text{Description} Description

对于数列 a a a：

• a 0 = 1 a_0 = 1 a0​=1

• a n = a i + a j ( n ≥ 1 , i , j a_n = a_i + a_j(n\ge1,i,j an​=ai​+aj​(n≥1,i,j 均在 [ 0 , n − 1 ] [0,n-1] [0,n−1] 内均匀随机 ) ) )

请求出对于给定的 n n n， a n a_n an​ 的期望值是多少。

• 0 ≤ n ≤ 2147483647 0\le n\le2147483647 0≤n≤2147483647。

Solution \text{Solution} Solution

你算一下前三项：

a 0 = 1 a_0=1 a0​=1

a 1 = ( a 0 + a 0 ) ÷ 1 = 2 a_1=(a_0+a_0)\div1=2 a1​=(a0​+a0​)÷1=2

a 2 = [ ( a 0 + a 0 ) + ( a 0 + a 1 ) + ( a 1 + a 0 ) + ( a 1 + a 1 ) ] ÷ 4 = 3 a_2=[(a_0+a_0)+(a_0+a_1)+(a_1+a_0)+(a_1+a_1)]\div4=3 a2​=[(a0​+a0​)+(a0​+a1​)+(a1​+a0​)+(a1​+a1​)]÷4=3

于是你就猜 a n = n + 1 a_n=n+1 an​=n+1。

然后就对了（

现在我们来用数学归纳法证明一下（过程可能有不严谨之处，请见谅）：

当 n = 0 n=0 n=0 时， a 0 = 1 a_0=1 a0​=1，成立。

当 ∀ i ∈ [ 0 , n − 1 ] , a i − 1 = i \forall i\in[0,n-1],a_{i-1}=i ∀i∈[0,n−1],ai−1​=i 成立时，设 E ( x ) E(x) E(x) 为 x x x 的期望值，我们有

a n = E ( a i + a J ) ( ∀ i , j ∈ [ 0 , n − 1 ] ) = E ( a i ) + E ( a j ) ( ∀ i , j ∈ [ 0 , n − 1 ] ) = 2 × E ( a i ) ( ∀ i ∈ [ 0 , n − 1 ] ) = 2 × ∑ i = 0 n − 1 a i n = 2 × 1 + 2 + ⋯ + n 2 n = n + 1 \begin{aligned}a_n&=E(a_i+a_J)(\forall i,j\in[0,n-1])\\&=E(a_i)+E(a_j)(\forall i,j\in[0,n-1])\\&=2\times E(a_i)(\forall i\in[0,n-1])\\&=2\times\dfrac{\sum_{i=0}^{n-1}a_i}{n}\\&=2\times\dfrac{\dfrac{1+2+\cdots+n}{2}}{n}\\&=n+1\end{aligned} an​​=E(ai​+aJ​)(∀i,j∈[0,n−1])=E(ai​)+E(aj​)(∀i,j∈[0,n−1])=2×E(ai​)(∀i∈[0,n−1])=2×n∑i=0n−1​ai​​=2×n21+2+⋯+n​​=n+1​

证毕。

记得特判 n = 2147483647 n=2147483647 n=2147483647， n + 1 n+1 n+1 爆 int 了（不然会丢 30 30 30 分）。

时间复杂度 O ( T ) \mathcal{O}(T) O(T)。

Code \text{Code} Code

#include <iostream>
#include <cstdio>
using namespace std;

int main()
{
	int t;
	scanf("%d", &t);
	while (t--)
	{
		int n;
		scanf("%d", &n);
		if (n == 2147483647)
		{
			puts("2147483648");
		}
		else
		{
			printf("%d\n", n + 1);
		}
	}
	return 0;
}

T2 So many prefix? \text{T2 So many prefix?} T2 So many prefix?

Description \text{Description} Description

给定一个字符串 S S S，请求出所有长度为偶数的 S S S 的前缀在 S S S 中出现的次数和。

• 对于 30 % 30\% 30% 的数据， ∣ S ∣ ≤ 100 |S|\le100 ∣S∣≤100，保证数据随机；
• 对于 100 % 100\% 100% 的数据， ∣ S ∣ ≤ 200000 |S|\le200000 ∣S∣≤200000。

Solution \text{Solution} Solution

提供 2 2 2 种思路，剩下一种请咨询 xhj：

1. A C 1. \rm{AC} 1.AC 自动机 + + + 拓扑建图优化

只考虑偶数的话就和 LUOGU5357 【模板】AC自动机（二次加强版） 差不多了。

对于偶数位上的都给 p o s pos pos 打上标记，然后 search ⁡ \operatorname{search} search 时遇上有标记的就不停地跳 f a i l fail fail 同时将 ans++。

这个的时间复杂度是 O ( ∣ S ∣ 2 ) \mathcal{O}(|S|^2) O(∣S∣2) 的。

那么加一个拓扑建图优化即可。

时间复杂度 O ( ∣ S ∣ ) \mathcal{O}(|S|) O(∣S∣)。

2. K M P + D P 2. \rm{KMP+\rm{DP}} 2.KMP+DP

设 d p i dp_i dpi​ 为长度为 i i i 的前缀的答案。

那么显然有 d p i = { d p n x t i + 1 i ≡ 0 ( m o d 2 ) d p n x t i i ≡ 1 ( m o d 2 ) dp_i=\begin{cases}dp_{nxt_i}+1&i\equiv0\pmod{2}\\dp_{nxt_i}&i\equiv1\pmod{2}\end{cases} dpi​={dpnxti​​+1dpnxti​​​i≡0(mod2)i≡1(mod2)​

所以 for ⁡ \operatorname{for} for 一遍边推边求和即可。

时间复杂度 O ( ∣ S ∣ ) \mathcal{O}(|S|) O(∣S∣)。

Code \text{Code} Code

1. 1. 1.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

const int MAXN = 2e5 + 5;

int len, tot, cnt;
int trie[MAXN][26], id[MAXN], fail[MAXN], head[MAXN], siz[MAXN];

struct edge
{
	int to, nxt;
}e[MAXN];

void add(int u, int v)
{
	e[++cnt] = edge{v, head[u]};
	head[u] = cnt;
}

void insert(char *s)
{
	int pos = 0;
	for (int i = 0; i < len; i++)
	{
		int c = s[i] - 'a';
		if (!trie[pos][c])
		{
			trie[pos][c] = ++tot;
		}
		pos = trie[pos][c];
		if (i & 1)
		{
			id[(i + 1) >> 1] = pos;
		}
	}
}

void build()
{
	queue<int> q;
	for (int c = 0; c < 26; c++)
	{
		if (trie[0][c])
		{
			q.push(trie[0][c]);
		}
	}
	while (!q.empty())
	{
		int u = q.front();
		q.pop();
		for (int c = 0; c < 26; c++)
		{
			int v = trie[u][c];
			if (v)
			{
				fail[v] = trie[fail[u]][c];
				q.push(v);
			}
			else
			{
				trie[u][c] = trie[fail[u]][c];
			}
		}
	}
}

void search(char *s)
{
	int pos = 0, res = 0;
	for (int i = 0; i < len; i++)
	{
		int c = s[i] - 'a';
		pos = trie[pos][c];
		siz[pos]++;
	}
	for (int i = 1; i <= tot; i++)
	{
		add(fail[i], i);
	}
}

void dfs(int u)
{
	for (int i = head[u]; i; i = e[i].nxt)
	{
		int v = e[i].to;
		dfs(v);
		siz[u] += siz[v];
	}
}

char s[MAXN];

int main()
{
	scanf("%s", s);
	len = strlen(s);
	insert(s);
	build();
	search(s);
	dfs(0);
	int ans = 0;
	for (int i = 1; i <= (len >> 1); i++)
	{
		ans += siz[id[i]]; //只对偶数求和
	}
	printf("%d\n", ans);
	return 0;
}

2. 2. 2.

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int MAXN = 2e5 + 5;

char s[MAXN];
int nxt[MAXN], dp[MAXN];

int main()
{
	scanf("%s", s + 1);
	int len = strlen(s + 1);
	for (int i = 2, j = 0; i <= len; i++)
	{
		while (j && s[i] != s[j + 1])
		{
			j = nxt[j];
		}
		if (s[i] == s[j + 1])
		{
			j++;
		}
		nxt[i] = j;
	}
	int ans = 0;
	for (int i = 1; i <= len; i++)
	{
		dp[i] = dp[nxt[i]] + !(i & 1);
		ans += dp[i];
	}
	printf("%d\n", ans);
	return 0;
}

T3 TRAVEL \text{T3 TRAVEL} T3 TRAVEL

Description \text{Description} Description

CF366D Dima and Trap Graph

在一张无向图上有 N N N 个点和 M M M 条边，每条边连接着点 a a a 和点 b b b，有无数个人编号为 1 , 2 , … , + ∞ 1,2,\dots,+\infty 1,2,…,+∞。通过某条边是要一定的条件的，对于每条边，有两个值 l l l 和 r r r，表示该条边只允许编号在 [ l , r ] [l,r] [l,r] 区间内的人通过，从 1 1 1 号点到达 N N N 号点，请求出最多有多少人可以通过，并求出这些人的编号（若有多组解取字典序最小的一组 )

• 可能有重边和自环。
• 如果没有人能通过只要输出 0 就可以了。
• 对于 30 % 30\% 30% 的数据， 1 ≤ N , M ≤ 10 1\le N,M\le10 1≤N,M≤10；
• 对于 100 % 100\% 100% 的数据， 2 ≤ N ≤ 1000 , 0 ≤ M ≤ 3000 , 1 ≤ a , b ≤ N , 1 ≤ l ≤ r ≤ 1 0 6 2\le N\le1000,0\le M\le3000,1\le a,b\le N,1\le l\le r\le10^6 2≤N≤1000,0≤M≤3000,1≤a,b≤N,1≤l≤r≤106。

Solution \text{Solution} Solution

依然有两种思路（注意字典序最小的判断）：

1. 1. 1. 最长路

遍历每一条边，对于第 i i i 条边，选取边权 ≥ l i \ge l_i ≥li​ 的边，从 1 1 1 到 N N N 跑最长路，让 r r r 最大，在 l l l 固定的情况下，肯定是 r r r 越大越好。

时间复杂度 O ( M ⋅ M log ⁡ N ) = O ( M 2 log ⁡ N ) \mathcal{O}(M\cdot M\log N)=\mathcal{O}(M^2\log N) O(M⋅MlogN)=O(M2logN)。

2. 2. 2. 并查集

同样是遍历每一条边 i i i，将所有满足 l j ≤ l i l_j\le l_i lj​≤li​ 的 j j j，都把 a j a_j aj​ 和 b j b_j bj​ 并入一个集合。

那么最终的 l l l 一定是 l i l_i li​，所以把所有的 r i r_i ri​ 取个 min ⁡ \min min 作为最终的 r r r，当点 1 1 1 和点 N N N 在同一个集合内说明可以尝试去更新答案。

因为是并查集实现，结合路径压缩和按秩合并可以做到 O ( M 2 α ( N ) ) \mathcal{O}(M^2\alpha(N)) O(M2α(N))，不过因为 N ≤ 1000 N\le1000 N≤1000 所以优化不大，主要优化在于常数（

时间复杂度 O ( M 2 α ( N ) ) \mathcal{O}(M^2\alpha(N)) O(M2α(N))。

Code \text{Code} Code

1. 1. 1.

#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;

const int MAXN = 1005;
const int MAXM = 3005;
const int INF = 0x3f3f3f3f;

int cnt;
int head[MAXN];

struct edge
{
	int to, l, r, nxt;
}e[MAXM << 1];

void add(int u, int v, int l, int r)
{
	e[++cnt] = edge{v, l, r, head[u]};
	head[u] = cnt;
}

int dis[MAXN];
bool vis[MAXN];

struct node
{
	int u, r;
	bool operator <(const node &x)const
	{
		if (x.r == r)
		{
			return x.u < u;
		}
		return x.r > r;
	}
};

void init()
{
	memset(dis, -INF, sizeof(dis));
	memset(vis, false, sizeof(vis));
}

void dijkstra(int l)
{
	init();
	dis[1] = INF;
	priority_queue<node> pq;
	pq.push(node{1, dis[1]});
	while (!pq.empty())
	{
		int u = pq.top().u;
		pq.pop();
		if (vis[u])
		{
			continue;
		}
		vis[u] = true;
		for (int i = head[u]; i; i = e[i].nxt)
		{
			if (e[i].l > l) //取在区间内的
			{
				continue;
			}
			int v = e[i].to;
			if (dis[v] < min(dis[u], e[i].r)) //r要取min
			{
				dis[v] = min(dis[u], e[i].r);
				pq.push(node{v, dis[v]});
			}
		}
	}
}

int l[MAXM], r[MAXM];

int main()
{
	int n, m;
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; i++)
	{
		int u, v;
		scanf("%d%d%d%d", &u, &v, l + i, r + i);
		add(u, v, l[i], r[i]);
		add(v, u, l[i], r[i]);
	}
	int ansk = 0, ansl = 0, ansr = 0;
	for (int i = 1; i <= m; i++)
	{
		dijkstra(l[i]);
		int res = dis[n] - l[i] + 1;
		if (ansk < res || (ansk == res && ansl > l[i]))
		{
			ansk = res;
			ansl = l[i];
			ansr = dis[n];
		}
	}
	if (ansk)
	{
		printf("%d\n", ansk);
		for (int i = ansl; i <= ansr; i++)
		{
			printf("%d ", i);
		}
	}
	else
	{
		puts("0");
	}
	return 0;
}

2. 2. 2.

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAXN = 1005;
const int MAXM = 3005;
const int INF = 0x3f3f3f3f;

struct edge
{
	int u, v, l, r;
}e[MAXM];

bool cmp(edge x, edge y)
{
	if (x.r == y.r)
	{
		return x.l < y.l;
	}
	return x.r > y.r;
}

int n, m, r, ansk, ansl, ansr;
int fa[MAXN], siz[MAXN];

void init()
{
	for (int i = 1; i <= n; i++)
	{
		fa[i] = i;
		siz[i] = 1;
	}
}

int find(int x)
{
	if (x == fa[x])
	{
		return x;
	}
	return fa[x] = find(fa[x]); //路径压缩
}

int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; i++)
	{
		scanf("%d%d%d%d", &e[i].u, &e[i].v, &e[i].l, &e[i].r);
	}
	sort(e + 1, e + m + 1, cmp);
	for (int i = 1; i <= m; i++)
	{
		init();
		r = INF;
		for (int j = 1; j <= m; j++)
		{
			if (e[j].l <= e[i].l)
			{
				int x = find(e[j].u), y = find(e[j].v);
				if (x != y)
				{
					if (siz[x] > siz[y]) //按秩合并
					{
						fa[y] = x;
						siz[x] += siz[y];
					}
					else
					{
						fa[x] = y;
						siz[y] += siz[x];
					}
					r = min(r, e[j].r);
					if (find(1) == find(n))
					{
						break;
					}
				}
			}
		}
		if (find(1) == find(n) && (ansk < r - e[i].l + 1 || (ansk == r - e[i].l + 1 && ansl > e[i].l)))
		{
			ansk = r - e[i].l + 1;
			ansl = e[i].l;
			ansr = r;
		}
	}
	if (ansk)
	{
		printf("%d\n", ansk);
		for (int i = ansl; i <= ansr; i++)
		{
			printf("%d ", i);
		}
	}
	else
	{
		puts("0");
	}
	return 0;
}

T4 潜入行动 \text{T4 潜入行动} T4 潜入行动

Description \text{Description} Description

LUOGU4516 [JSOI2018]潜入行动

有一棵 n n n 个节点、 n − 1 n−1 n−1 条边的树，如果在节点 u u u 上安装监听设备，则J能够监听与 u u u 直接相邻所有的节点。特别注意放置在节点 u u u 的监听设备并不监听 u u u 本身。一共有了 k k k 个监听设备，请求出有多少种不同的放置监听设备的方法，能够使得树上所有节点都被监听。

• 每个节点至多只能安装一个监听设备，且监听设备必须被用完。

• 输出答案 m o d    1000000007 \mod1000000007 mod1000000007 的余数。

• 存在 10 % 10\% 10% 的数据， 1 ≤ n ≤ 20 1\le n\le20 1≤n≤20；

• 存在另外 10 % 10\% 10% 的数据， 1 ≤ n ≤ 100 1\le n\le100 1≤n≤100；

• 存在另外 10 % 10\% 10% 的数据， 1 ≤ k ≤ 10 1\le k\le10 1≤k≤10；

• 存在另外 10 % 10\% 10% 的数据，输入的树保证是一条链；

• 对于所有数据， 1 ≤ n ≤ 105 1\le n\le105 1≤n≤105， 1 ≤ k ≤ min ⁡ { n , 100 } 1\le k\le \min\{n,100\} 1≤k≤min{n,100} 。

Solution \text{Solution} Solution

这种题一看就是 D P \rm DP DP。

设 d p u , x , 0 / 1 , 0 / 1 dp_{u,x,0/1,0/1} dpu,x,0/1,0/1​ 表示节点 u u u 的子树内有 x x x 个监听设备，且节点 u u u 是否安了监听设备，节点 u u u 是否被监听。

然后就是推柿子了（以下省略过程）设 v v v 为 u u u 的儿子。

d p u , j + l , 0 , 0 = d p u , j , 0 , 0 × d p v , l , 0 , 1 dp_{u,j+l,0,0}=dp_{u,j,0,0}\times dp_{v,l,0,1} dpu,j+l,0,0​=dpu,j,0,0​×dpv,l,0,1​

d p u , j + l , 0 , 1 = d p u , j , 0 , 1 × ( d p v , l , 0 , 1 + d p v , l , 1 , 1 ) + d p u , j , 0 , 0 × d p v , l , 1 , 1 dp_{u,j+l,0,1}=dp_{u,j,0,1}\times(dp_{v,l,0,1}+dp_{v,l,1,1})+dp_{u,j,0,0}\times dp_{v,l,1,1} dpu,j+l,0,1​=dpu,j,0,1​×(dpv,l,0,1​+dpv,l,1,1​)+dpu,j,0,0​×dpv,l,1,1​

d p u , j + l , 1 , 0 = d p u , j , 1 , 0 × ( d p v , l , 0 , 0 + d p v , l , 0 , 1 ) dp_{u,j+l,1,0}=dp_{u,j,1,0}\times(dp_{v,l,0,0}+dp_{v,l,0,1}) dpu,j+l,1,0​=dpu,j,1,0​×(dpv,l,0,0​+dpv,l,0,1​)

d p u , j + l , 1 , 1 = d p u , j , 1 , 0 × ( d p v , l , 1 , 0 + d p v , l , 1 , 1 ) + d p u , j , 1 , 1 × ( d p v , l , 0 , 0 + d p v , l , 0 , 1 + d p v , l , 1 , 0 + d p v , l , 1 , 1 ) dp_{u,j+l,1,1}=dp_{u,j,1,0}\times(dp_{v,l,1,0}+dp_{v,l,1,1})+dp_{u,j,1,1}\times(dp_{v,l,0,0}+dp_{v,l,0,1}+dp_{v,l,1,0}+dp_{v,l,1,1}) dpu,j+l,1,1​=dpu,j,1,0​×(dpv,l,1,0​+dpv,l,1,1​)+dpu,j,1,1​×(dpv,l,0,0​+dpv,l,0,1​+dpv,l,1,0​+dpv,l,1,1​)

注意事项：

1. d p u , j , 0 / 1 , 0 / 1 dp_{u,j,0/1,0/1} dpu,j,0/1,0/1​ 这个要预先存起来，不然用来更新 d p u , j + l , 0 / 1 , 0 / 1 dp_{u,j+l,0/1,0/1} dpu,j+l,0/1,0/1​ 的不是上一轮的了。；
2. 直接开 long long 会 M L E \rm MLE MLE。需要在计算时乘上 1LL。

Code \text{Code} Code

#include <iostream>
#include <cstdio>
using namespace std;

const int MAXN = 1e5 + 5;
const int MOD = 1e9 + 7;

int n, k, cnt;
int head[MAXN], siz[MAXN], dp[MAXN][105][2][2], tmp[105][2][2];

struct edge
{
	int to, nxt;
}e[MAXN << 1];

void add(int u, int v)
{
	e[++cnt] = edge{v, head[u]};
	head[u] = cnt;
}

void dfs(int u, int fa)
{
	siz[u] = dp[u][0][0][0] = dp[u][1][1][0] = 1; //初始化
	for (int i = head[u]; i; i = e[i].nxt)
	{
		int v = e[i].to;
		if (v == fa)
		{
			continue;
		}
		dfs(v, u);
		for (int j = 0; j <= min(siz[u], k); j++)
		{
			tmp[j][0][0] = dp[u][j][0][0], dp[u][j][0][0] = 0;
			tmp[j][0][1] = dp[u][j][0][1], dp[u][j][0][1] = 0;
			tmp[j][1][0] = dp[u][j][1][0], dp[u][j][1][0] = 0;
			tmp[j][1][1] = dp[u][j][1][1], dp[u][j][1][1] = 0;
		}
		for (int j = 0; j <= min(siz[u], k); j++)
		{
			for (int l = 0; l <= min(siz[v], k - j); l++)
			{
				dp[u][j + l][0][0] = (dp[u][j + l][0][0] + 1LL * tmp[j][0][0] * dp[v][l][0][1] % MOD) % MOD;
				dp[u][j + l][0][1] = (dp[u][j + l][0][1] + 1LL * tmp[j][0][1] * (1LL * dp[v][l][0][1] + 1LL * dp[v][l][1][1]) % MOD + 1LL * tmp[j][0][0] * dp[v][l][1][1] % MOD) % MOD;
				dp[u][j + l][1][0] = (dp[u][j + l][1][0] + 1LL * tmp[j][1][0] * (1LL * dp[v][l][0][0] + 1LL * dp[v][l][0][1]) % MOD) % MOD;
				dp[u][j + l][1][1] = (dp[u][j + l][1][1] + 1LL * tmp[j][1][0] * (1LL * dp[v][l][1][0] + 1LL * dp[v][l][1][1]) % MOD + 1LL * tmp[j][1][1] * (1LL * dp[v][l][0][0] + 1LL * dp[v][l][0][1] + 1LL * dp[v][l][1][0] + 1LL * dp[v][l][1][1]) % MOD) % MOD;
			}
		}
		siz[u] += siz[v];
	}
}

int main()
{
	scanf("%d%d", &n, &k);
	for (int i = 1; i < n; i++)
	{
		int u, v;
		scanf("%d%d", &u, &v);
		add(u, v);
		add(v, u);
	}
	dfs(1, 0);
	printf("%d\n", (dp[1][k][0][1] + dp[1][k][1][1]) % MOD); //最终1号点必须被监视
	return 0;
}