結果

問題 No.2985 May Count Induced C4 Subgraphs
ユーザー KudeKude
提出日時 2024-12-12 10:58:45
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 5,264 bytes
コンパイル時間 4,468 ms
コンパイル使用メモリ 305,072 KB
実行使用メモリ 25,216 KB
最終ジャッジ日時 2024-12-12 10:59:00
合計ジャッジ時間 13,476 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 15 ms
11,212 KB
testcase_01 AC 14 ms
11,264 KB
testcase_02 WA -
testcase_03 AC 13 ms
11,264 KB
testcase_04 AC 14 ms
11,208 KB
testcase_05 AC 14 ms
11,340 KB
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;


constexpr int FACT_SIZE = 1000000;
mint Fact[FACT_SIZE + 1];
mint iFact[FACT_SIZE + 1];
const auto fact_init = [] {
    Fact[0] = mint::raw(1);
    for(int i = 1; i <= FACT_SIZE; ++i) {
        Fact[i] = Fact[i-1] * i;
    }
    iFact[FACT_SIZE] = Fact[FACT_SIZE].inv();
    for(int i = FACT_SIZE; i; --i) {
        iFact[i-1] = iFact[i] * i;
    }
    return false;
}();
mint comb(int n, int k) {
    if (k == 0) return mint::raw(1);
    if (n < 0) return mint();
    assert(n >= 0 && k >= 0);
    if (k > n) return mint::raw(0);
    return Fact[n] * iFact[n - k] * iFact[k];
}

constexpr int M = 200010;
bool used[M];
int cnt[M];

int n, m;
VVI to;
vector<int> ord, pos;

mint c0() {
  return comb(n, 4);
}
mint c1() {
  return m * comb(n - 2, 2);
}
mint c2() {
  mint res;
  rep(i, n) res += comb(to[i].size(), 2);
  res *= n - 3;
  return res;
}
mint c3() {
  mint res = comb(m, 2);
  rep(i, n) res -= comb(to[i].size(), 2);
  return res;
}
mint c4() {
  mint res;
  rep(i, n) res += comb(to[i].size(), 3);
  return res;
}
mint c7() {
  mint res;
  vector<vector<int>::iterator> ends(n);
  rep(u, n) ends[u] = to[u].end();
  rrep(i, n) {
    int u = ord[i];
    for (auto it = to[u].begin(); it != ends[u]; it++) {
      int v = *it;
      ends[v]--;
      for (auto it = to[v].begin(); it != ends[v]; it++) res += mint::raw(cnt[*it]++);
    }
    for (auto it = to[u].begin(); it != ends[u]; it++) {
      int v = *it;
      for (auto it = to[v].begin(); it != ends[v]; it++) cnt[*it] = 0;
    }
  }
  return res;
}
array<mint, 4> c5c6c8c9() {
  mint c5, c6, c8, c9;
  rep(u, n) {
    for (int w : to[u]) used[w] = true, cnt[w] = ssize(to[u]) - 2;
    for (int v : to[u]) if (pos[v] < pos[u]) {
      int c = 0;
      int cntsm = 0;
      for (int w : to[v]) c += used[w], cntsm += cnt[w];
      c5 += mint(to[u].size() - 1) * mint(to[v].size() - 1);
      c6 += c;
      c8 += cntsm;
      c9 += comb(c, 2);
    }
    for (int w : to[u]) used[w] = false, cnt[w] = 0;
  }
  c6 /= 3;
  c5 -= 3 * c6;
  c6 *= n - 3;
  return {c5, c6, c8, c9};
}

vector<mint> gauss_elim(vector<vector<mint>> d) {
  assert(d.size() >= 1 && ssize(d[0]) >= 1);
  int n = d.size(), m = ssize(d[0]);
  int i0 = 0;
  rep(j, m) {
    int i1 = -1;
    for (int i = i0; i < n; i++) if (d[i][j].val()) {
      i1 = i;
      break;
    }
    if (i1 == -1) continue;
    if (j == m - 1) return {};
    swap(d[i0], d[i1]);
    mint inv = d[i0][j].inv();
    for (int jt = j; jt < m; jt++) d[i0][jt] *= inv;
    for (int i = i1 + 1; i < n; i++) {
      mint coeff = d[i][j];
      for (int jt = j; jt < m; jt++) d[i][jt] -= coeff * d[i0][jt];
    }
    i0++;
  }
  // for (int i = i0; i < n; i++) rep(j, m) assert(!d[i][j].val());
  vector<mint> ans(m);
  ans[m - 1] = 1;
  int j_last = m;
  rrep(i, i0) {
    int j = 0;
    while (j < m && !d[i][j].val()) j++;
    assert(j < j_last && d[i][j].val() == 1);
    j_last = j;
    for (int jt = j + 1; jt < m; jt++) ans[j] -= d[i][jt] * ans[jt];
  }
  ans.pop_back();
  return ans;
}


} int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  to.resize(n);
  cin >> n >> m;
  to.resize(n);
  rep(_, m) {
    int u, v;
    cin >> u >> v;
    u--, v--;
    to[u].emplace_back(v);
    to[v].emplace_back(u);
  }
  ord.resize(n), pos.resize(n);
  iota(ord.begin(), ord.end(), 0);
  ranges::sort(ord, {}, [&](int v) { return to[v].size(); });
  rep(i, n) pos[ord[i]] = i;
  rep(u, n) ranges::sort(to[u], {}, [&](int v) { return pos[v]; });
  mint A[10][11]{
    {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
    {0, 1, 2, 2, 3, 3, 3, 4, 4, 5, 6},
    {0, 0, 1, 0, 3, 2, 3, 4, 5, 8, 12},
    {0, 0, 0, 1, 0, 1, 0, 2, 1, 2, 3},
    {0, 0, 0, 0, 1, 0, 0, 0, 1, 2, 4},
    {0, 0, 0, 0, 0, 1, 0, 4, 2, 6, 12},
    {0, 0, 0, 0, 0, 0, 1, 0, 1, 2, 4},
    {0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 3},
    {0, 0, 0, 0, 0, 0, 0, 0, 1, 4, 12},
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 6}
  };
  vector B(10, vector<mint>(11));
  rep(i, 10) rep(j, 11) if (j != 7) B[j - (j > 7)][i] = A[i][j];
  B[0][10] = -1;
  auto v = gauss_elim(B);
  mint coeff[11];
  rep(i, 10) rep(j, 11) coeff[j] += v[i] * A[i][j];
  rep(j, 11) assert(j == 0 ? coeff[j] == 1 : j == 7 || coeff[j] == 0);
  mint c[10];
  c[0] = c0(), c[1] = c1(), c[2] = c2(), c[3] = c3(), c[4] = c4(), c[7] = c7();
  auto c5689 = c5c6c8c9();
  for (int i = 0; int idx : {5, 6, 8, 9}) c[idx] = c5689[i++];
  mint ans;
  rep(i, 10) ans += v[i] * c[i];
  // rep(i, 10) cout << c[i].val() << " \n"[i + 1 == 10];
  cout << coeff[7].val() << ' ' << ans.val() << '\n';
}
0