随机生成树 tree
题目描述
- 随机生成一棵树，一个节点的父亲为他的真因数之一；
- 请求出树上节点两两之间的距离和的期望。
题解
Subtask1（$n\leq 15$）
暴力搜索每个节点的父亲编号，然后通过换根 dp 求得距离和，与情况总数做比即为答案。
时间复杂度为 $\Theta\left(n\prod\limits_{i=1}^n\left(\sigma_0(i)-1\right)\right)$。
Subtask6（$n\leq 3\times 10^5$）
展开答案式。
$$
\begin{aligned}
&\sum_{i}\sum_{j}\texttt{dis}_T(i,j)\\
=&\sum_{i}\sum_{j}\texttt{dep}(i)+\texttt{dep}(j)-\texttt{dep}(\texttt{lca}(i,j))\\
=&\sum_{i}\left(n\times \texttt{dep}(i)+\sum_{j}\texttt{dep}(j)-\texttt{dep}(\texttt{lca}(i,j))\right)\\
=&2n\sum_i\texttt{dep}(i)-\sum_{i}\sum_{j}\texttt{dep}(\texttt{lca}(i,j))
\end{aligned}
$$
我们发现式子分成了两部分，根据期望的线性性，我们可以拆分答案，即
$$\mathbb{E}(\omega(T))=\mathbb{E}\left(2n\sum_i\texttt{dep}(i)\right)-\mathbb{E}\left(\sum_{i}\sum_{j}\texttt{dep}\left(\texttt{lca}(i,j)\right)\right)$$
前面的问题很好处理，不难看出
$$
\begin{aligned}
&\mathbb{E}(2n\sum_i\texttt{dep}(i))\\
=&2n\times\mathbb{E}(\sum_i\texttt{dep}(i))\\
=&2n\sum_i\mathbb{E}(\texttt{dep}(i))
\end{aligned}
$$
然而 $i\neq 1$ 时，有
$$
\mathbb{E}(\texttt{dep}(i))=\frac{\sum_{\texttt{fa}\mid i,\texttt{fa}\neq i}(\texttt{dep}_d)}{\sigma_0(i)-1}
$$
式子的第一部分被轻松解决，下面解决第二部分。
设 $f(\texttt{lca})$ 表示 $\texttt{lca}$ 被作为有序点对 $(i,j)$ 的 $\texttt{lca}$ 的次数。
$$
\begin{aligned}
&\sum_{i}\sum_{j}\texttt{dep}\left(\texttt{lca}(i,j)\right)\\
=&\sum_\texttt{u}\texttt{dep}(\texttt{u})\times\sum_i\sum_j\left[\texttt{lca}(i,j)=\texttt{u}\right]\\
=&\sum_\texttt{u}\texttt{dep}(\texttt{u})\times f_u
\end{aligned}
$$
如果求出了 $f_u$，由于它是与 $\texttt{dep}_u$ 无关的变量，所以我们可以直接乘起来得到答案。
我们可以用容斥原理来解决问题，具体地，对于两个节点 $i,j$ 的 $\texttt{lca}$ 必然有且仅有三种情况：
- $\texttt{lca}$ 是 $u$ 的祖先；
- $\texttt{lca}$ 是 $u$；
- $\texttt{lca}$ 是 $u$ 子树内的点；
不难发现，$\texttt{siz}_u^2$ 恰好包含了下面两种情况，也就是说，我们要求的 $f_u$ 为 $\texttt{siz}_u^2$ 减去第三种情况数，不难发现，它实际上就是
$$\sum_{v\in\texttt{son}_u}f_v$$
也就是说
$$f_u=\texttt{siz}_u^2-\sum_{v\in\texttt{son}_u}f_v$$
到这里，我们处理完了整个式子的展开，最后套上期望的格式，得到
$$
\texttt{siz}_i=1+\frac{\sum_{i\mid u,i\neq u}\texttt{siz}_u}{\sum_{i\mid u,i\neq u}1}
$$
然后枚举 $\texttt{lca}$ 处理即可。
std
#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
const int MAXN=3e5+5;
int n,p;
struct modInt{
int x;
inline modInt(reg int x=0):x(x){
//assert(0<=x&&x<p);
return;
}
inline modInt operator+(const modInt& a)const{
reg int sum=x+a.x;
return sum>=p?sum-p:sum;
}
inline modInt operator-(const modInt& a)const{
reg int sum=x-a.x;
return sum<0?sum+p:sum;
}
inline modInt operator-(void)const{
return modInt(0)-*this;
}
inline modInt operator*(const modInt& a)const{
return 1ll*x*a.x%p;
}
};
inline modInt fpow(modInt x,reg int exp){
modInt res=1;
while(exp){
if(exp&1)
res=res*x;
x=x*x;
exp>>=1;
}
return res;
}
vector<int> V[MAXN];
modInt fac[MAXN],invfac[MAXN],inv[MAXN];
modInt dep[MAXN],f[MAXN],g[MAXN];
int main(void){
scanf("%d%d",&n,&p);
for(int i=1;i<=n;++i)
for(reg int j=i+i;j<=n;j+=i)
V[j].push_back(i);
fac[0]=1;
for(reg int i=1;i<=n;++i)
fac[i]=fac[i-1]*i;
invfac[n]=fpow(fac[n],p-2);
for(reg int i=n-1;i>=0;--i)
invfac[i]=invfac[i+1]*(i+1);
inv[0]=1;
for(reg int i=1;i<=n;++i)
inv[i]=invfac[i]*fac[i-1];
for(reg int u=2;u<=n;++u){
for(int v:V[u])
dep[u]=dep[u]+dep[v];
dep[u]=dep[u]*inv[V[u].size()]+1;
}
modInt ans=0;
for(reg int u=n;u>=2;--u){
static modInt siz[MAXN];
modInt sum=1;
siz[u]=1;
for(reg int v=u+u;v<=n;v+=u){
siz[v]=0;
for(int x:V[v/u])
siz[v]=siz[v]+siz[x*u];
siz[v]=siz[v]*inv[V[v].size()];
sum=sum+siz[v];
}
f[u]=sum*sum;
for(reg int v=u+u;v<=n;v+=u)
f[u]=f[u]-siz[v]*siz[v]*f[v];
ans=ans+dep[u]*(-f[u]*2+(n<<1)%p);
}
printf("%d\n",ans.x);
return 0;
}矩形覆盖 cover
题目描述
- $n$ 块木板拼成的物体，求出把它切割成多个矩形的最小操作次数。
题解
Subtask1（$n\leq 5$）
考虑枚举每一条木板之间要不要竖着切割，相邻两木板 $u,d$ 不同时要不要横着切割，求最小值即可。
时间复杂度为 $\Theta(2^{3n})$。
Subtask4（$n\leq 500$）
发现题目存在限制，即横着切割的轨迹不能跨越竖着切割的痕迹。
也就是说，竖着切割把整个木板变成了多块子木板，这与动态规划的思想类似，考虑设计 $f_{l,r}$ 为解决 $[l,r]$ 区间木板的最小代价，不难得出
$$
f_{l,r}=\begin{cases}
0&,l=r\\
\min\{\texttt{cut}(l,r),\min_{i=l}^{r-1}\{f_{l,i}+f_{i+1,r}+1\}\}&,l\neq r
\end{cases}
$$
其中 $\texttt{cut}(l,r)$ 表示只用横向切割达成目的，不难用单调栈在 $\Theta(r-l)$ 的时间复杂度内求得。
不难用时间复杂度为 $\Theta(n^3)$ 的区间 dp 解决问题。
Subtask6（$n\leq 2\times 10^3$）
不难发现我们可以优化求解 $\texttt{cut}(l,r)$ 的时间复杂度，左端点固定，右端点平移，即可在 $\Theta(n^2)$ 的复杂度内预处理完。
重新设计 dp 状态，设 $f_{i}$ 表示切割 $1\sim i$ 块木板的最小操作次数，那么
$$
f_i=\min\{\texttt{cut}(1,i),\min_{1\leq j < i}\{f_{j}+\texttt{cut}(j+1,i)\}\}
$$
时间复杂度为 $\Theta(n^2)$。
Subtask8（$n\leq 5\times 10^5$）
不难发现，一个多边形如果它满足以下两个条件：
- 所有的边都与坐标轴平行或垂直；
- 凸，不存在一个内角大于 $\pi$；
它必定是一个矩形。
定义凸出来的角的顶点为凸点，凹进去的角的顶点为凹点。换句话说，我们要通过最小的次数消灭所有的凹点。
一次切割具有性质：切割不可能产生新的凹点，对凹点进行切割要么得到凸点，要么得到直线；
因为我们要消灭所有凹点，所以所有的凹点都要被我们切割一次，为了最优化答案，我们需要用最少的次数连接所有连线与坐标轴平行的凹点对。
因为题目限制中竖着切割会破坏横向切割的路径，也就是说，由于一开始这些操作都是合法的，而它们可能会变得不合法（两个端点变得分属两个多边形），所以在最优方案中，可以先进行这样的操作，只需要保证它们都还是合法的即可。而这等价于每个操作的端点都没有被切开，也就是任意两次操作都不相交。于是，我们的问题变成了求这些操作的最大独立集：两个操作之间有边，当且仅当它们相交。
这种点覆盖区间的最大匹配，我们用贪心法即可解决，用堆和单指针维护即可，时间复杂度 $\Theta(n\log_2n)$。
std
#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
reg char ch=getchar();
reg int res=0;
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))res=10*res+(ch^'0'),ch=getchar();
return res;
}
const int MAXN=5e5+5;
struct Interval{
int l,r;
inline Interval(reg int l=0,reg int r=0):l(l),r(r){
return;
}
inline bool in(reg int x){
return l<=x&&x<=r;
}
inline bool operator<(const Interval& a)const{
return r<a.r;
}
inline bool operator>(const Interval& a)const{
return r>a.r;
}
};
inline bool cmp(const Interval& a,const Interval& b){
return a.l<b.l;
}
int n;
int u[MAXN],d[MAXN];
int cnt,p[MAXN];
int tot;
Interval inv[MAXN<<1];
inline void calc(reg int a[],reg int n){
reg int top=0;
static int S[MAXN];
for(reg int i=1;i<=n;++i){
if(a[i]==a[i-1])
continue;
if(a[i]>a[i-1])
S[++top]=i-1;
else{
while(top&&a[S[top]]>a[i])
--top;
if(top&&a[S[top]]==a[i])
inv[++tot]=Interval(S[top--]+1,i);
}
}
return;
}
int main(void){
n=read();
for(reg int i=1;i<=n;++i)
u[i]=read(),d[i]=read();
calc(u,n),calc(d,n);
reg int ans=0;
for(reg int i=2;i<=n;++i){
if(u[i]!=u[i-1]&&d[i]!=d[i-1])
p[++cnt]=i;
ans+=(u[i]!=u[i-1])+(d[i]!=d[i-1]);
}
sort(inv+1,inv+tot+1,cmp);
priority_queue<Interval,vector<Interval>,greater<Interval>/**/> Q;
ans-=cnt+tot;
for(reg int i=1,j=1;i<=cnt;++i){
while(j<=tot&&inv[j].l<=p[i])
Q.push(inv[j++]);
while(!Q.empty()&&Q.top().r<p[i])
Q.pop();
if(!Q.empty())
++ans,Q.pop();
}
printf("%d\n",ans);
return 0;
}字串变换 strinq
题目描述
- 给你一个斐波那契串，查询多点的后缀排名。
题解
Subtask2（$n\leq 30$）
考虑直接求出字符串，然后用倍增法求解后缀排名。
时间复杂度 $\Theta(n\texttt{fib}_n)$。
Subtask5（$n\leq 10^{18}$）
作为后缀排名问题，显然建后缀数组不现实，自然的想法就是建出 SAM 然后遍历。
考虑这个特殊字符串的 SAM 有没有啥特殊结构。
注意到 $S_n=S_{n−1}S_{n−2}=S_{n−2}S_{n−3}S_{n−2}$。如果 $k=n-3$ 是奇数，那么注意到 $S_{k+1}S_k=S_{k+1}S_{k−1}S_{k−2}=\cdots=S_{k+1}S_{k−1}S_{k−3}\cdots S_4S_2S_1$ 而我们断言，$S_kS_{k+1}=S_{k+1}S_{k−1}S_{k−3}\cdots S_4S_1S_1S_0$。考虑归纳证明，基础情况是显然的。
而若这对于 $k−2$ 成立，则 $S_kS_{k+1}=S_kS_kS_{k−1}=S_kS_{k−1}S_{k−2}S_{k−1}=S_{k+1}S_{k−1}S_{k−3}S_{k−5}\cdots S_4S_1S_1S_0$ 因此，前后这两个部分实际上长得很像，除了最后两位一个是 $S_0S_1$ 一个是 $S_1S_0$ 以外（对于 $k$ 是偶数的情况也是一样的，只不过这两位反过来了而已）。
所以说，如果我们有了 $S_n−1$ 的 SAM，那么要得到 $S_n=S_{n−1}S_{n−2}$ 的 SAM，我们只要在后面拼上 $S_{n−2}$，然后将 $S_{n−1}$ 的倒数第二位与 $S_n$ 的最后一位连边即可。
所以说这个 SAM 的长相非常简单，就是一条主链再加上 $n-2$ 条额外的边。同时，其终态就是所有的 $S_n,S_{n−2},S_{n−4},\cdots,S_{n\bmod{2}}$ 对应的点。所以说，我们只要 $3n$ 个状态即可。
这样我们就得到了一个 $\Theta(n)$ 的做法。为了优化，注意到我们的询问 $i_j\leq 10^{18}$， 所以只要保留最后 $\Theta(\log i_j)$ 个状态即可。具体保留多少个可以简单的确定：把输入离 线，然后一边建 SAM 一边算从每个状态开始，可以得到多少个不同的后缀。如果这个值超过了所有输入的 $i_j$ 的最大值，那么就不建了即可。时间复杂度为 $\Theta(q\log i_j)$。不过当 $n$ 很小的情况需要暴力构造，但当 $n$ 这么小的时候直接求出所有后缀排序即可，没必要对每个 $n$ 都手动构造一遍 SAM。
std
#include <algorithm>
#include <cstdio>
#include <vector>
#include <string>
#include <tuple>
using ll = long long;
std::pair<ll, ll> get_fib(ll n, ll MOD)
{
if (!n)
return std::make_pair(0, 1);
ll x, y;
if (n & 1)
{
std::tie(x, y) = get_fib(n - 1, MOD);
return std::make_pair(y, (x + y) % MOD);
}
else
{
std::tie(x, y) = get_fib(n >> 1, MOD);
return std::make_pair((y * 2 - x + MOD) * x % MOD,
(x * x + y * y) % MOD);
}
}
ll qry[500005];
void solve_small(int n, int q, int MOD)
{
static std::string fib[] = {"b", "a", "ab", "aba", "abaab"};
std::string str = fib[n];
std::vector<std::string> suf;
for (int i = 0; i < str.size(); i++)
suf.push_back(str.substr(i));
std::sort(suf.begin(), suf.end());
for (int i = 0; i < q; i++)
printf("%d%c", (str.size() - suf[qry[i] - 1].size() + 1) % MOD, " \n"[i + 1 == q]);
}
struct Node
{
int trans[2];
ll len[2], ways;
bool is_end;
} node[305];
int main()
{
ll n, MOD;
int q;
scanf("%lld%d", &n, &q);
for (int i = 0; i < q; i++)
scanf("%lld", qry + i);
scanf("%lld", &MOD);
if (n <= 4)
{
solve_small(n, q, MOD);
return 0;
}
for (int i = 0; i < 300; i++)
{
node[i].trans[0] = node[i].trans[1] = -1;
node[i].len[0] = node[i].len[1] = 0;
node[i].ways = 0;
node[i].is_end = false;
}
ll bound = *std::max_element(qry, qry + q), m = n;
int tot = 0;
while (m >= 5)
{
node[tot].is_end = (m & 1) == (n & 1);
if (tot)
{
node[tot].trans[0] = tot - 1;
node[tot].len[0] = get_fib(m - 1, MOD).second - 2;
}
if (m & 1) // ba
{
if (tot)
{
node[tot + 2].trans[0] = tot - 2;
node[tot + 2].len[0] = 1;
}
node[tot + 2].trans[1] = tot + 1;
node[tot + 2].len[1] = 1;
node[tot + 1].trans[0] = tot;
node[tot + 1].len[0] = 1;
}
else // ab
{
if (tot)
{
node[tot + 2].trans[1] = tot - 2;
node[tot + 2].len[1] = 1;
}
node[tot + 2].trans[0] = tot + 1;
node[tot + 2].len[0] = 1;
node[tot + 1].trans[1] = tot;
node[tot + 1].len[1] = 1;
}
for (int i = 0; i < 3; i++)
{
node[tot + i].ways = node[tot + i].is_end;
for (int c = 0; c < 2; c++)
{
if (~node[tot + i].trans[c])
node[tot + i].ways += node[node[tot + i].trans[c]].ways;
}
}
if (node[tot].ways >= bound && (m & 1 ^ 1))
break;
tot += 3;
m--;
}
if (node[tot].ways < bound || (m & 1))
{
// Small ones
if (n & 1 ^ 1)
node[tot].is_end = node[tot + 3].is_end = true;
else
node[tot + 2].is_end = node[tot + 4].is_end = true;
node[tot + 5].trans[1] = tot + 3;
node[tot + 5].len[1] = 1;
node[tot + 2].trans[1] = tot - 2;
node[tot + 2].len[1] = 1;
node[tot + 4].trans[0] = tot + 1;
node[tot + 4].len[0] = 1;
const std::string str = "abaaba";
for (int i = 0; i <= 5; i++)
{
int c = str[5 - i] - 'a';
node[tot + i].trans[c] = tot + i - 1;
node[tot + i].len[c] = 1;
}
for (int i = 0; i < 5; i++)
{
node[tot + i].ways = node[tot + i].is_end;
for (int c = 0; c < 2; c++)
{
if (~node[tot + i].trans[c])
node[tot + i].ways += node[node[tot + i].trans[c]].ways;
}
}
tot += 5;
m = 0;
}
ll fib = get_fib(n, MOD).second, pre = 0;
if (m)
{
pre = get_fib(m, MOD).second;
ll x = m / 2 - 1;
pre = (pre - get_fib(x * 2 + 1, MOD).second + 1 + MOD) % MOD;
}
for (int i = 0; i < q; i++)
{
ll ans = fib, rk = qry[i];
if (n & 1)
{
if (m && rk == 1)
ans--;
else
ans -= pre;
if (m)
rk--;
}
else
{
if (rk <= m / 2 - 2)
{
ans -= get_fib(rk * 2 + 2, MOD).second;
ans += get_fib(rk * 2 + 1, MOD).second - 1;
rk = 0;
}
else
{
rk -= std::max(0ll, m / 2 - 2);
ans -= pre;
}
}
for (int u = tot; rk; )
{
rk -= node[u].is_end;
if (!rk)
break;
int x = node[u].trans[0], y = node[u].trans[1];
if (~x && node[x].ways >= rk)
{
ans -= node[u].len[0];
u = x;
}
else
{
if (~x)
rk -= node[x].ways;
ans -= node[u].len[1];
u = y;
}
}
printf("%lld%c", (ans % MOD + MOD + 1) % MOD, " \n"[i + 1 == q]);
}
return 0;
}