奥运

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

Total Submission(s): 159 Accepted Submission(s): 66

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

Sample Output

0
1506
0

Source

HDOJ 2008 Summer Exercise（4）- Buffet Dinner

Recommend

lcy

/*
题意：汉语题目略

初步思路：离散数学中讲矩阵的乘法的时候说过，矩阵的n次方，就是走n步能到达的地方，m[i][j]表示从i到j的方案数，
    这个题输入有点麻烦，就是只有30个城市，这个题输入有点麻烦，就是只有30个城市，城市的名字是1e32 ，所以建
    矩阵的时候不能用这个名字，而是放缩一下。
#问题：矩阵的处理老是处理不好，但是模板应该没问题

#找到错误：矩阵的n次方是：必须n步,i到j的方案数，应该是相加的
*/
#include<bits/stdc++.h>
#define ll long long
#define mod 2008
using namespace std;
map<ll,int>m;//用来映射城市的建图
int city;//用来表示描述中出现的总城市数量
/***********************矩阵快速幂模板****************************/
const int maxn=35;

class Matrix {
    public:
        int a[maxn][maxn];
        int n;  

        void init(int x) {
            memset(a,0,sizeof(a));
            if (x)  
                for (int i = 0; i < maxn ; i++)
                    a[i][i] = 1;
        }

        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] = (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;
        }
}unit;
/***********************矩阵快速幂模板****************************/


/*****************分治求(a^1+a^2+...+.a^p)%mod********************/
Matrix Cal(Matrix a,int p)  {
    if (p == 1)
        return a;
    if (p & 1)
        return a.power(p) + Cal(a, p-1);
    else
        return Cal(a, p/2) * (a.power(p/2) + 1);
}
/*****************分治求(a^1+a^2+...+.a^n)%mod********************/

void init(){
    unit.init(0);
    m.clear();
    city=0;
}
int n,k,t1,t2;
ll p1,p2,v1,v2;
int main(){
    // freopen("in.txt","r",stdin);
    while(scanf("%d",&n)!=EOF){
        init();
        for(int i=0;i<n;i++){
            scanf("%lld%lld",&p1,&p2);
            if(m.find(p1)==m.end())//没有的
                m[p1]=city++;
            if(m.find(p2)==m.end())
                m[p2]=city++;
            unit.a[m[p1]][m[p2]]++;//建图
        }
        unit.n=city;
        //cout<<"city="<<city<<endl;
        // for(int i=0;i<city;i++){
            // for(int j=0;j<city;j++){
                // cout<<unit.a[i][j]<<" ";
            // }
            // cout<<endl;
        // }
        scanf("%d",&k);
        for(int i=0;i<k;i++){
            scanf("%lld%lld%d%d",&v1,&v2,&t1,&t2);
            if(m.find(v1)==m.end()||m.find(v2)==m.end()){
                printf("0
");
                continue;
            }
            if(t1>t2){
                swap(t1,t2);
            }
            if(t1==0){//且t1=0时的走法数为0
                if(t2==0)
                    printf("0
");
                else 
                    printf("%d
",Cal(unit,t2).a[m[v1]][m[v2]]);
                continue;
            }
            if(t1==1){
                // for(int i=0;i<city;i++){
                    // for(int j=0;j<city;j++){
                        // cout<<unit.power(2).a[i][j]<<" ";
                    // }
                    // cout<<endl;
                // }
                printf("%d
",Cal(unit,t2).a[m[v1]][m[v2]]);
            }
            else
                printf("%d
",( Cal(unit,t2).a[m[v1]][m[v2]]-Cal(unit,t1-1).a[m[v1]][m[v2]] +mod)%mod);//这里一定要这么处理，
                //要不然会出来负数的
        }
    }
    return 0;
}