結果

問題 No.140 みんなで旅行
ユーザー HIcoderHIcoder
提出日時 2023-10-31 12:30:28
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 34 ms / 5,000 ms
コード長 2,595 bytes
コンパイル時間 1,017 ms
コンパイル使用メモリ 107,768 KB
実行使用メモリ 21,748 KB
最終ジャッジ日時 2023-10-31 12:30:31
合計ジャッジ時間 2,761 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 21 ms
21,748 KB
testcase_01 AC 21 ms
21,748 KB
testcase_02 AC 22 ms
21,748 KB
testcase_03 AC 22 ms
21,748 KB
testcase_04 AC 21 ms
21,748 KB
testcase_05 AC 22 ms
21,748 KB
testcase_06 AC 21 ms
21,748 KB
testcase_07 AC 21 ms
21,748 KB
testcase_08 AC 22 ms
21,748 KB
testcase_09 AC 22 ms
21,748 KB
testcase_10 AC 21 ms
21,748 KB
testcase_11 AC 34 ms
21,748 KB
testcase_12 AC 21 ms
21,748 KB
testcase_13 AC 21 ms
21,748 KB
testcase_14 AC 34 ms
21,748 KB
testcase_15 AC 34 ms
21,748 KB
testcase_16 AC 25 ms
21,748 KB
testcase_17 AC 23 ms
21,748 KB
testcase_18 AC 31 ms
21,748 KB
testcase_19 AC 31 ms
21,748 KB
testcase_20 AC 22 ms
21,748 KB
testcase_21 AC 21 ms
21,748 KB
権限があれば一括ダウンロードができます

ソースコード

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