Link: Codeforces Round #596 (Div. 2, based on Technocup 2020 Elimination Round 2)

D - Power Products

Description

给出一个长度为 $n$ 的序列和一不小于 2 的整数 $k$，要求找出数字对 $(i,j)$ 的数量，满足 $i\lt j$ 并且存在一个整数 $x$ 使得 $a_i\ast a_j = x^k$。

Solution

对于每个数字进行质因数分解，分解成 $x=p_1^{k_1}+p_2^{k_2}+\dots+p_m^{k_m}$，我们用一个 std::vector 存储若干个二元组 $(p_i,k_i)$，表示这个数字有 $k_i$ 个 $p_i$ 这个质因子，显然存储的时候这个 $k_i$ 次数可以对题中所给的 $K$ 取模。如果存在两个数字满足 $p_i$ 集合相同，并且对于所有 $p_i$，$k_1i + k_2i = K$，则说明这两个数字相乘能得到 $x^K$。
用 std::map 维护即可。

Code

#include<bits/stdc++.h>

#define int long long

#define pii pair<int,int>

using namespace std;

const int maxn=1e5+5;

inline int read(){
    int ret=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}

const int N=1e5;

int n,k;
int a[maxn];

int prime[maxn];
bool flag[maxn];

map<vector<pii>,int> hsh;

void build_prime(){
    memset(flag,true,sizeof(flag));
    flag[1]=false;
    for (int i=2;i<=N;i++){
        if (flag[i]) prime[++prime[0]]=i;
        for (int j=1;j<=prime[0];j++){
            if (i*prime[j] > N) break;
            flag[i*prime[j]]=false;
            if (i%prime[j]==0) break;
        }
    }
}

vector<pii> break_down(int x){
    vector<pii> ret; ret.clear();
    for (int i=1;i<=prime[0];i++) if (x%prime[i]==0){
        int cnt=0;
        while (x%prime[i]==0) cnt++,x/=prime[i];
        if (cnt%k) ret.push_back(make_pair(prime[i],cnt%k));
    } else if (x==1) break;
    return ret;
}

vector<pii> get_comp(vector<pii> &vec){
    vector<pii> ret=vec;
    for (int i=0;i<ret.size();i++) ret[i].second=k-ret[i].second;
    return ret;
}

int ans=0;

signed main(){
    n=read(); k=read();
    for (int i=1;i<=n;i++) a[i]=read();

    build_prime();

    for (int i=1;i<=n;i++){
        vector<pii> now=break_down(a[i]);
        vector<pii> com=get_comp(now);
        ans+=hsh[com]; hsh[now]++;
    }

    printf("%lld\n",ans);
    return 0;
}

E - Rock Is Push

Description

你在一个 $n\ast m$ 的迷宫左上角 $1,1$ 位置，你要到达右下角 $n,m$ 的位置。每次你只能向右或者向下移动。
迷宫的一些格子里有石头。当你移动到有石头的格子时，石头就会按你移动的方向被推到下一个格子。如果下一个格子里有石头，它就会被推得更远，以此类推。迷宫被不可穿透的墙壁所包围，因此任何将你或任何石头移出迷宫的行为都是非法的。
求出起点到终点路径数量，对 $10^9+7$ 取模。
$n\le 2000$。

一些很有趣的动图（样例解释）：

Solution

定义 $R(i,j)$ 和 $D(i,j)$，表示走到 $i,j$ ，下一次分别要向右/向下走，上一次和下一次走的方向不一样，走到终点的方案数。
则 $R(n,m)=D(n,m)=1$。

考虑到以这种定义走到 $i,j$ 的时候，右下角能到达的石头位置都没有改变过；所以 $i,j$ 的状态可以独立考虑，和经过的路径无关。

假设 $i,j$ 右边或者下面有 $k$ 个石头，则

$$R(i,j)=\sum_{t=1}^{m-k-j} D(i,j+t)\\ D(i,j)=\sum_{t=1}^{n-k-i} R(i+t,j)$$

然后前缀和优化即可。

Code

#include<bits/stdc++.h>

#define int long long

using namespace std;

const int maxn=2005;
const int tt=1e9+7;

inline int read(){
    int ret=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}

int n,m;
char a[maxn][maxn];
int rock[maxn][maxn];
int sum_r[maxn][maxn],sum_d[maxn][maxn];
int d[maxn][maxn],r[maxn][maxn];

int sd[maxn][maxn],sr[maxn][maxn]; // DP prefix sum

