D - Power Products

Solution

std::map 维护即可。

Code

#include<bits/stdc++.h>

#define int long long

#define pii pair<int,int>

using namespace std;

const int maxn=1e5+5;

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(){

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\le 2000$。

Solution

$$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;

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(){
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

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

Code

#include<bits/stdc++.h>

#define int long long

using namespace std;

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];

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(){

fa[0]=-1; deep[0]=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;
}