結果

問題 No.215 素数サイコロと合成数サイコロ (3-Hard)
ユーザー pekempeypekempey
提出日時 2016-11-02 05:17:47
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 3,028 ms / 4,000 ms
コード長 6,156 bytes
コンパイル時間 4,224 ms
コンパイル使用メモリ 225,968 KB
実行使用メモリ 24,064 KB
最終ジャッジ日時 2024-11-25 01:23:27
合計ジャッジ時間 13,479 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2,858 ms
24,064 KB
testcase_01 AC 3,028 ms
23,984 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC optimize ("O3")
#pragma GCC target ("avx")
#include <bits/stdc++.h>
typedef __int128_t int128;

// worst: 1152921504606839475 300 300 => 610505353
//        1000000000000000000 300 300 => 817328043

class Karatsuba128 {
private:
    int mod;

public:
    Karatsuba128(int mod) : mod(mod) {}

    std::vector<int> mul(std::vector<int> a, std::vector<int> b, int pmod = -1) {
        if (pmod == -1) pmod = a.size() + b.size() - 1;
        else {
            if (a.size() > pmod) a.resize(pmod);
            if (b.size() > pmod) b.resize(pmod);
        }
        int s = std::max<int>(a.size(), b.size());
        int t = 1;
        while (t < s) t *= 2;
        std::vector<int64_t> A(t), B(t), C(t * 4);
        std::vector<int128> res(t * 4);
        for (int i = 0; i < a.size(); i++) A[i] = a[i];
        for (int i = 0; i < b.size(); i++) B[i] = b[i];
        mul(A.data(), B.data(), C.data(), t, res.data());
        std::vector<int> c(pmod);
        for (int i = 0; i < std::min<int>(pmod, C.size()); i++) {
            c[i] = res[i] % mod;
            if (c[i] < 0) c[i] += mod;
        }
        return c;
    }

private:
    void mul(int64_t a[], int64_t b[], int64_t c[], int n, int128 res[]) {
        if (n <= 8) {
            memset(res, 0, sizeof(res[0]) * n * 2);
            for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
                res[i + j] += int128(a[i]) * b[j];
            }
            return;
        }
        int64_t *a0 = a, *a1 = a + n / 2;
        int64_t *b0 = b, *b1 = b + n / 2;
        int64_t *c0 = c, *c1 = c + n / 2;
        int128 *x0 = res, *x1 = res + n, *x2 = res + n * 2;
        for (int i = 0; i < n / 2; i++) {
            c0[i] = a0[i] + a1[i];
            c1[i] = b0[i] + b1[i];
        }
        mul(a0, b0, c + n * 2, n / 2, x0);
        mul(a1, b1, c + n * 2, n / 2, x1);
        mul(c0, c1, c + n * 2, n / 2, x2);
        for (int i = 0; i < n; i++) x2[i] -= x0[i] + x1[i];
        for (int i = 0; i < n; i++) res[i + n / 2] += x2[i];
    }
};

class AnyModPolynomial {
private:
    int mod;
    Karatsuba128 kara128;

    std::vector<int> t;

public:
    AnyModPolynomial(int mod) : mod(mod), kara128(mod) {}

    std::vector<int> mul(const std::vector<int> &a, const std::vector<int> &b) {
        return kara128.mul(a, b);
    }

    std::vector<int> add(const std::vector<int> &a, const std::vector<int> &b) {
        std::vector<int> res(std::max<int>(a.size(), b.size()));
        for (int i = 0; i < res.size(); i++) {
            res[i] = add(i < a.size() ? a[i] : 0, i < b.size() ? b[i] : 0);
        }
        return res;
    }

    std::vector<int> sub(const std::vector<int> &a, const std::vector<int> &b) {
        std::vector<int> res(std::max<int>(a.size(), b.size()));
        for (int i = 0; i < res.size(); i++) {
            res[i] = add(i < a.size() ? a[i] : 0, i < b.size() ? (mod - b[i]) : 0);
        }
        return res;
    }

