結果
問題 | No.2326 Factorial to the Power of Factorial to the... |
ユーザー |
![]() |
提出日時 | 2023-05-28 14:31:40 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 34 ms / 2,000 ms |
コード長 | 6,241 bytes |
コンパイル時間 | 4,633 ms |
コンパイル使用メモリ | 268,564 KB |
最終ジャッジ日時 | 2025-02-13 11:39:34 |
ジャッジサーバーID (参考情報) |
judge3 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 20 |
ソースコード
#include <bits/stdc++.h>using namespace std;#include <atcoder/all>using namespace atcoder;template<typename T> inline bool chmax(T &a, T b) { return ((a < b) ? (a = b, true) : (false)); }template<typename T> inline bool chmin(T &a, T b) { return ((a > b) ? (a = b, true) : (false)); }#define rep(i, n) for (long long i = 0; i < (long long)(n); i++)#define rep2(i, m ,n) for (int i = (m); i < (long long)(n); i++)#define REP(i, n) for (long long i = 1; i < (long long)(n); i++)typedef long long ll;#pragma GCC target("avx512f")#pragma GCC optimize("Ofast")#pragma GCC optimize("unroll-loops")#define updiv(N,X) (N + X - 1) / X#define l(n) n.begin(),n.end()#define mat vector<vector<ll>>#define YesNo(Q) Q==1?cout<<"Yes":cout<<"No"using P = pair<int, int>;using mint = modint;const int MOD = 998244353LL;const ll INF = 999999999999LL;vector<long long> fact, fact_inv, inv;/* init_nCk :二項係数のための前処理計算量:O(n)*/template <typename T>void input(vector<T> &v){rep(i,v.size()){cin>>v[i];}return;}void init_nCk(int SIZE) {fact.resize(SIZE + 5);fact_inv.resize(SIZE + 5);inv.resize(SIZE + 5);fact[0] = fact[1] = 1;fact_inv[0] = fact_inv[1] = 1;inv[1] = 1;for (int i = 2; i < SIZE + 5; i++) {fact[i] = fact[i - 1] * i % MOD;inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;fact_inv[i] = fact_inv[i - 1] * inv[i] % MOD;}}/* nCk :MODでの二項係数を求める(前処理 int_nCk が必要)計算量:O(1)*/long long nCk(int n, int k) {assert(!(n < k));assert(!(n < 0 || k < 0));return fact[n] * (fact_inv[k] * fact_inv[n - k] % MOD) % MOD;}long long modpow(long long a, long long n, long long mod) {long long res = 1;while (n > 0) {if (n & 1) res = res * a % mod;a = a * a % mod;n >>= 1;}return res;}ll POW(ll a,ll n){long long res = 1;while (n > 0) {if (n & 1) res = res * a;a = a * a;n >>= 1;}return res;}struct unionfind{vector<int> par,siz;void reset(int n){par.resize(n);siz.resize(n);rep(i,n){par[i]=-1;siz[i]=1;}}int root(int x){if(par[x]==-1){return x;}else{return par[x] = root(par[x]);}}bool issame(int x,int y){return root(x)==root(y);}bool unite(int x,int y){x = root(x);y=root(y);if(x == y){return false;}if(siz[x] < siz[y]){swap(x,y);}par[y] = x;siz[x] += siz[y];return true;}int size(int x){return siz[root(x)];}};struct graph{vector<vector< pair<int,ll> > > val;void print(){rep(i,val.size()){rep(j,val[i].size()){cout << val[i][j].first<<"/" <<val[i][j].second << " ";}cout << endl;}}void resize(int n){val.resize(n);}void add(int n,int k,ll cost){ assert((int)(val.size())>k);val[ n ].push_back( pair(k,cost) ); }void add2(int n,int k,ll cost){ val[ n ].push_back( pair(k,cost) ); val[ k ].push_back( pair(n,cost) );}vector<ll> dfs_basic(int a){vector<ll>seen(val.size(),-1);queue<int> q;q.push(a);seen[a]=0;while(!q.empty()){int wc=q.front();q.pop();rep(i,val[wc].size()){if(-1==seen[val[wc][i].first]){q.push(val[wc][i].first);seen[val[wc][i].first]=seen[wc]+val[wc][i].second;}}}return seen;}vector<ll>dijkstra(int r){vector<ll> d(val.size(), INF);d[r] = 0;priority_queue<P, vector<P>, greater<P>> pq;pq.push(P(0, r));while (!pq.empty()){P p = pq.top();pq.pop();int dist = p.first, u = p.second;if (dist > d[u])continue;for (ll i = 0LL; i < (int)(val[u].size()); i++){int v = val[u][i].first, w = val[u][i].second;if (d[v] > d[u] + w){d[v] = d[u] + w;pq.push(P(d[v], v));}}}return d;}ll classcal(){std::priority_queue<pair<ll,pair<int,int>>, // 要素の型はintstd::vector<pair<ll,pair<int,int>>>, // 内部コンテナはstd::vector (デフォルトのまま)std::greater<pair<ll,pair<int,int>>> // 昇順 (デフォルトはstd::less<T>)> pq;// priority_queue<pair<ll,pair<int,int>>> pq;ll costt=0;rep(i,val.size()){rep(j,val[i].size()){if(val[i][j].first>i){pq.push(pair(val[i][j].second,pair(i,val[i][j].first)));}}}dsu d(val.size());while(!pq.empty()){pair<ll,pair<int,int>> ee=pq.top();pq.pop();if(d.same(ee.second.first,ee.second.second)){continue;}costt += ee.first;d.merge(ee.second.first,ee.second.second);}return costt;}};// N の約数をすべて求める関数ll cd(long long N) {// 答えを表す集合long long res=0;// 各整数 i が N の約数かどうかを調べるfor (long long i = 1; i * i <= N; ++i) {// i が N の約数でない場合はスキップif (N % i != 0) continue;// i は約数であるres ++;// N ÷ i も約数である (重複に注意)if (N / i != i){res += 1;}}// 約数を小さい順に並び替えて出力return res;}ll md;/// 行列積mat mat_mul(mat &a, mat &b) {mat res(a.size(), vector<ll>(b[0].size()));for (int i = 0; i < (int)(a.size()); i++) {for (int j = 0; j < (int)(b[0].size()); j++) {for (int k = 0; k < (int)(b.size()); k++) {(res[i][j] += a[i][k] * b[k][j]) %= md;}}}return res;}/// 行列累乗mat mat_pow(mat a, long long n) {mat res(a.size(), vector<ll>(a.size()));// 単位行列で初期化for (int i = 0; i < (int)(a.size()); i++)res[i][i] = 1;// 繰り返し二乗法while (n > 0) {if (n & 1) res = mat_mul(a, res);a = mat_mul(a, a);n >>= 1;}return res;}int main() {ll n,p;cin>>n>>p;ll sm = 0;ll f = 1;ll ft = 1;while(n>=ft){ft *= p;sm += n/ft;}rep(i,n){f *= (i+1);f %= 1000000007LL;}ll f2 = 1;rep(i,n){f2 *= (i+1);f2 %= 1000000006LL;}cout << (modpow(f,f2,1000000007LL)*sm)%(1000000007) << endl;}