# T1
首先题目没有强制让我们一起算 $k^{r(p)}+r^2(p)$ ，我们可以把它拆成两部分，一部分是 $k^{r(p)}$ ，一部分是 $r^2(p)$ 。
考虑递推求解两个部分。先看第一个部分。设 $n$ 的全排列的逆序对个数分别是 $p_1,p_2,...,p_{n!}$ ，并假设我们已经知道 $k^{r(p)}$ 的值。现在新增一个数 $n+1$ ，如果它是最后一个数，那么新形成的排列的逆序对个数分别是 $p_1,p_2,...,p_{n!}$ ；如果它是倒第二个数，那么新形成的排列逆序对个数分别是 $p_1+1,p_2+1,...,p_{n!}+1$ ......如果它是第一个数，那么新形成的排列的逆序对个数分别是 $p_1+n,p_2+n,...,p_{n!}+n$ 。这时新的 $\sum k^{r(p')}$ 的结果应该是 $\sum k^{r(p)}\times (1+k+k^2+...+k^n)$
再看第二个部分。新的 $\sum r^2(p')$ 应该是 $\sum r^2(p)\times (n+1)+(2+4+...+2n)\times \sum r(p)+n!\times (1^2+2^2+3^2+...+n^2)$ 。但这时我们引入了 $\sum r(p')$ ，还需要同时更新它。 $\sum r(p')=(1+2+...+n)\times n!+\sum r(p)\times (n+1)$ .
处理好这两部分后，直接相加就是答案。时间复杂度$O(n+t)$ .
$code:$
#include<iostream> #include<cstdio> using namespace std; const long long mod=1e9+7; long long n,t,k,fac,ans1[5],ans2[5],ans3[5]; int main(){ //freopen("concert.in","r",stdin); //freopen("concert.out","w",stdout); scanf("%lld",&t); while(t--){ scanf("%lld%lld",&n,&k); ans1[1]=1;ans2[1]=ans3[1]=0;//1:k^n,2:n^2,3:n long long sum=1,sum2=0,p=1; fac=1; for(long long i=2;i<=n;++i){ p=p*k%mod; sum=(sum+p)%mod; ans1[i&1]=(ans1[(i-1)&1]*sum)%mod; } for(long long i=2;i<=n;++i){ fac=fac*(i-1)%mod; sum2=(sum2+(i-1)*(i-1)%mod)%mod; ans3[i&1]=(fac*(i*(i-1)/2%mod)%mod+(i*ans3[(i-1)&1]%mod))%mod; ans2[i&1]=ans2[(i-1)&1]*i%mod; ans2[i&1]=(ans2[i&1]+((ans3[(i-1)&1]*i%mod*(i-1)%mod)%mod))%mod; ans2[i&1]=(ans2[i&1]+(fac*sum2%mod))%mod; } printf("%lld\n",(ans1[n&1]+ans2[n&1])%mod); } fclose(stdin);fclose(stdout); return 0; }
# T2
新建一个超级源点，将超级源点和所有朋友连边，跑最短路，输出每个点的路径长度$-1$即可。
$code:$
#include<iostream> #include<cstdio> #include<queue> using namespace std; const int l=100005; int n,m,k,u,v,tot,pos[l],nxt[l*20],ver[l*20],head[l*20],ans[l],vis[l],dis[l]; struct node{ int to,w; friend bool operator < (node a,node b){ return a.w>b.w; }; };priority_queue <node> q; void add(int x,int y){ nxt[++tot]=head[x];head[x]=tot;ver[tot]=y; } void bfs(int x){ q.push((node){x,0});dis[x]=0; while(!q.empty()){ node f=q.top();q.pop(); if(vis[f.to]) continue; vis[f.to]=1; for(int i=head[f.to];i;i=nxt[i]){ int y=ver[i]; if(dis[y]>dis[f.to]+1){ dis[y]=1+dis[f.to]; q.push((node){y,dis[y]}); } } } } int main(){ //freopen("39c5bb.in","r",stdin); //freopen("39c5bb.out","w",stdout); scanf("%d%d%d",&n,&m,&k); for(int i=1;i<=m;++i){ scanf("%d%d",&u,&v); add(u,v);add(v,u); } for(int i=1;i<=n;++i) ans[i]=1e9; bool ok=1; for(int i=1;i<=k;++i) scanf("%d",&pos[i]),add(0,pos[i]),add(pos[i],0); for(int i=0;i<=n;++i) vis[i]=0,dis[i]=1e9; bfs(0); for(int i=1;i<=n;++i) printf("%d ",dis[i]-1); printf("\n"); fclose(stdin);fclose(stdout); return 0; }