2023.6.4拷逝

# 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;
}