結果
| 問題 |
No.2435 Order All Company
|
| コンテスト | |
| ユーザー |
 Kude
|
| 提出日時 | 2023-08-18 23:40:23 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 38 ms / 2,000 ms |
| コード長 | 5,932 bytes |
| コンパイル時間 | 2,038 ms |
| コンパイル使用メモリ | 218,948 KB |
| 最終ジャッジ日時 | 2025-02-16 10:59:42 |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 36 |
ソースコード
#include<bits/stdc++.h>
namespace {
#pragma GCC diagnostic ignored "-Wunused-function"
#include<atcoder/all>
#pragma GCC diagnostic warning "-Wunused-function"
using namespace std;
using namespace atcoder;
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(i,n) for(int i = (int)(n) - 1; i >= 0; i--)
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
template<class T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; }
template<class T> bool chmin(T& a, const T& b) { if (b < a) { a = b; return true; } else return false; }
using ll = long long;
using P = pair<int,int>;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<ll>;
using VVL = vector<VL>;
using mint = modint998244353;
mint L[5][50][50];
template<class T, int N>
struct Mat: std::array<std::array<T, N>, N> {
friend Mat<T, N> operator*(const Mat& A, const Mat& B) {
Mat<T, N> C = {};
for(int i = 0; i < N; i++) {
for(int k = 0; k < N; k++) {
for(int j = 0; j < N; j++) {
C[i][j] += A[i][k] * B[k][j];
}
}
}
return C;
}
friend std::array<T, N> operator*(const Mat& A, const std::array<T, N>& v) {
std::array<T, N> x = {};
for(int i = 0; i < N; i++) for(int j = 0; j < N; j++) x[i] += A[i][j] * v[j];
return x;
}
friend Mat<T, N> operator+(const Mat& A, const Mat& B) {
Mat<T, N> C;
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
C[i][j] = A[i][j] + B[i][j];
}
}
return C;
}
Mat<T, N>& operator*=(const Mat& A) { return *this = *this * A; }
Mat<T, N>& operator+=(const Mat& A) {
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
(*this)[i][j] += A[i][j];
}
}
}
static Mat<T, N> I() {
Mat<T, N> X = {};
for(int i = 0; i < N; i++) X[i][i] = 1;
return X;
}
Mat<T, N> pow(long long k) const {
assert(k >= 0);
auto X = *this;
auto Y = I();
while(k) {
if (k & 1) Y *= X;
k >>= 1;
if (k) X *= X;
}
return Y;
}
Mat<T, N> inv() const {
auto X = *this;
auto Y = I();
for(int p = 0; p < N; p++) {
bool ok = false;
for(int i = p; i < N; i++) {
if (X[i][p] != T()) {
ok = true;
if (i != p) {
// std::swap(X[i], X[p]);
for(int j = p; j < N; j++) std::swap(X[i][j], X[p][j]);
std::swap(Y[i], Y[p]);
}
break;
}
}
assert(ok);
T c = 1 / X[p][p];
for(int j = p; j < N; j++) X[p][j] *= c;
for(int j = 0; j < N; j++) Y[p][j] *= c;
for(int i = 0; i < N; i++) if (i != p) {
T c = X[i][p];
for(int j = p; j < N; j++) X[i][j] -= c * X[p][j];
for(int j = 0; j < N; j++) Y[i][j] -= c * Y[p][j];
}
}
return Y;
}
T det() const {
if (N == 0) return T();
auto X = *this;
bool flag = false;
T res = 1;
bool ok = false;
for(int p = 0; p < N; p++) {
for(int i = p; i < N; i++) {
if (X[i][p] != T()) {
ok = true;
if (i != p) {
flag = !flag;
for(int j = p; j < N; j++) std::swap(X[i][j], X[p][j]);
}
break;
}
}
if (!ok) return T();
// T = modint
for(int i = p + 1; i < N; i++) {
T c0 = 1, c1 = 0, d0 = 0, d1 = 1;
int a = X[p][p].val(), b = X[i][p].val();
while(true) {
if (b == 0) {
break;
}
int q = a / b;
a -= q * b;
c0 -= q * d0;
c1 -= q * d1;
if (a == 0) {
flag = !flag;
for(int j = p; j < N; j++) std::swap(X[i][j], X[p][j]);
std::swap(c0, d1);
std::swap(c1, d0);
break;
}
q = b / a;
b -= q * a;
d0 -= q * c0;
d1 -= q * c1;
}
for(int j = p; j < N; j++) {
T a = X[p][j], b = X[i][j];
T x = c0 * a + c1 * b, y = d0 * a + d1 * b;
X[p][j] = x;
X[i][j] = y;
}
}
res *= X[p][p];
}
if (flag) res = -res;
return res;
}
friend std::ostream& operator<<(std::ostream& os, const Mat<T, N>& A) {
for(int i = 0; i < N; i++) for(int j = 0; j < N; j++) os << A[i][j] << " \n"[j + 1 == N];
return os;
}
};
using M = Mat<mint, 50>;
} int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, k;
cin >> n >> k;
rep(i, k) {
int t;
cin >> t;
rep(_, t) {
int a, b;
cin >> a >> b;
a--, b--;
L[i][a][b]--;
L[i][b][a]--;
L[i][a][a]++;
L[i][b][b]++;
}
}
mint cnt[32];
rep(s, 1 << k) {
M a;
for(int i = n - 1; i < 50; i++) a[i][i] = 1;
rep(i, k) if (s >> i & 1) {
rep(j, n - 1) rep(k, n - 1) a[j][k] += L[i][j][k];
}
cnt[s] = a.det();
// cout << cnt[s].val() << '\n';
}
rep(i, k) rep(s, 1 << k) if (s >> i & 1) {
cnt[s] -= cnt[s ^ (1 << i)];
}
cout << cnt[(1 << k) - 1].val() << '\n';
}