个人感觉这是这套题中最好的一道题了……

题意:给定一张有向图,以及一个k。之后有Q个询问,每次询问从s到t所有路径长度不超过k的路径的长度平方和。
n不超过100,k不超过

不妨将k+1,那么我们需要考虑所有路径长度小于k的路径长度平方和。
考虑如何计算答案。不妨设表示经过长度为i-1的路径,从s到t的方案数。

那么有:

不妨设
则:

不妨设D为邻接矩阵,I为单位矩阵。设G为所有点对间g的矩阵,设F为所有点对间f的矩阵,设A为所有点对间ans的矩阵。那么我们有:

那么按以上式子矩乘即可。复杂度
实现时要注意一点细节……不然矩乘容易出问题,爆栈什么的。

下面贴代码:

/**************************************************************
    Problem: 3610
    User: keavil
    Language: C++
    Result: Accepted
    Time:13908 ms
    Memory:48956 kb
****************************************************************/
 
#include<stdio.h>
#include<string.h>
int n,m,K,Q;
const long long mod = 1000000007;
struct matrix
{
    long long a[101][101];
    matrix(){memset(a,0,sizeof(a));}
    void setI(){for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)a[i][j]=(i==j);}
    matrix operator * (const matrix &t)const
    {
        matrix ret;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                for(int k=1;k<=n;k++)
                    ret.a[i][j]=(ret.a[i][j]+a[i][k]*t.a[k][j])%mod;
        return ret;
    }
    matrix operator + (const matrix &t)const
    {
        matrix ret;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                ret.a[i][j]=(a[i][j]+t.a[i][j])%mod;
        return ret;
    }
    matrix operator * (long long t)const
    {
        matrix ret;t%=mod;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                ret.a[i][j]=a[i][j]*t%mod;
        return ret;
    }
    void operator +=(const matrix &t){*this=*this+t;}
    void operator *=(const matrix &t) {*this=*this*t;}
    void operator *=(long long &t){*this=*this*t;}
}trans,tmp,mat[3][40],mapnow,tmp1,tmp2;int tnow;
void work(int w,int deep)
{
    if(w==1)
    {
        mat[0][deep].setI();
        mapnow=trans;tnow=1;
        return ;
    }
    work(w>>1,deep+1);
    int d=w>>1;
    if(tnow==d-1)mapnow*=trans,tnow++;
    tmp1=mat[0][deep+1]*mapnow;
    tmp2=mat[1][deep+1]*mapnow;
    mat[0][deep]=tmp1;
    mat[0][deep]+=mat[0][deep+1];
    mat[1][deep]=tmp2;
    mat[1][deep]+=mat[1][deep+1];
    mat[1][deep]+=tmp1*(w>>1);
    mat[2][deep]=mat[2][deep+1]*mapnow;
    mat[2][deep]+=mat[2][deep+1];
    mat[2][deep]+=tmp1*((long long)d*d);
    mat[2][deep]+=tmp2*(d<<1);
    mapnow*=mapnow;tnow<<=1;
    if(w&1)
    {
        mat[0][deep]+=mapnow;
        mat[1][deep]+=mapnow*(w-1);
        mat[2][deep]+=mapnow*((long long)(w-1)*(w-1));
    }
}
int main()
{
    scanf("%d%d%d%d",&n,&m,&K,&Q);
    while(m--)
    {
        int x,y;scanf("%d%d",&x,&y);
        trans.a[x][y]++;
    }
    work(K+1,0);
    while(Q--)
    {
        int x,y;scanf("%d%d",&x,&y);
        printf("%lld\n",mat[2][0].a[x][y]);
    }
    return 0;
}

Comments

comments powered by Disqus