比赛 2024暑假C班集训D 评测结果 AAAAAAAAAA
题目名称 沼泽鳄鱼 最终得分 100
用户昵称 darkMoon 运行时间 0.263 s
代码语言 C++ 内存使用 4.16 MiB
提交时间 2024-07-13 09:55:02
显示代码纯文本
#include<bits/stdc++.h>
#define int long long
using namespace std;
// #define fin cin
// #define fout cout
ifstream fin("swamp.in");
ofstream fout("swamp.out");
auto mread = [](){
    int x;
    fin >> x;
    return x;
};
const int N = 55, MOD = 10000;
int n = mread(), m = mread(), s = mread() + 1, t = mread() + 1, k = mread(), a[N][N], nf, b[N][N];
struct node{
    int a[N][N];
    node(){
        for(int i = 1; i <= n; i ++){
            for(int j = 1; j <= n; j ++){
                a[i][j] = 0;
            }
        }
    }
    friend node operator * (node a, node b){
        node ans;
        for(int i = 1; i <= n; i ++){
            for(int j = 1; j <= n; j ++){
                for(int k = 1; k <= n; k ++){
                    (ans.a[i][j] += a.a[i][k] * b.a[k][j] % MOD) %= MOD;
                }
            }
        }
        return ans;
    }
};
node ksm(node x, int k){
    node now = x, ans;
    for(int i = 1; i <= n; i ++){
        ans.a[i][i] = 1;
    }
    while(k){
        if(k & 1){
            ans = ans * now;
        }
        now = now * now;
        k >>= 1;
    }
    return ans;
}
signed main(){
    for(int i = 1, x, y; i <= m; i ++){
        x = mread() + 1, y = mread() + 1;
        a[x][y] ++;
        a[y][x] ++;
    }
    nf = mread();
    for(int i = 1; i <= nf; i ++){
        b[i][0] = mread();
        for(int j = 1; j <= b[i][0]; j ++){
            b[i][j] = mread() + 1;
        }
        for(int j = 1; j <= 12; j ++){
            int tmp = (j - 1) % b[i][0] + 1;
            b[i][j] = b[i][tmp];
        }
    }
    node c[20];
    for(int i = 1; i <= 11; i ++){
        for(int j = 1; j <= n; j ++){
            for(int k = 1; k <= n; k ++){
                int e = 1;
                for(int l = 1; l <= nf; l ++){
                    if(k == b[l][i + 1]){
                        e = 0;
                        break;
                    }
                }
                if(e){
                    c[i].a[j][k] = a[j][k];
                }
            }
        }
        // printf("--- %lld\n", i);
        // for(int j = 1; j <= n; j ++){
        //     for(int k = 1; k <= n; k ++){
        //         printf("%lld ", c[i].a[j][k]);
        //     }
        //     printf("\n");
        // }
    }
    for(int j = 1; j <= n; j ++){
        for(int k = 1; k <= n; k ++){
            int e = 1;
            for(int l = 1; l <= nf; l ++){
                if(k == b[l][1]){
                    e = 0;
                    break;
                }
            }
            if(e){
                c[12].a[j][k] = a[j][k];
            }
        }
    }
    node tmp = c[1];
    for(int i = 2; i <= 12; i ++){
        tmp = tmp * c[i];
    }
    node ans = ksm(tmp, k / 12);
    for(int i = 1; i <= k % 12; i ++){
        ans = ans * c[i];
        // printf("*** %lld\n", i);
        // for(int j = 1; j <= n; j ++){
        //     for(int k = 1; k <= n; k ++){
        //         printf("%lld ", ans.a[j][k]);
        //     }
        //     printf("\n");
        // }
    }
    fout << ans.a[s][t];
    return 0;
}