結果
問題 | No.2326 Factorial to the Power of Factorial to the... |
ユーザー |
|
提出日時 | 2023-05-09 23:29:57 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 33 ms / 2,000 ms |
コード長 | 2,625 bytes |
コンパイル時間 | 2,230 ms |
コンパイル使用メモリ | 205,108 KB |
最終ジャッジ日時 | 2025-02-12 21:06:21 |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 20 |
ソースコード
#include<bits/stdc++.h>using namespace std;template <typename T>struct PrimeFact{vector<T> spf;PrimeFact(T N){ init(N); }void init(T N){spf.assign(N + 1, 0);for(T i = 0; i <= N; i++) spf[i] = i;for(T i = 2; i * i <= N; i++) {if(spf[i] == i) {for(T j = i * i; j <= N; j += i){if(spf[j] == j){spf[j] = i;}}}}}map<T, T> get(T n){map<T, T> m;while(n != 1){if(m.count(spf[n]) == 0){m[spf[n]] = 1;}else{m[spf[n]]++;}n /= spf[n];}return m;}};template <typename T>T modpow(T x, T n, const T &m){T ret = 1 % m;x %= m;while(n > 0){if(n & 1) (ret *= x) %= m;(x *= x) %= m;n >>= 1;}return ret;}struct Combination{vector<long long> memo, memoinv, inv;const long long mod;Combination(const int &N, const long long &m) : memo(N + 1), memoinv(N + 1), inv(N + 1), mod(m){memo[0] = memo[1] = 1;memoinv[0] = memoinv[1] = 1;inv[1] = 1;for(int i = 2; i <= N; ++i){memo[i] = memo[i - 1] * i % mod;inv[i] = mod - inv[mod % i] * (m / i) % mod;memoinv[i] = memoinv[i - 1] * inv[i] % mod;}}inline long long fact(const long long &n) const {return memo[n];}inline long long factinv(const long long &n) const {return memoinv[n];}inline long long ncr(const long long &n, const long long &r) const {if(n < r || r < 0) return 0;return (memo[n] * memoinv[r] % mod) * memoinv[n - r] % mod;}inline long long npr(const long long &n, const long long &r) const {if(n < r || r < 0) return 0;return (memo[n] % mod) * memoinv[n - r] % mod;}inline long long nhr(const long long &n, const long long &r) const {if(n == 0 && r == 0) return 1;return ncr(n + r - 1, r);}};const long long MOD = 1000000007;int main(){long long n, p; cin >> n >> p;long long ans = 0;PrimeFact<int> spf(n);for(int i = 2; i <= n; i++){map<int, int> mp = spf.get(i);for(auto [k, x] : mp){if(k == p){ans += x;}}}Combination comb(n, MOD);Combination comb2(n, MOD - 1);long long e = modpow(comb.fact(n), comb2.fact(n), MOD);ans *= e; ans %= MOD;cout << ans << "\n";}