Hdu 2254 奥运 (矩阵)

柔情只为你懂 2022-09-08 11:52 112阅读 0赞

题意：给出n条道路，k个询问，每个询问包括起点v1、终点v2、t1天、t2天 求从v1到v2走了i天一共有多少走法(mod 2008)？(t1<=i<=t2)

思路：矩阵的应用，由离散数学知识：

一张有向图的邻接矩阵A，A表示所有点之间路径长度为一的路径数量，A^n则表示路径长度为n的路径数量

设图的可达矩阵为a，则答案为a^t1+a^(t1+1)……+a^t2。

本题数据范围太大，需要离散化

#pragma warning(disable:4786)
    #include <map>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    
    const int N=35;
    const int mod=2008;
    
    class Matrix
    {
    public:
    	int a[N][N];
    	int n;   //矩阵大小
    
    	void init (int x)
    	{
    		memset(a,0,sizeof(a));
    		if (x) for (int i=0;i<N;i++)
    			a[i][i]=1;
        }
    
    	void read (int _n)
    	{
    		n=_n;      //
    		for (int i=0;i<n;i++)
    			for (int j=0;j<n;j++)
    			{
    				scanf("%d",&a[i][j]);
    				a[i][j]%=mod;
    			}
    	}
    
    	Matrix operator + (Matrix b)
    	{
    		Matrix c;
    		c.n=n;
    		for (int i=0;i<n;i++)
    			for (int j=0;j<n;j++)
    				c.a[i][j]=(a[i][j]+b.a[i][j])%mod;
    		return c;
    	}
    
        Matrix operator + (int x)
    	{
    		Matrix c=*this;
    		for (int i=0;i<n;i++)
    			c.a[i][i]+=x;
    		return c;
    	}
    
    	Matrix operator * (Matrix b)
    	{
    		Matrix p;
    		p.n=b.n;   //
    		p.init(0);
    		for (int i=0;i<n;i++) for (int j=0;j<n;j++)
    			for (int k=0;k<n;k++)
    				(p.a[i][j]+=a[i][k]*b.a[k][j]%mod)%=mod;
    		return p;
    	}
    
    	Matrix power (int t)
    	{
    		Matrix ans,p=*this;
    		ans.n=p.n;  //
    		ans.init(1);
    		while (t)
    		{
    			if (t&1) ans=ans*p;
    			p=p*p;
    			t>>=1;
    		}
    		return ans;
    	}
    
    	void print (int n)
        {
    		for (int i=0;i<n;i++)
    			for (int j=0;j<n;j++)
    				printf(j==n?"d\n":"%d ",a[i][j]);
    	}
    }a;
    
    map<int,int> mp;
    
    Matrix Cal (Matrix a,int n)   //分治求(a^1+a^2+...+.a^n)%mod
    {
        if (n==1) return a;
        if (n&1)
            return a.power(n)+Cal(a,n/2)*(a.power(n/2)+1);
        else
            return Cal(a,n/2)*(a.power(n/2)+1);
    }
    
    int main ()
    {
    #ifdef ONLINE_JUDGE
    #else
    	freopen("read.txt","r",stdin);
    #endif
        int n,m;
        while (~scanf("%d",&n))
        {
            a.init (0);
            mp.clear();
            int id=0,i,u,v,t1,t2;
            for (i=0;i<n;i++)
            {
                scanf("%d%d",&u,&v);
                if (mp.find(u)==mp.end()) mp[u]=id++;
                if (mp.find(v)==mp.end()) mp[v]=id++;
                a.a[mp[u]][mp[v]]++;
            }
    
            a.n=id;   //记得传递矩阵大小
            scanf("%d",&m);
            while (m--)
            {
                scanf("%d%d%d%d",&u,&v,&t1,&t2);
                if (mp.find(u)==mp.end() || mp.find(v)==mp.end())
                {
                    printf("0\n");
                    continue;
                }
                if (t1>t2) swap(t1,t2);
                int s=mp[u],t=mp[v];
                if (t1==0)
                {
                    if (t2==0) printf("0\n");
                    else
                    {
                        printf("%d\n",Cal(a,t2).a[s][t]);
                    }
                }
                else if (t1==1)
                    printf("%d\n",Cal(a,t2).a[s][t]);
                else
                {
                    int ans=Cal(a,t2).a[s][t]-Cal(a,t1-1).a[s][t];
                    ans=(ans%mod+mod)%mod;
                    printf("%d\n",ans);
                }
            }
        }
    	return 0;
    }