Posted in: 未分类

带参数的矩阵乘法

#include<bits/stdc++.h>
using namespace std;

const int N=3;  //矩阵维数
typedef vector<pair<string,int> > VSI;
typedef pair<string,int> SI;

//带参数的矩阵乘法
void mul(VSI ans[N][N],SI a[N][N])
{
    VSI res[N][N];  //临时矩阵

    //模拟
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            for(int k=0;k<N;k++)
            {
                string s2=a[k][j].first;    //参数
                int i2=a[k][j].second;  //系数
                if(i2==0) continue;   //优化,f(x)*0=0,不必继续往下计算
                for(int l=0;l<ans[i][k].size();l++)
                {
                    string s1=ans[i][k][l].first;
                    int i1=ans[i][k][l].second;
                    if(s2!="1"/*省略1*/) s1+=s2;
                    res[i][j].push_back({s1,i1*i2});    //参数:字符串直接加在后面;系数:直接相乘
                }
            }

    //将临时矩阵复制到答案矩阵        
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
        {
            ans[i][j].clear();
            for(int k=0;k<res[i][j].size();k++) ans[i][j].push_back(res[i][j][k]);
        }

    return ;
}

//计数排序
unordered_map<char,int> h;
void Hash(char a)
{
    if(!h.count(a)) h[a]=1;
    else h[a]++;
    return ;
}

//计数排序求最简单项式
string get_min(string a)
{
    string res;
    h.clear();
    for(int i=0;i<a.length();i++) Hash(a[i]);
    for(char x='a';x<='z';x++)
        for(int i=1;i<=h[x];i++)
            if(x!='h') res.push_back(x);
    return res;
}

//化简
void simplify(VSI ans[N][N])
{
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
        {
            //对组成多项式的单项式求最简式
            for(int k=0;k<ans[i][j].size();k++) ans[i][j][k].first=get_min(ans[i][j][k].first);

            //排列项
            sort(ans[i][j].begin(),ans[i][j].end());

            //合并同类项
            VSI res;    //临时矩阵
            int ne=0,num=0;
            for(int k=0;k<ans[i][j].size();k=ne)
            {
                num=ans[i][j][k].second;
                ne=k+1;
                while(ne<ans[i][j].size() && ans[i][j][k].first==ans[i][j][ne].first)
                {
                    num+=ans[i][j][ne].second;
                    ne++;
                }
                res.push_back({ans[i][j][k].first,num});
            }

            //将临时矩阵复制到答案矩阵
            ans[i][j].clear();
            for(int k=0;k<res.size();k++) if(res[k].second!=0) ans[i][j].push_back(res[k]);
        }
    return ;
}

//输出
void print(VSI ans[N][N])
{
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
        {
            for(int k=0;k<ans[i][j].size();k++) cout<<ans[i][j][k].second<<ans[i][j][k].first<<' ';
            puts("");
        }
    puts("");
    return ;
}

int main()
{
    //填入第一个矩阵
    VSI ans[N][N];
    ans[0][0].push_back({"b",1});
    ans[0][1].push_back({"a",1});
    ans[0][2].push_back({"0",0});
    ans[1][0].push_back({"a",-1});
    ans[1][1].push_back({"b",1});
    ans[1][2].push_back({"0",0});
    ans[2][0].push_back({"0",0});
    ans[2][1].push_back({"0",0});
    ans[2][2].push_back({"1",1});

    //填入后面相乘的矩阵
    SI op1[N][N]=
    {
        {{"d",1},{"0",0},{"c",1}},
        {{"0",0},{"1",1},{"0",0}},
        {{"c",-1},{"0",0},{"d",1}}
    };
    SI op2[N][N]=
    {
        {{"1",1},{"0",0},{"0",0}},
        {{"0",0},{"f",1},{"e",-1}},
        {{"0",0},{"e",1},{"f",1}}
    };
    SI op3[N][N]=
    {
        {{"d",1},{"0",0},{"c",-1}},
        {{"0",0},{"1",1},{"0",0}},
        {{"c",1},{"0",0},{"d",1}}
    };
    SI op4[N][N]=
    {
        {{"b",1},{"a",-1},{"0",0}},
        {{"a",1},{"b",1},{"0",0}},
        {{"0",0},{"0",0},{"1",1}}
    };

    //带参数的矩阵乘法
    mul(ans,op1);
    mul(ans,op2);
    mul(ans,op3);
    mul(ans,op4);

    //化简
    simplify(ans);

    //输出
    print(ans);

    return 0;
}
Posted in: QuestOJ 比赛题解

