結果

問題 No.890 移調の限られた旋法
コンテスト
ユーザー rpy3cpp
提出日時 2019-09-23 02:37:09
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 25 ms / 2,000 ms
コード長 2,230 bytes
コンパイル時間 1,914 ms
コンパイル使用メモリ 171,544 KB
実行使用メモリ 11,008 KB
最終ジャッジ日時 2024-09-19 04:10:46
合計ジャッジ時間 3,296 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
constexpr long long MOD = 1e9 + 7;

vector<int> factorize(int n){
    vector<int> fs;
    int k = 0;
    for (; n % 2 == 0; n /= 2, ++k);
    if (k > 0) fs.push_back(2);
    for (int p = 3; p * p <= n; p += 2){
        k = 0;
        for(; n % p == 0; n /= p, ++k);
        if (k > 0) fs.push_back(p);
    }
    if (n > 1) fs.push_back(n);
    return fs;
}

long long pow_mod(long long b, long long p, long long mod = 1'000'000'007){
    long long ret = 1;
    while (p){
        if (p & 1) ret = (ret * b) % mod;
        b = (b * b) % mod;
        p >>= 1;
    }
    return ret;
}

class ModuloMath{
private:
    long long N;
    long long mod;
public:
    vector<long long> fac;
    vector<long long> invfac;
    ModuloMath(long long N, long long mod = 1'000'000'007): N{N}, mod{mod}, fac(N + 1, 1), invfac(N + 1, 1){
        for (long long i = 1; i <= N; ++i) fac[i] = (fac[i - 1] * i) % mod;
        invfac[N] = pow_mod(fac[N], mod - 2, mod);
        for (long long i = N; i != 1; --i) invfac[i - 1] = (invfac[i] * i) % mod;
    }
    long long nCr(long long n, long long r){return (r > n or r < 0) ? 0 : (fac[n] * invfac[n - r] % mod * invfac[r] % mod);}
    long long nPr(long long n, long long r){return (r > n or r < 0) ? 0 : (fac[n] * invfac[n - r] % mod);}
    long long nHr(long long n, long long r){return nCr(n + r - 1, r);}
};

long long process(const int N, const int K, int mask, const vector<int> & fs, ModuloMath & mm){
    int c = 0;
    int k = 1;
    for (auto f : fs){
        if (mask & 1){
            ++c;
            k *= f;
        }
        mask >>= 1;
    }
    long long result = mm.nCr(N / k, K / k);
    if (c % 2 == 0) result = MOD - result;
    return result;
}

long long solve(int N, int K){
    int gcd = __gcd(N, K);
    if (gcd == 1) {
        return 0LL;
    }else if (N == K){
        return 1LL;
    }
    ModuloMath mm(N / 2 + 1);
    auto fs = factorize(gcd);
    int k = fs.size();
    long long count = 0LL;
    for (int mask = 1; mask < (1 << k); ++mask){
        count = (count + process(N, K, mask, fs, mm))% MOD;
    }
    return count;
}

int main(){
    int N, K;
    cin >> N >> K;
    cout << solve(N, K) << endl;
    return 0;
}
0