signed main(){
    n=read(); m=read();
    for (int i=1;i<=n;i++) scanf("%s",a[i]+1);

    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
            rock[i][j]=a[i][j]=='R';

    if (n==1 && m==1){printf("%lld\n",1-rock[1][1]);return 0;}

    for (int i=1;i<=n;i++)
        for (int j=m;j>=1;j--)
            sum_r[i][j]=sum_r[i][j+1]+rock[i][j];
    for (int j=1;j<=m;j++)
        for (int i=n;i>=1;i--)
            sum_d[i][j]=sum_d[i+1][j]+rock[i][j];

    for (int i=n;i>=1;i--){
        for (int j=m;j>=1;j--){
            // for (int t=1;t<=n-sum_d[i+1][j]-i;t++) d[i][j]=(d[i][j]+r[i+t][j])%tt;
            // for (int t=1;t<=m-sum_r[i][j+1]-j;t++) r[i][j]=(r[i][j]+d[i][j+t])%tt;
            d[i][j] = (sr[i+1][j] - sr[i+ (n-sum_d[i+1][j]-i) +1][j] + tt)%tt;
            r[i][j] = (sd[i][j+1] - sd[i][j+ (m-sum_r[i][j+1]-j) +1] + tt)%tt;
            if (i==n && j==m) d[i][j]=r[i][j]=1-rock[i][j]; else
            if (i==n){d[i][j]=0; if (sum_r[i][j+1]) r[i][j]=0;} else 
            if (j==m){r[i][j]=0; if (sum_d[i+1][j]) d[i][j]=0;}

            sr[i][j]=(sr[i+1][j]+r[i][j])%tt;
            sd[i][j]=(sd[i][j+1]+d[i][j])%tt;
        }
    }

    printf("%lld\n",(d[1][1]+r[1][1])%tt);
    return 0;
}

F - Tree Factory

Description

给出一棵树，节点编号为 $[0,n-1]$，0 为树根，节点 $x$ 父亲的标号 $p(x)$ 小于 $x$。
你需要构造一条链，赋予链上每个点 $[0,n-1]$ 的标号，并且在对这个链进行 $k$ 次操作后，其形态和给出的树完全相同。
所谓的“操作”如下：选定一个点 $x$，满足 $x$ 不是树根并且其父亲 $p(x)$ 不是树根，把 $x$ 的父亲设置为 $p(p(x))$。其它所有点的父亲不变。
输出一种链上点的标号方案，然后输出操作次数和一种操作方案。操作次数不能大于 $10^6$ 的。保证有解。

$2\le n\le 10^5$。

Solution

考虑反着做，把给定的树变成一条链。如果每次操作都能使树的深度增加 1，那么我们最多只需要做 $n-1$ 次，满足答案的限制。那么考虑如何让每次操作都使深度加 1。
首先贪心地想，肯定选取树中从根节点出发的最长的一条路径作为链的基础，其他操作在剩余的点上完成。如果这条路径上所有节点都没有大于一个儿子，则已经做完了；否则找出一个有至少两个儿子的点 $x$，假设其一个在路径上的点是 $u$，另一个不在路径上的点是 $v$，我们另 $u$ 的父亲变成 $v$，就实现了深度增加。

具体实现，对最深的分叉点，把这个节点的所有儿子一个个合并。

参考 wxhtxdy 的代码……

Code

#include<bits/stdc++.h>

#define int long long

using namespace std;

inline int read(){
    int ret=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}

const int maxn=1e5+5;

int n,fa[maxn],deep[maxn];
int tot=0,lnk[maxn],nxt[maxn],to[maxn],son[maxn];

int opt[maxn],ans[maxn];

int heavy_son[maxn];

void add_edge(int x,int y){
    tot++; to[tot]=y; son[x]++;
    nxt[tot]=lnk[x]; lnk[x]=tot;
}

int cnt=0;

void DFS(int x){
    ans[++ans[0]]=x;
    for (int i=1;i<=cnt;i++) opt[++opt[0]]=x;
    cnt=0;
    for (int i=lnk[x];i;i=nxt[i]) if (to[i]!=heavy_son[x]) DFS(to[i]);
    if (heavy_son[x]) DFS(heavy_son[x]);
    cnt++;
}

signed main(){
    n=read();

    fa[0]=-1; deep[0]=1;
    for (int i=1;i<n;i++) fa[i]=read(),add_edge(fa[i],i),deep[i]=deep[fa[i]]+1;

    int max_deep=0,k=-1;
    for (int i=0;i<n;i++) if (deep[i]>max_deep) max_deep=deep[i],k=i;
    while (k!=-1){
        if (fa[k]!=-1) heavy_son[fa[k]]=k;
        k=fa[k];
    }

    DFS(0);

    for (int i=1;i<=ans[0];i++) printf("%lld ",ans[i]); printf("\n");

    printf("%lld\n",opt[0]);
    for (int i=1;i<=opt[0];i++) printf("%lld ",opt[i]);
    printf("\n");
    return 0;
}