P13863 [SWERC 2020] Decoration 题解

· · 题解

P13863 [SWERC 2020] Decoration 题解

题目传送门。

线性时间线性空间做法。

截止至 2025-09-26，暂无题解，但是随机抽样翻看过题记录都是用倍增做的。

题意

构造长度为 k 的数组 s，满足：

无解输出 -1。

思路

注意到 d_i 可以线性筛出来。

容易发现如果确定了 s_i 那么 s_{i+1} 也是确定的。

考虑 i 向 i+d_i 连有向边，因为每个点有一个出边，所以这个图是内向基环树森林。

原题目转化成在这个基环树森林上走长度为 k 的路径，点不能重复经过。

考虑一条长度为 k 的路径怎么组成，两种情况：

  1. 树上一个点到某个祖先的路径（这个点深度 \ge k）。
  2. 树上一个点到根，加上从根出发的环的某一段（这个点深度 <k）。

考虑对于每个点都算一遍从这个点开始的长度为 k 的路径，最后取最小即可。

这个玩意倍增做完了。但是莫名多了一个老哥。

所以把环搞出来，做环的前缀和（可能需要破环成链）。

然后在 dfs 的过程中动态维护一个数组，表示当前点到根的路径的前缀和。

然后分类讨论上面两种情况就做完了。

时间复杂度 O(n+k)，具体的看代码。

AC 代码

由于需要拓扑排序以及建反边之类的操作，常数略大。

::::success[code]

#include<bits/stdc++.h>
#define Code using
#define by namespace
#define wjb std
Code by wjb;
#define int long long
int in()
{
    int k=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')k=k*10+c-'0',c=getchar();
    return k*f;
}
void out(int x)
{
    if(x<0)putchar('-'),x=-x;
    if(x<10)putchar(x+'0');
    else out(x/10),putchar(x%10+'0');
}
const int N=1e6+10;
int n,k;
vector<int>e[N];
int b[N],p[N],d[N],x[N];
void init(int n)
{
    int tot=0;d[1]=1;
    for(int i=2;i<=n;i++)
    {
        if(b[i]==0)d[i]=2,p[++tot]=i,x[i]=1;
        for(int j=1;j<=tot&&i*p[j]<=n;j++)
        {
            b[i*p[j]]=1;
            if(i%p[j]==0)d[i*p[j]]=d[i]/(x[i]+1)*(x[i]+2),x[i*p[j]]=x[i]+1;
            if(i%p[j]==0)break;
            x[i*p[j]]=1,d[i*p[j]]=d[i]*2;
        }
    }
}
int deg[N];bool isring[N];
void toposort()
{
    queue<int>q;
    for(int i=0;i<n;i++)isring[i]=1;
    for(int i=0;i<n;i++)if(!deg[i])q.push(i);
    while(!q.empty())
    {
        int u=q.front();q.pop(),isring[u]=0;
        int v=(u+d[u])%n;
        if(!--deg[v])q.push(v);
    }
}
int vis[N];vector<int>s;
void dfs(int u)
{
    vis[u]=1,s.push_back(u);
    for(int v:e[u])if(!vis[v]&&isring[v])dfs(v);
}
int sum[N<<1];
int sumt[N],tot=0,len;
int minn=1e18,id=-1;
void solve(int u,int from)
{
    tot++,sumt[tot]=sumt[tot-1]+u;
    int val=1e18;
    if(len+tot-1>=k)
        if(tot>=k)val=sumt[tot]-sumt[tot-k];
        else val=sumt[tot]+sum[from]-sum[from-(k-tot)];
    if(val<minn)minn=val,id=u;
    for(int v:e[u])if(!isring[v])solve(v,from);
    sumt[tot--]=0;
}
void work()
{
    len=s.size();
    for(int i=1;i<=len;i++)sum[i]=sum[i-1]+s[i-1];
    for(int i=len+1;i<=2*len;i++)sum[i]=sum[i-1]+s[i-len-1];
    for(int i=len+1;i<=2*len;i++)tot=0,solve(s[i-len-1],i-1);
}
signed main()
{
    n=in(),k=in(),init(n);
    for(int i=0;i<n;i++)e[(i+d[i])%n].push_back(i),deg[(i+d[i])%n]++;
    toposort();
    for(int i=0;i<n;i++)if(!vis[i]&&isring[i])s.clear(),dfs(i),work();
    if(id==-1)out(-1),exit(0);
    for(int i=1;i<=k;i++)out(id),putchar(' '),id=(id+d[id])%n;
    return 0;
}

::::