QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#854254#9735. Japanese Bandsucup-team2796#WA 74ms11576kbC++177.4kb2025-01-11 22:59:482025-01-11 22:59:52

Judging History

你现在查看的是最新测评结果

  • [2025-01-18 23:34:05]
  • hack成功，自动添加数据
  • (/hack/1459)
  • [2025-01-11 22:59:52]
  • 评测
  • 测评结果：WA
  • 用时：74ms
  • 内存：11576kb
查看
  • [2025-01-11 22:59:48]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rrep(i, a, b) for (int i = (int)(b)-1; i >= (int)(a); i--)
#define ALL(v) (v).begin(), (v).end()
#define UNIQUE(v) sort(ALL(v)), (v).erase(unique(ALL(v)), (v).end())
#define SZ(v) (int)v.size()
#define MIN(v) *min_element(ALL(v))
#define MAX(v) *max_element(ALL(v))
#define LB(v, x) int(lower_bound(ALL(v), (x)) - (v).begin())
#define UB(v, x) int(upper_bound(ALL(v), (x)) - (v).begin())

using uint = unsigned int;
using ll = long long int;
using ull = unsigned long long;
using i128 = __int128_t;
using u128 = __uint128_t;
const int inf = 0x3fffffff;
const ll INF = 0x1fffffffffffffff;

template <typename T> inline bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <typename T> inline bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return 1;
    }
    return 0;
}
template <typename T, typename U> T ceil(T x, U y) {
    assert(y != 0);
    if (y < 0)
        x = -x, y = -y;
    return (x > 0 ? (x + y - 1) / y : x / y);
}
template <typename T, typename U> T floor(T x, U y) {
    assert(y != 0);
    if (y < 0)
        x = -x, y = -y;
    return (x > 0 ? x / y : (x - y + 1) / y);
}
template <typename T> int popcnt(T x) {
    return __builtin_popcountll(x);
}
template <typename T> int topbit(T x) {
    return (x == 0 ? -1 : 63 - __builtin_clzll(x));
}
template <typename T> int lowbit(T x) {
    return (x == 0 ? -1 : __builtin_ctzll(x));
}

template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
    os << "P(" << p.first << ", " << p.second << ")";
    return os;
}
template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec) {
    os << "{";
    for (int i = 0; i < vec.size(); i++) {
        os << vec[i] << (i + 1 == vec.size() ? "" : ", ");
    }
    os << "}";
    return os;
}
template <typename T, typename U>
ostream &operator<<(ostream &os, const map<T, U> &map_var) {
    os << "{";
    for (auto itr = map_var.begin(); itr != map_var.end(); itr++) {
        os << "(" << itr->first << ", " << itr->second << ")";
        itr++;
        if (itr != map_var.end())
            os << ", ";
        itr--;
    }
    os << "}";
    return os;
}
template <typename T> ostream &operator<<(ostream &os, const set<T> &set_var) {
    os << "{";
    for (auto itr = set_var.begin(); itr != set_var.end(); itr++) {
        os << *itr;
        ++itr;
        if (itr != set_var.end())
            os << ", ";
        itr--;
    }
    os << "}";
    return os;
}
#ifdef LOCAL
#define show(...) _show(0, #__VA_ARGS__, __VA_ARGS__)
#else
#define show(...) true
#endif
template <typename T> void _show(int i, T name) {
    cerr << '\n';
}
template <typename T1, typename T2, typename... T3>
void _show(int i, const T1 &a, const T2 &b, const T3 &...c) {
    for (; a[i] != ',' && a[i] != '\0'; i++)
        cerr << a[i];
    cerr << ":" << b << " ";
    _show(i + 1, a, c...);
}

/**
 * @brief template
 */

template <unsigned mod = 1000000007> struct fp {
    unsigned v;
    static constexpr int get_mod() {
        return mod;
    }
    constexpr unsigned inv() const {
        assert(v != 0);
        int x = v, y = mod, p = 1, q = 0, t = 0, tmp = 0;
        while (y > 0) {
            t = x / y;
            x -= t * y, p -= t * q;
            tmp = x, x = y, y = tmp;
            tmp = p, p = q, q = tmp;
        }
        if (p < 0)
            p += mod;
        return p;
    }
    constexpr fp(ll x = 0) : v(x >= 0 ? x % mod : (mod - (-x) % mod) % mod) {}
    fp operator-() const {
        return fp() - *this;
    }
    fp pow(ull t) {
        fp res = 1, b = *this;
        while (t) {
            if (t & 1)
                res *= b;
            b *= b;
            t >>= 1;
        }
        return res;
    }
    fp &operator+=(const fp &x) {
        if ((v += x.v) >= mod)
            v -= mod;
        return *this;
    }
    fp &operator-=(const fp &x) {
        if ((v += mod - x.v) >= mod)
            v -= mod;
        return *this;
    }
    fp &operator*=(const fp &x) {
        v = ull(v) * x.v % mod;
        return *this;
    }
    fp &operator/=(const fp &x) {
        v = ull(v) * x.inv() % mod;
        return *this;
    }
    fp operator+(const fp &x) const {
        return fp(*this) += x;
    }
    fp operator-(const fp &x) const {
        return fp(*this) -= x;
    }
    fp operator*(const fp &x) const {
        return fp(*this) *= x;
    }
    fp operator/(const fp &x) const {
        return fp(*this) /= x;
    }
    bool operator==(const fp &x) const {
        return v == x.v;
    }
    bool operator!=(const fp &x) const {
        return v != x.v;
    }
    friend istream &operator>>(istream &is, fp &x) {
        return is >> x.v;
    }
    friend ostream &operator<<(ostream &os, const fp &x) {
        return os << x.v;
    }
};

