NC20462. [ZJOI2005]SWAMP 沼泽鳄鱼
描述
输入描述
输入文件共M + 2 + NFish行。第一行包含五个正整数N，M，Start，End和K，分别表示石墩数目、石桥数目、Start石墩和End石墩的编号和一条路线所需的单位时间。石墩用0到N–1的整数编号。第2到M + 1行，给出石桥的相关信息。每行两个整数x和y，0 ≤ x, y ≤ N–1，表示这座石桥连接着编号为x和y的两座石墩。第M + 2行是一个整数NFish，表示食人鱼的数目。第M + 3到M + 2 + NFish行，每行给出一条食人鱼的相关信息。每行的第一个整数是T，T = 2，3或4，表示食人鱼的运动周期。接下来有T个数，表示一个周期内食人鱼的行进路线。如果T＝2，接下来有2个数P0和P1，食人鱼从P0到P1，从P1到P0，……；如果T＝3，接下来有3个数P0，P1和P2，食人鱼从P0到P1，从P1到P2，从P2到P0，……； 如果T＝4，接下来有4个数P0，P1，P2和P3，食人鱼从P0到P1，从P1到P2，从P2到P3，从P3到P0，……。豆豆出发的时候所有食人鱼都在自己路线上的P0位置，请放心，这个位置不会是Start石墩。
输出描述
输出路线的种数，因为这个数可能很大，你只要输出该数除以10000的余数就行了。
【约定】 1 ≤ N ≤ 50 ； 1 ≤ K ≤ 2,000,000,000 ；1 ≤ NFish ≤ 20
示例1
输入:
6 8 1 5 3 0 2 2 1 1 0 0 5 5 1 1 4 4 3 3 5 1 3 0 5 1
输出:
2
说明:
【样例说明】C++14(g++5.4) 解法, 执行用时: 290ms, 内存消耗: 988K, 提交时间: 2020-04-03 18:45:33
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define SZ(x) ((int)x.size())
#define ALL(x) (x).begin(),(x).end()
#define lowbit(x) x&-x
#define pb push_back
#define ls (id<<1)
#define rs (id<<1|1)
#define Rint register int
typedef long long ll;
typedef double db;
typedef pair<db,ll> pii;
const int MAXN=2e6+10,MAXM=4e6+10;
const int INF=INT_MAX,SINF=0x3f3f3f3f;
const ll llINF=LLONG_MAX;
const int MOD=10000,mod=998244353;
const int inv2=5e8+4;
int n,k,m,s,t;
struct Matrix
{
ll a[55][55];
Matrix operator * (const Matrix &rhs)const
{
Matrix res;
memset(res.a,0,sizeof(res.a));
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
for(int k=0;k<n;k++)
(res.a[i][j]+=a[i][k]*rhs.a[k][j])%=MOD;
return res;
}
};
Matrix ksm(Matrix x,int v)
{
Matrix res;
memset(res.a,0,sizeof(res.a));
for(int i=0;i<n;i++)res.a[i][i]=1;
while(v)
{
if(v&1)(res=res*x);
x=x*x;
v>>=1;
}
return res;
}
void print(Matrix b)
{
for(int i=0;i<n;i++,puts(""))
for(int j=0;j<n;j++)printf("%d ",b.a[i][j]);
puts("");
}
Matrix b[15];
int main()
{
scanf("%d%d%d%d%d",&n,&m,&s,&t,&k);
for(int i=1;i<=m;i++)
{
int u,v;
scanf("%d%d",&u,&v);
b[0].a[u][v]=1;
b[0].a[v][u]=1;
}
for(int i=1;i<12;i++)b[i]=b[0];
int nf;
scanf("%d",&nf);
for(int i=1;i<=nf;i++)
{
int T;
scanf("%d",&T);
int p[5];
for(int j=0;j<T;j++)
{
scanf("%d",&p[j]);
}
for(int k=0;k<12;k++)
{
for(int kk=0;kk<n;kk++)
b[k].a[kk][p[(k+1)%T]]=0;
}
}
//for(int i=0;i<12;i++)print(b[i]);
Matrix res;
memset(res.a,0,sizeof(res.a));
res.a[0][s]=1;
for(int i=0;i<n;i++)b[12].a[i][i]=1;
for(int i=0;i<12;i++)b[12]=b[12]*b[i];
for(int i=0;i<12;i++)
{
res=ksm(b[12],k/12);
}
for(int i=0;i<k%12;i++)res=res*b[i];
cout<<res.a[s][t];
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 40ms, 内存消耗: 484K, 提交时间: 2020-10-09 22:46:21
#include<cstdio>
using namespace std;
const int mod = 10000, N = 50;
int P[20][5];
struct mat{
int x[N][N], n;
mat(int val, int m){
n = m;
for(int i = 0;i < n;i++){
for(int j = 0;j < n;j++)x[i][j] = 0;
x[i][i] = val;
}
}
mat operator*(const mat &B)const{
mat C(0, n);
for(int i = 0;i < n;i++)
for(int j = 0;j < n;j++)
for(int k = 0;k < n;k++)
C.x[i][j] = (C.x[i][j] + x[i][k] * B.x[k][j] % mod) % mod;
return C;
}
};
mat qp(mat A, int x){
mat B(1, A.n);
for(;x;x >>= 1, A = A * A)if(x & 1)B = B * A;
return B;
}
int main(){
int n, m, x, y, t, i, j, r, k;
scanf("%d%d%d%d%d", &n, &m, &x, &y, &t);
mat G(0, n), A(1, n);
while(m--){
scanf("%d%d", &i, &j);
G.x[i][j] = G.x[j][i] = 1;
}scanf("%d", &m);
for(i = 0;i < m;i++){
scanf("%d", &P[i][0]);
for(j = 1;j <= P[i][0];j++)scanf("%d", &P[i][j]);
}for(i = 1;i <= 24;i++){
A = A * G;
for(j = 0;j < m;j++)
for(k = 0, r = P[j][i % P[j][0] + 1];k < n;k++)
A.x[k][r] = 0;
}A = qp(A, t / 24);
for(i = 1;i <= t % 24;i++){
A = A * G;
for(j = 0;j < m;j++)
for(k = 0, r = P[j][i % P[j][0] + 1];k < n;k++)
A.x[k][r] = 0;
}printf("%d", A.x[x][y]);
return 0;
}