五一“欢乐”赛 题解

随机生成树 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;
}
Posted in: QuestOJ 题解

「QOJ2349」鸿鹄之志 bird

题目

题目链接:QOJ2349

题目限制

  • 时间限制:$1\texttt{s}$;
  • 空间限制:$512\texttt{MiB}$;
  • 输入文件:bird.in
  • 输出文件:bird.out

题目背景

你从小就励志,要当世界第一的猛汉王

题目描述

展现自我的时刻到了,现在你面前有 $n$ 位考官,每位考官都是多面手,具体地,每一位考官都有 $k$ 个属性值,其中第 $i$ 位考官的属性值分别为 $a_{i,0},a_{i,1},a_{i,2},\cdots,a_{i,k-1}$。

考官喜欢合伙刁难你,具体地,他们会对自己的各项属性进行线性组合,线性组合可以看做一个长度为 $k$ 的 $01$ 串,例如 $01000$。一个合法的线性组合集合 $\mathbb{S}$ 应该满足如下需求:

  1. 如果一个串 $a\in\mathbb{S}$ ,那么它的取反串 $a'\not\in\mathbb{S}$ ;
  2. 如果一个串 $a\in\mathbb{S}$,那么它应当满足 $\operatorname{cnt}(a)<\operatorname{cnt}(a')$ 或者 $\operatorname{cnt}(a)=\operatorname{cnt}(a')$ 的同时 $\operatorname{val}(a)< \operatorname{val}(a')$,其中 $\operatorname{cnt}(x)$ 表示 $x$ 中 $1$ 的个数,$\operatorname{val}(x)$ 表示 $x$ 的大小。

如果看不懂,你可以使用如下代码生成长度为 $n$ 的合法线性组合集合。

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;

const int n=4; //改变这里的值,即可得出不同长度的线性组合集合

int main(void){
    bitset<n> B;
    for(reg int i=0;i<(1<<n);++i){
        B=i;
        if(n&1){
            if(B.count()<=n/2)
                cout<<B<<endl;
        }
        else{
            if(B.count()<n/2)
                cout<<B<<endl;
            else if(B.count()==n/2&&i<(1<<(n-1)))
                cout<<B<<endl;
        }
    }
    return 0;
}

不难发现,长度为 $n$ 的线性组合集合 $\mathbb{S}$ 满足 $|\mathbb{S}|=2^{n-1}$。

定义一个考官的武德为一个 $2^{n-1}$ 元组,即上述线性组合集合中的每一个线性组合都对应一个武德值。具体地,对于一个线性组合 $s$,考官 $i$ 对应的武德值为 $\left(\sum\limits_{w=0}^{k-1}(-1)^{s_w}a_{i,w}\right)$。

与考官的武德相比,你总是有所不如,对于一个考官,你面对他的审查产生的尴尬值为两人武德差值绝对值的最大值,即 $\max\limits_{s_{j}\in\mathbb{S}}\left|A_j-\left(\sum\limits_{w=0}^{k-1} (-1)^{s_{j,w}}a_{i,w}\right)\right|$。

考官也喜欢不讲武德,总喜欢让你尴尬,他们会组织起来,对你进行多次审查,定义一次区间 $[l,r]$ 内考官审查你的尴尬值为 $\sum\limits_{i=l}^{r}\left(\max\limits_{s_{j}\in\mathbb{S}}\left|A_j-\left(\sum\limits_{w=0}^{k-1} (-1)^{s_{j,w}}a_{i,w}\right)\right|\right)$。

你可以在审查开始之前修炼自己的武德,即自由改变 $A_j$。请求出尴尬值的最小值。

输入格式

第一行,三个整数 $n,q,k$。

后 $n$ 行,每行 $k$ 个整数 $a_{i,0},a_{i,1},\cdots,a_{i,k-1}$。

后 $q$ 行,每行两个正整数 $l,r$ 表示询问区间。

输出格式

共 $q$ 行,表示每次询问尴尬值的最小值。

样例

样例输入

4 3 2
1 2
3 4
5 6
7 8
1 1
1 2
2 4

样例输出

0.000000
4.000000
8.000000

样例解释

$k=2$ 时,线性组合集合 $\mathbb{S}={[00],[01]}$。

第一次询问,考官属性为 ${[1,2]}$,对应的武德值为 ${(3,-1)}$,应选择 $A_0=3,A_1=-1$,尴尬值取最小为 $0$;

第二次询问,考官属性为 ${[1,2],[3,4]}$,对应武德值为 ${(3,-1),(7,-1)}$,应选择 $A_0\in[3,7]$,$A_1=-1$,尴尬值取最小为 $4$;

第三次询问,考官属性为 ${[3,4],[5,6],[7,8]}$,对应武德值为 ${(7,-1),(11,-1),(15,-1)}$,应选择 $A_0=11,A_1=-1$,尴尬值取最小为 $8$。

数据范围与提示

子任务编号 $n$ $q$ $k$ $a$ 分数
$1$ $\leq 10$ $0$ $=1$ $\lvert a\rvert\leq 10^9$ $5$
$2$ $\leq 100$ $\leq 100$ $=1$ $\lvert a\rvert\leq 10^3$ $10$
$3$ $\leq 100$ $\leq 100$ $=1$ $\lvert a\rvert\leq 10^5$ $5$
$4$ $\leq 100$ $\leq 100$ $=2$ $\lvert a\rvert\leq 10^3$ $5$
$5$ $\leq 10^5$ $\leq 10^5$ $=2$ $\lvert a\rvert\leq 10^9$ $20$
$6$ $\leq 100$ $\leq 100$ $\leq 10$ $\lvert a\rvert\leq 10^5$ $10$
$7$ $\leq 10^4$ $\leq 10^4$ $\leq 10$ $\lvert a\rvert\leq 10^5$ $45$

对于 $100\%$ 的数据,保证 $1\leq l\leq r\leq n$。

题解

下面我们直接说正解。

不难发现下面的规律,它表明各个属性之间对答案的影响无关。

如果我们设 $A_j=\left(\sum\limits_{w=0}^{k-1} (-1)^{s_{j,w}}x_{i,w}\right)$ 其中 $x$ 是我们任意选择,那么我们就对题目进行了恒等变换,不影响答案。

$$
\begin{aligned}
&\max\limits_{s_{j}\in\mathbb{S}}\left|A_j-\left(\sum\limits_{w=0}^{k-1} (-1)^{s_{j,w}}a_{i,w}\right)\right|\\\
=&\max\limits_{s_{j}\in\mathbb{S}}\left|\left(\sum\limits_{w=0}^{k-1} (-1)^{s_{j,w}}x_{i,w}\right)-\left(\sum\limits_{w=0}^{k-1} (-1)^{s_{j,w}}a_{i,w}\right)\right|\\
=&\max\limits_{s_{j}\in\mathbb{S}}\left|\left(\sum\limits_{w=0}^{k-1} (-1)^{s_{j,w}}\left(x_{i,w}-a_{i,w}\right)\right)\right|
\end{aligned}
$$

我们发现事实上线性组合就是一个幌子,如果我们将线性组合取反,由于上面式子绝对值的作用,我们得到的结果相同。也就是说如果我们把线性组合扩充到包含它与它的取反,结果不变。

这样的话,新的线性组合集合就包含了 $2^k$ 个元素,对应所有属性值之差乘上 $+1$ 或者 $-1$ 的自由组合,所以我们进一步转化,得到

$$
\begin{aligned}
&\max\limits_{s_{j}}\left|\left(\sum\limits_{w=0}^{k-1} (-1)^{s_{j,w}}\left(x_{i,w}-a_{i,w}\right)\right)\right|\\
=&\sum\limits_{w=0}^{k-1} \max\limits_{s_{j}}\left|(-1)^{s_{j,w}}\left(x_{i,w}-a_{i,w}\right)\right|\\
=&\sum\limits_{w=0}^{k-1} \max\limits_{s_{j}}\left|\left(x_{i,w}-a_{i,w}\right)\right|\\
=&\sum\limits_{w=0}^{k-1} \left|x_{i,w}-a_{i,w}\right|\\
\end{aligned}
$$

进一步地,我们得出答案其实就是 $k$ 维货仓选址。

我们选择运用主席树来解决区间中位数问题,时间复杂度为 $\Theta\left((k(n+q)\log_2n)\right)$。

代码以后再放。

Posted in: 未分类

「QOJ2342」鸭性统计 duck

首先,聪明的你应该把$duck$反过来读:就是“可达”。

所以这道题就是“可达性统计”的模板题。

只不过,这道题把数据加强到了 $10^5$,并且本题中的图可能存在环。

就是这两个问题,我们一个一个来处理。

对于图中存在环的问题,我们只需要 $\texttt{tarjan}$一下,缩点染色一下就行了,因为在一个环内的两个点肯定两两互相可达,我们把他染成一个颜色并没有问题,其他的操作正常进行,$\texttt{tarjan}$ 缩点肯定大家都会。

接着,我们要对付 $10^5$ 的数据。

对于简单版的可达性统计,我们是建了 bitset<1005> b[1005]b[x][y] 代表的是否能从 $x$ 点到达 $y$ 点,我们用 $\texttt{bitset}$,是为了把第二维压成一个 01 串,从而降低空间。但是对于 $10^5$ 的数据我们把 $\texttt{bitset}$ 建出来:bitset<100005> b[100005]。算一下,上了 $1000\texttt{MiB}$,肯定不可取。

那怎么办呢?

这里就要用到一个很常用的,很重要的技巧:牺牲时间复杂度来补救空间复杂度!
因为我们发现,时间复杂度太优秀了,空间复杂度太菜了。于是我们想到一个类似分块的思想来解决这个问题。
我们可以把 $Q$ 次询问分成 $k$ 段,每一段长为 $len$,然后一段一段地解决,一段一段地处理,我们将每一段询问中 $(u,v)$ 的 $v$ 做一个离散化操作,使得 $\texttt{bitset}$ 的第二维空间降下来,因为这一段最后真正有用的就这 $len$ 个点能否到达,至于其他点能否到达我们不在乎,将它们都看作编号为 0 即可。每一段询问都进行同样的操作,就可以通过本题。其实这样的方法也不叫分块,它就是把一个问题分成了几段,依次处理。

当然,在保证空间复杂度的前提下,$k$ 越小越好。

$code:$

#include<cmath>
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
#include<bitset>
#define reg register
using namespace std;
const int maxn=2e5+5;
const int mod=1e9+7;
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0' || ch>'9')
    {
        if(ch=='-')
        f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}
int n,m,Q;
int wugui=0;
int head1[maxn];
struct node
{
    int to;
    int nxt;
}edge[maxn];
void add(int x,int y)
{
    wugui++;
    edge[wugui].to=y;
    edge[wugui].nxt=head1[x];
    head1[x]=wugui;
}
int in[maxn];
queue<int> q;
vector<int> v[maxn];
int low[maxn];
int dfn[maxn];
int cnt=0;
int s[maxn];
int col[maxn];
int color=0;
int vis[maxn];
int index1=0;
struct Query
{
    int x,y;
}ask[maxn];

//tarjan

void tarjan(int x)
{
    low[x]=dfn[x]=++index1;
    vis[x]=1;   
    s[++cnt]=x;
    for(reg int i=0;i<(int)v[x].size();i++)
    {
        int t=v[x][i];
        if(dfn[t]==0)
        {
            tarjan(t);
            low[x]=min(low[x],low[t]);
        }
        else
        {
            if(vis[t]==1)
            low[x]=min(low[x],dfn[t]);
        }
    }
    if(dfn[x]==low[x])
    {
        int v;
        color++;
        do
        {
            v=s[cnt];
            cnt--;
            col[v]=color;
            vis[v]=0;
        }
        while(v!=x);
    }
}

bitset<20005> a[maxn];
int re_in[maxn];
int tot=0;
int b[maxn];
int id[maxn];
int Get(int x)
{
    return lower_bound(s+1,s+1+tot,x)-s;
}
int order[maxn];
int ORDER=0;
void Work(int l,int r)
{

    // re_sort  & Get_id

    tot=0;
    int fuck=0;
    for(reg int i=l;i<=r;i++)
        b[++fuck]=col[ask[i].y];
    sort(b+1,b+1+fuck);
    b[0]=-1e9;
    for(reg int i=1;i<=fuck;i++)
    {
        if(b[i]!=b[i-1])
        s[++tot]=b[i];
    }

    // bitset_dp & topo

    for(reg int i=1;i<=color;i++)
    {
        id[i]=Get(i);
        if(s[id[i]]!=i)
        id[i]=0;
        a[i].reset();
        if(re_in[i]==0)
        {
            q.push(i);
            int x=id[i];
            a[i][x]=1;
        }
    }
    for(reg int j=1;j<=ORDER;j++)
    {
        int point=order[j];
        int x=id[point];
        a[point][x]=1;
        for(reg int i=head1[point];i;i=edge[i].nxt)
        {
            int t=edge[i].to;
            a[t] |= a[point];
        }
    }

    // Get_ans

    for(reg int i=l;i<=r;i++)
    {
        int x=col[ask[i].x];
        int y=col[ask[i].y];
        if(a[x][id[y]])
            cout<<"Y";
        else
            cout<<"N";
    }
}
int main()
{
    //tarjan

    n=read(),m=read(),Q=read();
    for(int i=1;i<=m;i++)
    {
        int x=read(),y=read();
        v[x].push_back(y);
    }
    for(int i=1;i<=n;i++)
    {
        if(dfn[i]==0)
        tarjan(i);
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<(int)v[i].size();j++)
        {
            int x=col[i];
            int y=col[v[i][j]];
            if(x==y)
                continue;       
            in[x]++;
            add(y,x);
        }
    }

    //topo_sort

    for(int i=1;i<=color;i++)
        re_in[i]=in[i];
    for(reg int i=1;i<=color;i++)
    {
        if(in[i]==0)
            q.push(i);
    }
    while(!q.empty())
    {
        int point=q.front();
        q.pop();
        order[++ORDER]=point;
        for(reg int i=head1[point];i;i=edge[i].nxt)
        {
            int t=edge[i].to;
            in[t]--;
            if(in[t]==0)
            q.push(t);
        }
    }

    // divide segments

    for(int i=1;i<=Q;i++)
        ask[i].x=read(),ask[i].y=read();
    int len=20000;
    int now=1;
    while(true)
    {
        if(now+len-1<Q)
        {
            Work(now,now+len-1); // Get_ans
            now=now+len;
        }
        else
        {
            Work(now,Q); // Get_ans
            break;
        }
    }
    return 0;
}
Back to Top