// template <unsigned mod> void rd(fp<mod> &x) {
//     fastio::rd(x.v);
// }
// template <unsigned mod> void wt(fp<mod> x) {
//     fastio::wt(x.v);
// }

template <typename T> T Inv(ll n) {
    static const int md = T::get_mod();
    static vector<T> buf({0, 1});
    assert(n > 0);
    n %= md;
    while (SZ(buf) <= n) {
        int k = SZ(buf), q = (md + k - 1) / k;
        buf.push_back(buf[k * q - md] * q);
    }
    return buf[n];
}

template <typename T> T Fact(ll n, bool inv = 0) {
    static const int md = T::get_mod();
    static vector<T> buf({1, 1}), ibuf({1, 1});
    assert(n >= 0 and n < md);
    while (SZ(buf) <= n) {
        buf.push_back(buf.back() * SZ(buf));
        ibuf.push_back(ibuf.back() * Inv<T>(SZ(ibuf)));
    }
    return inv ? ibuf[n] : buf[n];
}

template <typename T> T nPr(int n, int r, bool inv = 0) {
    if (n < 0 || n < r || r < 0)
        return 0;
    return Fact<T>(n, inv) * Fact<T>(n - r, inv ^ 1);
}
template <typename T> T nCr(int n, int r, bool inv = 0) {
    if (n < 0 || n < r || r < 0)
        return 0;
    return Fact<T>(n, inv) * Fact<T>(r, inv ^ 1) * Fact<T>(n - r, inv ^ 1);
}
template <typename T> T nHr(int n, int r, bool inv = 0) {
    return nCr<T>(n + r - 1, r, inv);
}

/**
 * @brief Modint
 */

using Fp = fp<>;

int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
int _;
cin >> _;
while(_--) {
    ll N1, N2, M, K;
    cin >> N1 >> N2 >> M >> K;
    vector<int> A(K), B(K);
    rep(i,0,K) cin >> A[i] >> B[i], A[i]--, B[i]--;
    ll hoge = 0, hissu = 0;
    rep(i,0,K) hoge |= (1 << A[i]), hoge |= (1 << B[i]);
    rep(i,0,K) if (A[i] == B[i]) hissu |= (1<<A[i]);
    vector<int> NG(1<<M, true);
    rep(i,0,K) NG[(1<<A[i]) | (1<<B[i])] = false;
    rep(i,0,M) {
        rep(j,0,1<<M) if (!NG[j]) NG[j | (1<<i)] = false;
    }
    vector<int> OK = NG;
    reverse(ALL(OK));
    Fp ANS = 0;
    rep(mask,0,1<<M) {
        if (!OK[mask]) continue;
        int aikata = (((1<<M) - 1 - mask) & hoge) | hissu;
        int popmask = popcnt(mask), popaik = popcnt(aikata);
        if (popmask-1 < 0 || popmask > N1) continue;
        if (M-1 < 0 || N2-popaik < 0) continue;
        Fp Cur = 1, Rev = 1;
        rep(i,0,popmask-1) Cur *= (N1-1-i), Rev *= (i+1);
        rep(i,0,M-1) Cur *= (N2-popaik+M-1-i), Rev *= (i+1);
        Cur /= Rev;
        ANS += Cur;
    }
    cout << ANS << endl;
}
}
源文件, 语言: C++17

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3540kb

input:

3
2 3 3 3
2 3
1 1
2 3
2 2 2 1
1 1
1 1 10 2
1 2
1 3

output:

6
4
0

result:

ok 3 lines

Test #2:

score: -100
Wrong Answer
time: 74ms
memory: 11576kb

input:

500
481199252 336470888 8 58
4 7
7 6
4 7
2 6
2 6
2 7
8 3
8 7
8 1
2 6
2 6
1 2
1 5
3 1
6 4
2 4
4 7
2 6
2 3
7 1
4 4
5 1
2 7
6 7
8 1
8 7
5 6
4 2
4 2
8 5
5 4
6 8
5 6
3 8
1 7
1 6
7 1
5 6
6 3
1 1
2 7
3 3
1 5
5 5
8 7
3 4
6 3
8 8
7 4
1 6
2 1
8 7
4 5
2 7
3 5
2 6
4 5
4 3
2 6 2 2
2 1
1 1
500330171 987581927 10 ...

output:

776415478
11
64009214
672439243
200116643
1
271862120
405695354
1
269113412
515563632
1
0
598319348
376698469
54376973
13643616
544511885
423174656
333489126
0
487514263
448576974
8376584
16
540403419
933415828
808801372
1
612901047
526166128
644198558
1260
683254244
1
928786226
465503749
1
1
577162...

result:

wrong answer 1st lines differ - expected: '724920553', found: '776415478'
English 繁體中文 简体中文

服务器时间: 2025-02-01 17:58:10 | 开源项目