結果

問題 No.140 みんなで旅行
ユーザー HIcoder
提出日時 2023-10-31 12:30:28
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 36 ms / 5,000 ms
コード長 2,595 bytes
コンパイル時間 1,220 ms
コンパイル使用メモリ 103,524 KB
最終ジャッジ日時 2025-02-17 17:09:15
ジャッジサーバーID
（参考情報） 		judge1 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<set>
#include<algorithm>
#include<vector>
#include<string>
#include<set>
#include<map>
#include<stack>
#include<numeric>
#include<queue>
#include<cmath>
#include<deque>
using namespace std;
typedef long long ll;
const ll INF=1LL<<60;
typedef pair<int,int> P;
typedef pair<int,P> PP;
const ll MOD=1e9+7;


//xのy乗
ll mod_pow(ll x,ll y,ll mod){
    ll power=x;
    ll ret = 1;
    while(y>0){
        if(y&1){
           ret = ret*power%mod;
        }
        power = power*power%mod;
        y = y>>1;
    }
    return ret;

}



struct combination{
    typedef long long ll;
    std::vector<ll> fact,ifact;
    combination(ll n): fact(n+1),ifact(n+1){
        fact[0]=1;//0!=1通り
        for(ll i=1;i<=n;i++) fact[i] = fact[i-1]*i%MOD;
        //ifact[n] = fact[n].inv();
        
        // n!の逆元がifact[n]
        ifact[n] = mod_pow(fact[n],MOD-2,MOD);// n!を(mod-2)乗した後でmodであまりをとった
        for(ll i=n;i>=1;i--) ifact[i-1] = ifact[i]*i%MOD;
    }

    ll operator()(ll n,ll k){
        if(k<0 || k>n) return 0;
        // n!/( k!*(n-k)! )
        return (fact[n]*ifact[k])%MOD * ifact[n-k]%MOD;
    }

};

combination comb(1000000);

struct Stirling{
    vector<vector<ll>> S;

    Stirling(int MAX):S(MAX+1,vector<ll>(MAX+1,0)){
        
        for(int k=1;k<=MAX;k++){
            S[k][1]=1;
        }

       

        for(int n=2;n<=MAX;n++){
            for(int k=2;k<=n;k++){
                S[n][k]=S[n-1][k-1] + k*S[n-1][k]%MOD;
                S[n][k]%=MOD;
            }
        }
    }

    ll get(ll n,ll k){
        if(n<0 || k<0 || n<k) return 0;
        else return S[n][k];
    }
};

int main(){
    ll N;
    cin>>N;


    Stirling stir(600);

    /*
    
    kグループに分かれるとする

    グループ分けのときにばらけない夫婦がn組
    ばらける夫婦が N-n組


    ばらけない夫婦の通り数が NCn
    こいつらでkグループを構成するが,kグループの中で空のグループがあってはいけない
    かつ kグループは区別をつけないで スターリング数S(n,k)



    ばらける夫婦の通り数.k個のグループあるけど,同じグループになってはいけないのでk*(k-1)通り
    (k(k-1))^(N-n)


    */
    ll ans=0;
    for(int k=1;k<=N;k++){
        for(int n=0;n<=N;n++){
            ll res=comb(N,n);
            res*=stir.get(n,k);
            res%=MOD;
            res*=mod_pow(k*(k-1)%MOD, N-n,MOD);
            ans+=res;
            ans%=MOD;
        }
        
    }

    


    cout<<ans<<endl;
}
0