1 条题解
-
1
#include<bits/stdc++.h> char buf[100000],*buff = buf + 100000; #define gc ((buff == buf + 100000 ? (fread(buf,1,100000,stdin),buff = buf) : 0),*(buff++)) #define li long long #define pc putchar using namespace std; const int mo = 998244353; inline int read(){ int x = 0,c = gc; while(c < '0' || c > '9') c = gc; while(c >= '0' && c <= '9') x = x * 10 + c - '0',c = gc; return x; } inline void print(int x){ if(x >= 10) print(x / 10); pc(x % 10 + '0'); } int T,k,n[105],m[105]; struct mtx{ li a[205][205]; int x,y; inline li* operator [](int x){return a[x];} inline mtx(){x = y = 0;memset(a,0,sizeof(a));} inline void init(){x = y = 0;memset(a,0,sizeof(a));} }a[105]; inline mtx operator * (mtx x,mtx y){ assert(x.y == y.x); mtx as;as.x = x.x;as.y = y.y; li tmp; register int i,j,k; for(i = 1;i <= x.x;++i) for(k = 1;k <= x.y;++k){ tmp = x[i][k]; for(j = 1;j <= y.y;++j) as[i][j] += tmp * y[k][j]; } for(i = 1;i <= x.x;++i) for(j = 1;j <= y.y;++j) if(as[i][j] > 4e16l) as[i][j] %= mo; return as; } inline li ksm(li q,li w){ li as = 1; while(w){ if(w & 1) as = as * q % mo; q = q * q % mo; w >>= 1; } return as; } inline li det(mtx x){ assert(x.x == x.y); int n = x.x,i,j,k; for(i = 1;i <= n;++i) for(j = 1;j <= n;++j) x[i][j] %= mo; li tmp = 1; for(i = 1;i <= n;++i){ if(!x[i][i]){ for(j = i + 1;j <= n;++j) if(x[j][i]){ tmp = (mo - tmp) % mo; for(k = i;k <= n;++k) swap(x[i][k],x[j][k]); break; } } if(!x[i][i]) return 0; (tmp *= x[i][i]) %= mo; li tp = ksm(x[i][i],mo - 2); for(j = i;j <= n;++j) (x[i][j] *= tp) %= mo; for(j = i + 1;j <= n;++j){ tp = x[j][i]; for(k = i + 1;k <= n;++k) (x[j][k] += mo - x[i][k] * tp % mo) %= mo; x[j][i] = 0; } } return tmp; } int main(){ int i,j,u,v; T = read(); while(T--){ k = read(); for(i = 1;i < k;++i) a[i].init(); for(i = 1;i <= k;++i) n[i] = read(),a[i].x = a[i - 1].y = n[i]; for(i = 1;i < k;++i) m[i] = read(); for(i = 1;i < k;++i){ for(j = 1;j <= m[i];++j){ u = read();v = read(); a[i][u][v] = 1; } } for(i = 2;i < k;++i) a[1] = a[1] * a[i]; print(det(a[1]));pc('\n'); } return 0; }
- 1
信息
- ID
- 6624
- 时间
- 1000ms
- 内存
- 1024MiB
- 难度
- 6
- 标签
- 递交数
- 2
- 已通过
- 2
- 上传者