### 我再不打暴力我是傻逼
T1：是一道找规律题，当然可以用矩阵快速幂过
递推式：dp[n]=dp[n-1](1/nn+(n-1)^2/n^2)+(1-dp[n])*2/n^2
(dp[n]:操作n次，在原位的概率)
(md我比赛推出70分递推式没打)
宸的逆天三行代码：
#include<bits/stdc++.h>
using namespace std;
long long T,n,m,mod=998244353,k1,k2,k3,k4;
long long kuai(long long x,long long y)
{
long long res=1;
while(y>=1)
{
if(y%2==1) res=(res*x)%mod;
x=(x*x)%mod;
y/=2;
}
return res;
}
int main()
{
freopen("poster.in","r",stdin);
freopen("poster.out","w",stdout);
cin>>T;
while(T--)
{
scanf("%lld%lld",&n,&m);
if(n==1)
{
printf("0\n");
continue;
}
k1=((kuai((n-2)%mod,m)*(n%mod))%mod+kuai(n%mod,m)-kuai((n-2)%mod,m)+mod)%mod;
k2=kuai(n%mod,m);
printf("%lld\n",(n-(k1*kuai(k2,mod-2))%mod+mod)%mod);
}
return 0;
}
T2：大水题，三分钟想出来，10分钟切
（话说NOIP T2会这么简单吗？？？？）
#include<bits/stdc++.h>
using namespace std;
const long long MAX=11451419198109999;
long long n,uu,vv,val[1000005],dp[1000005][2][2];//放/不放；取/不取
vector<int> G[1000005];
void dfs(int x,int fa)
{
int ff=0;
for(int i=0;i<G[x].size();i++)
{
if(G[x][i]!=fa)
{
ff=1;
dfs(G[x][i],x);
}
}
if(ff==0)
{
dp[x][1][1]=val[x];
dp[x][0][0]=0;
return;
}
////////dp[1][1]
long long Min=11451419198109999,sum=0,to;
for(int i=0;i<G[x].size();i++)
{
if(G[x][i]!=fa)
{
to=G[x][i];
Min=11451419198109999;
Min=min(Min,min(dp[to][1][0],dp[to][1][1]));
Min=min(Min,min(dp[to][0][0],dp[to][0][1]));
sum+=Min;
if(sum>=MAX) break;
}
}
dp[x][1][1]=sum+val[x];
/////////dp[0][0]
sum=0;
for(int i=0;i<G[x].size();i++)
{
if(G[x][i]!=fa)
{
to=G[x][i];
sum+=dp[to][0][1];
if(sum>=MAX) break;
}
}
dp[x][0][0]=sum;
///////////dp[0][1]
sum=0;
bool flag=0;
for(int i=0;i<G[x].size();i++)
{
if(G[x][i]!=fa)
{
to=G[x][i];
if(dp[to][1][1]<=dp[to][0][1])
{
flag=1;
}
sum+=min(dp[to][1][1],dp[to][0][1]);
if(sum>=MAX) break;
}
}
if(flag==1) dp[x][0][1]=sum;
else
{
Min=MAX;
for(int i=0;i<G[x].size();i++)
{
if(G[x][i]!=fa)
{
to=G[x][i];
Min=min(Min,sum-dp[to][0][1]+dp[to][1][1]);
}
}
dp[x][0][1]=Min;
}
return ;
}
int main()
{
freopen("router.in","r",stdin);
freopen("router.out","w",stdout);
cin>>n;
for(int i=1;i<=n;i++)
{
scanf("%lld",&val[i]);
dp[i][0][0]=dp[i][1][0]=11451419198109999;
dp[i][0][1]=dp[i][1][1]=11451419198109999;
}
for(int i=1;i<=n-1;i++)
{
scanf("%lld%lld",&uu,&vv);
G[uu].push_back(vv);
G[vv].push_back(uu);
}
dfs(1,0);
// for(int i=1;i<=n;i++)
// {
// cout<<i<<":"<<dp[i][1][1]<<" "<<dp[i][0][1]<<" "<<dp[i][0][0]<<endl;
// }
// cout<<dp[3][0][1]<<endl<<dp[2][0][0]<<endl<<dp[1][1][1]<<endl<<dp[1][0][1]<<endl;
long long ans=MAX;
ans=min(ans,dp[1][1][1]);
ans=min(ans,dp[1][0][1]);
cout<<ans;
return 0;
}
T3 赛时没想，赛后发现70分暴力很好打，几分钟就打完了
（我TM到底为什么要磕T1啊啊啊啊啊啊）
观察到一段基因，反推祖先，这个过程是确定的（每次用大减小）
又可以发现像是求gcd的过程，于是想到每一次操作记录操作序列（逆序）
一段基因是另一段基因的祖先当且仅当它们gcd相等且一段是另一段的前缀
想到先把对应的gcd的序列最后一个字符后打特殊标记，然后排序，则前缀一样的一段总连续，直接二分查找两次就好了
（一打就费）
70分：（100没打出来）
#include<bits/stdc++.h>
using namespace std;
long long n,q,a[50005],b[50005],c[50005],d[50005],ans[50005],f1[50005],f2[50005];
int check(long long st,long long en,long long aa,long long bb)
{
//if(aa<bb) swap(aa,bb);
//if(st<en) swap(st,en);
// cout<<st<<" "<<en<<" "<<aa<<" "<<bb<<endl;
if(aa==bb&&((st!=aa)||(en!=bb))) return 0;
if(aa<st||bb<en) return 0;
if(st==aa&&en==bb) return 1;
while(aa!=bb)
{
//if(aa<bb) swap(aa,bb);
if(aa>bb)
{
if(en==bb&&aa%bb==st%en&&st>en) return 1;
}
else
{
if(st==aa&&bb%aa==en%st&&st<=en) return 1;
}
if(aa>bb) aa%=bb;
else bb%=aa;
if(aa<st||bb<en) return 0;
}
return 1;
}
int main()
{
freopen("up4.in","r",stdin);
freopen("up.out","w",stdout);
cin>>n>>q;
for(int i=1;i<=n;i++)
{
scanf("%lld%lld",&a[i],&b[i]);
f1[i]=__gcd(a[i],b[i]);
}
for(int i=1;i<=q;i++)
{
scanf("%lld%lld",&c[i],&d[i]);
f2[i]=__gcd(c[i],d[i]);
}
for(int i=1;i<=q;i++)
{
for(int j=1;j<=n;j++)
{
if(f2[i]!=f1[j]) continue;
if(check(c[i],d[i],a[j],b[j])==1)
{
ans[i]++;
}
}
}
for(int i=1;i<=q;i++) printf("%lld\n",ans[i]);
return 0;
}