QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#163714 | #6865. foreverlasting and fried-chicken | jrjyy# | WA | 75ms | 3564kb | C++20 | 4.0kb | 2023-09-04 14:28:11 | 2023-09-04 14:28:12 |
Judging History
answer
#include <bits/stdc++.h>
using i64 = long long;
template <typename T> constexpr T power(T a, i64 b) {
T c{1}; for (; b; b /= 2, a *= a) if (b & 1) c *= a;
return c;
}
template <int P> struct MInt {
int x;
constexpr MInt() : x{} {}
constexpr MInt(i64 x_) : x{norm(x_ % getMod())} {}
static int Mod;
constexpr static int getMod() { return P > 0 ? P : Mod; }
constexpr static void setMod(int Mod_) { Mod = Mod_; }
constexpr int up(int x) const {
if (x < 0) x += getMod();
return x;
}
constexpr int down(int x) const {
if (x >= getMod()) x -= getMod();
return x;
}
constexpr int norm(int x) const {
return up(down(x));
}
constexpr int val() const { return x; }
explicit constexpr operator int() const { return x; }
constexpr MInt operator-() const {
MInt res; res.x = norm(getMod() - x); return res;
}
constexpr MInt inv() const {
assert(x != 0);
return power(*this, getMod() - 2);
}
constexpr MInt &operator+=(MInt rhs) & { return x = down(x + rhs.x), *this; }
constexpr MInt &operator-=(MInt rhs) & { return x = up(x - rhs.x), *this; }
constexpr MInt &operator*=(MInt rhs) & { return x = 1ll * x * rhs.x % getMod(), *this; }
constexpr MInt &operator/=(MInt rhs) & { return *this *= rhs.inv(); }
friend constexpr MInt operator+(MInt lhs, MInt rhs) { return lhs += rhs; }
friend constexpr MInt operator-(MInt lhs, MInt rhs) { return lhs -= rhs; }
friend constexpr MInt operator*(MInt lhs, MInt rhs) { return lhs *= rhs; }
friend constexpr MInt operator/(MInt lhs, MInt rhs) { return lhs /= rhs; }
friend constexpr bool operator==(MInt lhs, MInt rhs) { return lhs.val() == rhs.val(); }
friend constexpr bool operator!=(MInt lhs, MInt rhs) { return lhs.val() != rhs.val(); }
friend constexpr std::istream &operator>>(std::istream &is, MInt &a) {
i64 x = 0; is >> x, a = MInt(x); return is;
}
friend constexpr std::ostream &operator<<(std::ostream &os, const MInt &a) {
return os << a.val();
}
};
template <int P> int MInt<P>::Mod = P;
template <> int MInt<0>::Mod = 1;
template <int V, int P> constexpr MInt<P> CInv = MInt<P>(V).inv();
constexpr int P = 1000000007;
using Z = MInt<P>;
struct Comb {
int n; std::vector<Z> fac_, ifac_, inv_;
Comb() : n(0), fac_{1}, ifac_{1}, inv_{0} {}
Comb(int n) : Comb() { init(n); }
void init(int m) {
if (m <= n) return;
fac_.resize(m + 1), ifac_.resize(m + 1), inv_.resize(m + 1);
for (int i = n + 1; i <= m; ++i) fac_[i] = fac_[i - 1] * i;
ifac_[m] = fac_[m].inv();
for (int i = m; i > n + 1; --i) ifac_[i - 1] = ifac_[i] * i;
for (int i = m; i > n; --i) inv_[i] = ifac_[i] * fac_[i - 1];
n = m;
}
Z fac(int m) {
if (n < m) init(2 * m);
return fac_[m];
}
Z ifac(int m) {
if (n < m) init(2 * m);
return ifac_[m];
}
Z inv(int m) {
if (n < m) init(2 * m);
return inv_[m];
}
Z binom(int n, int m) {
return n < m || m < 0 ? 0 : fac(n) * ifac(m) * ifac(n - m);
}
} comb;
constexpr int N = 1000;
void solve() {
int n, m;
std::cin >> n >> m;
std::vector<std::bitset<N>> adj(n);
std::vector<int> f(n);
for (int i = 0; i < m; ++i) {
int u, v;
std::cin >> u >> v;
--u, --v;
adj[u][v] = adj[v][u] = 1;
f[u] += 1, f[v] += 1;
}
Z ans = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (i != j) {
int cnt = (adj[i] & adj[j]).count();
ans += comb.binom(cnt, 4) * comb.binom(f[i] - 4, 2);
}
}
}
std::cout << ans << '\n';
}
int main() {
std::cin.tie(nullptr)->sync_with_stdio(false);
int t;
std::cin >> t;
while (t--) {
solve();
}
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 75ms
memory: 3564kb
input:
9 8 10 1 2 1 3 1 4 1 5 1 6 1 7 8 4 8 5 8 6 8 7 10 12 1 2 1 3 1 4 1 5 1 6 1 7 8 4 8 5 8 6 8 7 8 9 8 10 11 13 1 2 1 3 1 4 1 5 1 6 1 7 8 4 8 5 8 6 8 7 8 9 8 10 1 11 11 14 1 2 1 3 1 4 1 5 1 6 1 7 8 4 8 5 8 6 8 7 8 9 8 10 1 11 1 8 10 45 5 10 2 9 5 8 3 10 2 10 4 9 4 3 4 2 5 6 7 1 10 6 10 7 6 1 8 3 5 1 7 5...
output:
1 2 4 9 63000 0 624414727 928162958 4088223
result:
wrong answer 4th lines differ - expected: '4', found: '9'