    std::vector<int> quot(std::vector<int> a, std::vector<int> b) {
        if (a.size() < b.size()) return{ 0 };
        while (b.back() == 0) b.pop_back();
        int s = a.size() - b.size() + 1;
        while (!is_pow2(a.size() - b.size() + 1)) a.push_back(0);
        int n = a.size() - b.size() + 1;
        if (t.empty()) t = inv(rev(b), n);
        std::vector<int> q = rev(mul(rev(a), t, n));
        q.resize(s);
        return q;
    }

    std::vector<int> rem(std::vector<int> a, std::vector<int> b) {
        while (b.back() == 0) b.pop_back();
        std::vector<int> r = sub(a, mul(quot(a, b), b, b.size() - 1));
        r.resize(b.size() - 1);
        return r;
    }

    std::vector<int> remmul(std::vector<int> a, std::vector<int> b, std::vector<int> c) {
        return rem(mul(a, b), c);
    }

private:
    int pow(int64_t x, int64_t y, int mod) {
        int64_t res = 1;
        for (; y > 0; x = x * x % mod, y >>= 1) if (y & 1) res = res * x % mod;
        return res;
    }

    int inv(int x, int mod) {
        return pow(x, mod - 2, mod);
    }

    int is_pow2(int n) {
        return (n & (n - 1)) == 0;
    }

    int mul(int x, int y) {
        return int64_t(x) * y % mod;
    }

    int add(int x, int y) {
        return (x += y) >= mod ? x - mod : x;
    }

    void upd(int &x, int y) {
        x = add(x, y);
    }

    int pow(int x, int y) {
        int res = 1;
        for (; y > 0; x = mul(x, x), y >>= 1) if (y & 1) res = mul(res, x);
        return res;
    }

    int inv(int x) {
        return pow(x, mod - 2);
    }

    std::vector<int> mul(std::vector<int> a, std::vector<int> b, int n) {
        return kara128.mul(a, b, n);
    }

    std::vector<int> inv(std::vector<int> a, int n) {
        assert(is_pow2(n));
        std::vector<int> b(1);
        b[0] = inv(a[0]);
        for (int i = 0; (1 << i) < a.size(); i++) {
            b = sub(add(b, b), mul(mul(b, b), a, 1 << (i + 1)));
        }
        return b;
    }

    std::vector<int> rev(std::vector<int> a) {
        reverse(a.begin(), a.end());
        return a;
    }
};

const int mod = 1e9 + 7;

int64_t dp[2][301][4000], way[10000];

void calc(int64_t dp[301][4000], int64_t n, std::vector<int> dice) {
    dp[0][0] = 1;
    for (int k = 0; k < dice.size(); k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 3910; j++) {
                (dp[i + 1][j + dice[k]] += dp[i][j]) %= mod;
            }
        }
    }
}

int main() {
    using namespace std;
    int64_t N, P, C;
    cin >> N >> P >> C;
    calc(dp[0], P, { 2, 3, 5, 7, 11, 13 });
    calc(dp[1], C, { 4, 6, 8, 9, 10, 12 });
    for (int i = 0; i <= 3900; i++) {
        for (int j = 0; j <= 3900; j++) {
            (way[i + j] += dp[0][P][i] * dp[1][C][j]) %= mod;
        }
    }
    int64_t K = P * 13 + C * 12 + 1;
    vector<int> a(K + 1);
    for (int i = 0; i < K; i++) a[i] = mod - way[K - i];
    a[K] = 1;
    int64_t M = N + K - 1;
    AnyModPolynomial poly(mod);
    vector<int> f = { 1 }, g = { 0, 1 };
    for (; M > 0; g = poly.remmul(g, g, a), M >>= 1) if (M & 1) f = poly.remmul(f, g, a);
    int64_t ans = 0;
    for (int i = 0; i < K; i++) ans += int64_t(f[i]);
    cout << ans % mod << endl;
}
0