제출 #1138887

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1138887		phamducminh	Zapina (COCI20_zapina)	C++20	110 / 110	120 ms	1384 KiB

zapina

#include <bits/stdc++.h>
#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <stack>
#include <algorithm>
#include <string>
#include <queue>
#include <cctype>
#include <cstring>
#include <iomanip>
#include <deque>
#include <random>
#include <sstream>

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx,avx2,bmi,bmi2,popcnt,lzcnt")
// #pragma GCC optimize("Ofast","inline","no-stack-protector")
// #pragma GCC target("arch=skylake")

using namespace std;

#define file(name) freopen(name".inp","r",stdin);\
                    freopen(name".out","w",stdout);
#define TIME (1.0*clock()/CLOCKS_PER_SEC)
#define all(a) a.begin(),a.end()
#define all1(a) a+1,a+n+1
#define ll long long

const long long INF=1e18;
const long long MOD=1e9+7;
const long long MODD[] = {(long long)998244353,(long long)1e9+2277, (long long)1e9+5277}; // 998244353
const int maxN=2e5+9;
const long long LOG=20;
const double eps = 1e-1;


//------------------------



void solve();
signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);


    // file("PNUM");



    int t;

    // cin >> t;

    t=1;

    while (t--){
        solve();
    }

    cerr << "Time: " << TIME << "s.\n";
    cerr << "ducminh";
    return 0;
}

/// -------------- PROBLEM SOLUION --------------------


int n;
long long dp[409][409];
long long fac[409], ifac[409];

long long binpow(long long a, long long b){
    long long ans=1;

    while (b){
        if (b&1) ans=ans*a%MOD;

        a=a*a%MOD;
        b>>=1;
    }
    return ans;
}


void genfac(int n){
    fac[0]=1;
    for (int i=1; i<=n; i++){
        fac[i]=fac[i-1]*i%MOD;
    }

    ifac[n]=binpow(fac[n], MOD-2);
    for (int i=n; i>=1; i--){
        ifac[i-1]=ifac[i]*i%MOD;
    }
}

long long combine(int n, int k){
    if (k < 0 || k > n) return 0;
    return fac[n]*ifac[k]%MOD*ifac[n-k]%MOD;
}
void solve(){  

    cin >> n;

    genfac(n+2);

    dp[0][0]=1;
    for (int i=1; i<=n; i++){
        for (int j=0; j<=n; j++){
            for (int k=0; k<=n-j; k++){
                if (k!=i) (dp[i][j+k]+=dp[i-1][j]*combine(n-j,k)%MOD)%=MOD;
                
            }
        }
    }
    cout << (binpow(n,n)%MOD-dp[n][n]+MOD*MOD)%MOD;


}


    

• Subtask 1: 22 / 22
• Subtask 2: 33 / 33
• Subtask 3: 55 / 55