在洛谷引用别的网站不会被封吧(心虚)
by Coder_User @ 2022-09-23 19:51:31
所以......
by zhang_kevin @ 2022-09-23 19:52:03
纯老师太强辣%%%%
by rabbitohh @ 2022-09-23 20:12:25
# [评测记录](https://www.luogu.com.cn/record/100012741)
# 平均用时仅 $79.5 \mathrm{ms}$
```cpp
#include <bits/stdc++.h>
using namespace std;
#define F(i,a,b) for(register int i=a;i<=b;++i)
#define ll long long
int head[55],nxt[130],to[130],ct = 1;
inline void add(int u,int v)
{
nxt[++ct] = head[u];
head[u] = ct;
to[ct] = v;
}
const int mod = 45989;
struct mat
{
ll a[130][130];
mat()
{
memset(a,0,sizeof(a));
}
inline mat friend operator*(const mat &A,const mat &B)
{
mat ans;
F(i,2,ct)
F(k,2,ct)
{
register int p = A.a[i][k];
F(j,2,ct) ans.a[i][j] += p * B.a[k][j];
}
F(i,2,ct)
F(j,2,ct)
ans.a[i][j] %= mod;
return ans;
}
inline mat friend operator^(mat A,int b)
{
mat ans = A;
--b;
while(b)
{
if(b & 1) ans = ans * A;
A = A * A;
b >>= 1;
}
return ans;
}
};
int n,m,t,A,B;
int main()
{
scanf("%d%d%d%d%d",&n,&m,&t,&A,&B);
++A,++B;
while(m--)
{
int u,v;
scanf("%d%d",&u,&v);
++u,++v;
add(u,v);
add(v,u);
}
mat C;
F(u,1,n)
for(register int i = head[u];i;i = nxt[i])
for(register int j = head[to[i]];j;j = nxt[j])
if(j != (i^1))
C.a[i][j] = 1;
C = C ^ (t-1);
ll ans = 0;
for(register int i = head[A];i;i = nxt[i])
{
for(register int j = head[B];j;j = nxt[j]) ans += C.a[i][j^1];
ans %= mod;
}
printf("%lld",ans);
return 0;
}
```
by Wangxun @ 2023-01-16 19:50:11
使用:
+ inline 优化
+ 减少取模次数
+ 链式前向星
+ ……
等。
by Wangxun @ 2023-01-16 19:51:29
全局long long,你不T谁T
by hjxhjx @ 2023-09-09 20:13:01