QuestOJ's Blog

随机生成树 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;
}