bzoj 1875: [SDOI2009]HH去散步

 1 #include<bits/stdc++.h>
 2 #define N 100005
 3 #define M 10000005
 4 #define LL long long
 5 #define inf 0x3f3f3f3f
 6 using namespace std;
 7 inline int ra()
 8 {
 9     int x=0,f=1; char ch=getchar();
10     while (ch<‘0‘ || ch>‘9‘) {if (ch==‘-‘) f=-1; ch=getchar();}
11     while (ch>=‘0‘ && ch<=‘9‘) {x=x*10+ch-‘0‘; ch=getchar();}
12     return x*f;
13 }
14 const int p=45989;
15 int head[155];
16 int n,m,t,a,b,sum,cnt;
17 struct Edge{
18     int to,next;
19 }e[305];
20 struct Maxtri{
21     int a[155][155];
22     Maxtri(){
23         memset(a,0,sizeof(a));
24     }
25     friend Maxtri operator * (Maxtri a, Maxtri b) 
26     {
27         Maxtri ans;
28         for (int i=0; i<=cnt; i++)
29             for (int j=0; j<=cnt; j++)
30                 for (int k=0; k<=cnt; k++)    
31                     (ans.a[i][j]+=a.a[i][k]*b.a[k][j]%p)%=p;
32         return ans;
33     }
34     friend Maxtri operator ^ (Maxtri a, int b)
35     {
36         Maxtri ans;
37         for (int i=0; i<=cnt; i++) ans.a[i][i]=1;
38         for (;b;b>>=1,a=a*a)
39             if (b&1) ans=ans*a;
40         return ans;
41     }
42 };
43 Maxtri ans,A;
44 void insert(int x, int y){
45     e[++cnt].next=head[x]; e[cnt].to=y; head[x]=cnt;
46 }
47 int main()
48 {
49     n=ra(); m=ra(); t=ra(); a=ra()+1; b=ra()+1;
50     for (int i=1; i<=m; i++)
51     {
52         int x=ra()+1,y=ra()+1;
53         insert(x,y); insert(y,x);
54     }
55     for (int i=head[a];i;i=e[i].next)
56         ans.a[0][i]++;
57     for (int i=1; i<=cnt; i++)
58         for (int j=head[e[i].to];j;j=e[j].next)
59             if (j!=i+((i&1)?1:-1)) A.a[i][j]++;
60     A=A^(t-1); ans=ans*A;
61     for (int i=1; i<=cnt; i++)
62         if (e[i].to==b)
63             (sum+=ans.a[0][i])%=p;
64     cout<<sum;
65     return 0;
66 }