Submission #25072176

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
int MOD = 1000000007;
int PMOD = 1000000007;
inline int exgcd(int a, int md = MOD) {
    a %= md;
    if (a < 0) a += md;
    int b = md, u = 0, v = 1;
    while (a) {
        int t = b / a;
        b -= t * a; swap(a, b);
        u -= t * v; swap(u, v);
    }
    if (u < 0) u += md;
    return u;
}
inline int add(int a, int b) { return a + b >= MOD ? a + b - MOD : a + b; }
inline int sub(int a, int b) { return a - b < 0 ? a - b + MOD : a - b; }
inline int mul(int a, int b) { return 1LL * a * b % MOD; }
inline int powmod(int a, long long b) {
    int res = 1;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <bits/stdc++.h>
using namespace std;
int MOD = 1000000007;
int PMOD = 1000000007;
inline int exgcd(int a, int md = MOD) {
    a %= md;
    if (a < 0) a += md;
    int b = md, u = 0, v = 1;
    while (a) {
        int t = b / a;
        b -= t * a; swap(a, b);
        u -= t * v; swap(u, v);
    }
    if (u < 0) u += md;
    return u;
}
inline int add(int a, int b) { return a + b >= MOD ? a + b - MOD : a + b; }
inline int sub(int a, int b) { return a - b < 0 ? a - b + MOD : a - b; }
inline int mul(int a, int b) { return 1LL * a * b % MOD; }
inline int powmod(int a, long long b) {
    int res = 1;
    while (b > 0) {
        if (b & 1) res = 1LL * res * a % MOD;
        a = 1LL * a * a % MOD;
        b >>= 1;
    }
    return res;
}

constexpr int maximum = 200000;
vector<int> fac(maximum + 1), ifac(maximum + 1), ord(maximum + 1);
vector<long long> pdivs, divs; // 质因子数组 和 质因子的幂次数组

// 求解形如 x = ci (mod mi) 的线性方程组 mi 必须是素数
int CRT(vector<long long> c, vector<long long> m) {
    long long M = m[0], ans = 0;
    for (int i = 1; i < (int)m.size(); ++i) M *= m[i];
    for (int i = 0; i < (int)m.size(); ++i) { // Mi * ti * ci
        long long mi = M / m[i];
        long long ti = exgcd(mi, m[i]); // mi 模 m[i] 的逆元
        ans = (ans + mi * ti % M * c[i] % M) % M;
    }
    ans = (ans + M) % M; // 返回模 M 意义下的唯一解
    return ans;
}

inline int binom(int n, int m) {
    if (n < m || n < 0 || m < 0) return 0;
    int res = mul(fac[n], exgcd(mul(fac[n - m], fac[m])));
    res = mul(res, powmod(PMOD, ord[n] - ord[n - m] - ord[m]));
    return res;
}

void prepareFactorials() {
    ord[0] = ord[1] = 0, fac[0] = fac[1] = 1;
    for (int i = 2; i <= maximum; i++) {
        long long cnt = 0, now = i;
        while (now % MOD == 0) {
            ++cnt;
            now /= MOD;
        }
        ord[i] = ord[i - 1] + cnt; // ord 是MOD这一质因子的出现次数前缀和
        fac[i] = mul(fac[now - 1], now); // fac是去掉了MOD这一质因子后的阶乘
    }
}

void getDivisors(int x) {
    for (int i = 2; 1LL * i * i <= x; i++) {
        int d = 1;
        while (x % i == 0) x /= i, d *= i;
        if (d != 1) {
            pdivs.emplace_back(i);
            divs.emplace_back(d);
        }
    }
    if (x != 1) {
        pdivs.emplace_back(x);
        divs.emplace_back(x);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, t, res = 1;
    cin >> n >> t >> MOD;
    if (MOD == 1) {
        cout << "0\n";
        return 0;
    }
    getDivisors(MOD);
    vector<pair<int, int>> pr(n), rp;
    vector<long long> C;
    for (auto& i : pr) {
        cin >> i.first >> i.second;
        auto [x, y] = i;
        x = abs(x), y = abs(y);
        if ((t - x - y) < 0 || (t - x - y) % 2 != 0) {
            cout << 0 << "\n";
            return 0;
        } else {
            int dx = abs(x + y), dy = abs(y - x);
            rp.push_back({ (t - dx) / 2 + dx, (t - dy) / 2 + dy });
        }
    }
    for (int i = 0; i < (int)pdivs.size(); i++) {
        MOD = divs[i];
        PMOD = pdivs[i];
        prepareFactorials();
        res = 1;
        for (int j = 0; j < rp.size(); j++) {
            auto [x, y] = rp[j];
            int cnt = mul(binom(t, x), binom(t, y));
            res = mul(res, cnt);
        }
        C.push_back(res);
    }
    cout << CRT(C, divs) << "\n";
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:112:27: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::pair<int, int> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  112 |         for (int j = 0; j < rp.size(); j++) {
      |                         ~~^~~~~~~~~~~

Judge Result