赛时：0+0+0+0+动车mrfz肉鸽竞赛1266
p1：赛题
T1：简单质因数分解
T2：简单背包
T3（tj特供）：比较简单判环+树D
T4：
形式化的,对于n个点，设第i个环的长度为ri
定义：
F(i,j)=0（i,j在同一个环上）
F(i,j)=lcm(r3~rn,r1+r2)
求F(i,j)，i,j:1-n;
1.暴力复杂度n^3;
2.观察到答案只和环的长度有关，通过存有多少种不同长度的环：n->sqrt(n)，总复杂度n^2
3.观察答案，对于一个ans，其质因数分解出P^q中，q由原序列中r分解出最大的p^q决定
想到对r序列质因数分解，计算ans时通过合并每个出现质数的最大指数
这样看起来貌似是m^3logm，复杂度瓶颈就在于计算LCM（全都要算一遍）
再看一下“3”
原序列中最大的p^q?
所以一个数至多影响log(r1)个数
4.最坏情况分析：前两个都被删去->存3个
就可以用log(r)的复杂度完成对当前答案的一次修改
总复杂度：m^2*log^2(m)=nlog^2(n)
然后就收获一个120多行的诗人代码
#include<bits/stdc++.h>
using namespace std;
const int M=1000011;
int T,n,a[M],vis[M],tot,rin[M],rrin[M],k[M],m,gl[M],mod=1000000007;
unordered_map<int,int> mp,mpp;
void dfs(int x)
{
if(vis[x]==1) return;
vis[x]=1,rin[tot]++;
dfs(a[x]);
return;
}
int pr1[M][30],pr2[M][30],num1[M];
int gg[M][4],tr[M];
int ans1[M],ans2[M],tot_ans;
long long ans,t_ans;
void work_every_pri()
{
int num2=0;
for(int i=2;i<=M;i++)
{
if(gl[i]==0)
{
int ty=0;
for(int j=i;j<=M;j=j+i)
{
num2++;
mpp[i]=num2;
ty++;
if(mp[j]!=0)
{
num1[mp[j]]++;
pr1[mp[j]][num1[mp[j]]]=i;//r's prime
pr2[mp[j]][num1[mp[j]]]=ty;
if(tr[num2]==3)
{
gg[num2][1]=gg[num2][2];
gg[num2][2]=gg[num2][3];
gg[num2][3]=mp[j];
}
else
{
tr[num2]++;
gg[num2][tr[num2]]=mp[j];
}
}
tot_ans++;
ans1[tot_ans]=i;//ans's prime
ans2[tot_ans]=pr2[gg[num2][tr[num2]]][num1[gg[num2][tr[num2]]]];
gl[j]=1;
}
}
}
}
int pian[M];
queue<int> qq;
void tag(int xa)
{
}
long long work(int x,int y)
{
for(int i=1;i<=num1[x];i++)
{
if(gg[mpp[pr1[x][i]]][tr[mpp[pr1[x][i]]]]!=x) continue;
pian[mpp[pr1[x][i]]]++;
tr[mpp[pr1[x][i]]]--;
qq.push(mpp[pr1[x][i]]);
}
for(int i=1;i<=num1[y];i++)
{
if(gg[mpp[pr1[y][i]]][tr[mpp[pr1[y][i]]]]!=y) continue;
pian[mpp[pr1[y][i]]]++;
tr[mpp[pr1[y][i]]]--;
qq.push(mpp[pr1[y][i]]);
}
tag(rrin[x]+rrin[y]);
}
int main()
{
cin>>T;
while(T--)
{
m=tot=0;
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]),vis[i]=rin[i]=rrin[i]=0;
for(int i=1;i<=n;i++)
{
if(vis[i]==0) tot++,dfs(i);
}
sort(rin+1,rin+1+tot);
int y=0;
for(int i=1;i<=tot;i++)
{
if(rin[i]!=rin[i-1]){
m++;
rrin[m]=rin[i];
mp[rrin[m]]=m;
k[m-1]=y;
y=1;
}
else y++;
}
work_every_pri();
k[m]=y;
//k->rin num
//rrin-> rin length
for(int i=1;i<=m;i++)
{
t_ans=work(i,i);
if(k[i]%2==0) ans+=((t_ans*(k[i]/2)%mod)*(k[i]-1))%mod;
else ans+=((t_ans*((k[i]-1)/2)%mod)*k[i])%mod;
ans%=mod;
for(int j=i+1;j<=m;j++)
{
t_ans=work(i,j);
ans+=((t_ans*(k[i])%mod)*k[j])%mod;
ans%=mod;
}
}
printf("%lld\n",ans);
}
return 0;
}
T5：不会打，摸了
P2：铀蛆的题目
T1~3没认真看
T4：有点难的树形dp
将变换序列放到完全二叉树上，定义根为A,左儿子为B，右儿子为C，讨论：
A<min(B,C) 不交换
B<min(A,C) 交换A和B
C<min(A,B）交换A和C……然后A和B呢？
手玩几组样例，发现可能存在一种方式，可以将右子树的B’换上来
考虑此时较小的C，若交换A，B得到C的一个位置p1,不交换得到p2
显然若p1<p2则交换，否则不交换
又已知一个点只能一直与其祖先交换，在记忆化处理下交换序列长度在log(n)级别
直接暴力跑交换序列更新答案就好了