Submission #334994

#TimeUsernameProblemLanguageResultExecution timeMemory
334994achibasadzishviliZapina (COCI20_zapina)C++14
110 / 110
259 ms3180 KiB
#include<bits/stdc++.h> #define ll long long #define f first #define s second #define pb push_back using namespace std; ll n,C[500][500],dp[500][500],mod=1000000007; int main(){ ios::sync_with_stdio(false); cin >> n; for(int i=0; i<=n; i++){ C[i][0] = 1; } for(int i=1; i<=n; i++) for(int j=1; j<=n; j++){ C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod; } dp[0][0] = 1; for(int i=1; i<=n; i++){ dp[i][0] = 1; for(int j=1; j<=n; j++){ for(int k=0; k<=j; k++){ if(k != i){ dp[i][j] += dp[i - 1][j - k] * C[j][k]; dp[i][j] %= mod; } } } } ll ans = (mod - dp[n][n]),k = 1; for(int i=1; i<=n; i++){ k *= n; k %= mod; } ans = (ans + k) % mod; cout << ans << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...