結果

問題 No.2326 Factorial to the Power of Factorial to the...
ユーザー Magentor
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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>>, // int
std::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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0