现在的位置: 首页 > 综合 > 正文

hdu 2254 不错的矩阵 从a到b 在规定时间内有多少条路到达

2013年05月25日 ⁄ 综合 ⁄ 共 2667字 ⁄ 字号 评论关闭

http://acm.hdu.edu.cn/showproblem.php?pid=2254

奥运

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1629    Accepted Submission(s): 393

Problem Description
北京迎来了第一个奥运会,我们的欢呼声响彻中国大地,所以今年的奥运金牌 day day up!
比尔盖兹坐上鸟巢里,手里摇着小纸扇,看的不亦乐乎,被俺们健儿的顽强拼搏的精神深深的感动了。反正我的钱也多的没地方放了,他对自己说,我自己也来举办一个奥运会,看谁的更火。不过他的奥运会很特别:
1 参加人员必须是中国人;
2 至少会加法运算(因为要计算本人获得的金牌数)
他知道中国有很多的名胜古迹,他知道自己在t1 到 t2天内不可能把所有的地方都玩遍,所以他决定指定两个地方v1,v2,如果参赛员能计算出在t1到t2天(包括t1,t2)内从v1到v2共有多少种走法(每条道路走需要花一天的时间,且不能在某个城市停留,且t1=0时的走法数为0),那么他就会获得相应数量的金牌,城市的总数<=30,两个城市间可以有多条道路
,每条都视为是不同的。
 

Input
本题多个case,每个case:
输入一个数字n表示有n条道路 0<n<10000
接下来n行每行读入两个数字 p1,p2 表示城市p1到p2有道路,并不表示p2到p1有道路 (0<=p1,p2<2^32)
输入一个数字k表示有k个参赛人员
接下来k行,每行读入四个数据v1,v2,t1,t2 (0<=t1,t2<10000)
 

Output
对于每组数据中的每个参赛人员输出一个整数表示他获得的金牌数(mod 2008)
 

Sample Input
6 1 2 1 3 2 3 3 2 3 1 2 1 3 1 2 0 0 1 2 1 100 4 8 3 50
 

Sample Output
0 1506 0
 

Source
 

Recommend
lcy

        解题思路:求t1->t2天内,v1->v2一共有多少条的路径。
        就是要用到离散数学的邻接矩阵的n次幂各元素的值就是经过n条路可以到达该点。
        所以说这道题说白了就是叫你求 A^t1+a^(t1+1)+……A^(t2),
        输出v1,v2该元素的值模2008(注意负数的处理).所以就是要用到矩阵降幂+二分求和。

#include<stdio.h>
#include<string.h>
#include<map>
using namespace std;
 
#define ll int
#define mod 2008
struct Mat
{
	ll martix[30][30];
};
Mat temp,q,p,res,init,mid1,mid2;
ll N;
Mat Martix_Add(Mat a,Mat b)  
{  
    ll i,j;  
    Mat c;  
    for (i=0;i<N;i++)  
    {  
        for (j=0;j<N;j++)  
        {  
            c.martix[i][j]=(a.martix[i][j]+b.martix[i][j])%mod;  
        }  
    }  
    return c;  
}  
Mat Martix_Mul(Mat a,Mat b)  
{  
    ll i,j,l;  
    Mat c;  
    for (i=0;i<N;i++)  
    {  
        for (j=0;j<N;j++)  
        {  
            c.martix[i][j]=0;  
            for (l=0;l<N;l++)  
            {  
                c.martix[i][j]+=(a.martix[i][l]*b.martix[l][j])%mod;  
                c.martix[i][j]%=mod;  
            }  
        }  
    }  
    return c;  
}  
  
Mat er_fun(Mat e,ll x)  //求矩阵e^x  
{  
	Mat tp; 
    tp=e;
    e=res;  //res是单位矩阵
    while(x)  
    {  
        if(x&1)  
            e=Martix_Mul(e,tp);  
        tp=Martix_Mul(tp,tp);  
        x>>=1;  
    }  
    return e;  
}  
  
Mat Solve(Mat a,ll p)  //计算 a^1+a^2.....+a^p
{  
    if(p==1||p==0) return a;  
    else if(p&1) return Martix_Add(er_fun(a,p),Solve(a,p-1));  
    else return Martix_Mul(Solve(a,p>>1),Martix_Add(er_fun(a,p>>1),res));  
}  
int main()
{
     ll n,j,i,cnt,ans;
	 __int64 x,y;
	 for(i=0;i<30;i++)
		 for(j=0;j<30;j++)
		 {
			 if(i==j) res.martix[i][j]=1;
			 else res.martix[i][j]=0;
		 }
	 while(scanf("%d",&n)!=EOF)
	 {
		 cnt=0;
		 map<__int64,int>mp;
           memset(init.martix,0,sizeof(init.martix));
		   while(n--)
		   {
			   scanf("%I64d %I64d",&x,&y);
               if(mp.find(x)==mp.end())
			                 mp[x]=cnt++;
			   if(mp.find(y)==mp.end())
				   mp[y]=cnt++;
			   init.martix[mp[x]][mp[y]]++;
		   }
		   N=cnt;
		   ll m;
		   scanf("%d",&m);
		   while(m--)
		   {
			   ll t1,t2;
			   scanf("%I64d %I64d %d %d",&x,&y,&t1,&t2);
			   if(mp.find(x)==mp.end()||mp.find(y)==mp.end()||(t1==0&&t2==0))//注意细节
			   {
				   printf("0\n");
				   continue;
			   }
			   x=mp[x];
			   y=mp[y];
			   if(t1>1)
			   {
				   mid1=Solve(init,t1-1);
				   mid2=Solve(init,t2);
				    ans=(mid2.martix[x][y]-mid1.martix[x][y])%mod;
			   }
			   else
			   {
				  mid1=Solve(init,t2);
				  ans=mid1.martix[x][y]%mod;
			   }
			  
               if(ans<0) ans+=mod;
			   printf("%d\n",ans);
		   }
	 }
	return 0;
}
//不能全用__int64  这样会栈溢出

另外 本题海可以用    矩阵连续相乘 保存 起来  Mat a[10000]  把所有得到的矩阵保存下来

hnust_xiehonghao

抱歉!评论已关闭.