| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 545665 |
2022-04-05T06:39:50 Z |
AlperenT |
Zapina (COCI20_zapina) |
C++17 |
|
258 ms |
1356 KB |
#include <bits/stdc++.h>
using namespace std;
const int N = 350 + 5, MOD = 1e9 + 7;
struct mint{
int val = 0;
mint(long long a = 0) : val(a % MOD) {if(val < 0) val += MOD; }
mint(long long a, long long b) {*this += a; *this /= b; }
mint &operator += (const mint &b) {val += b.val; if(val >= MOD) val -= MOD; return *this; }
mint &operator -= (const mint &b) {val -= b.val; if(val < 0) val += MOD; return *this; }
mint &operator *= (const mint &b) {val = (1ll * val * b.val) % MOD; return *this; }
mint mexp(mint a, long long b){
mint c(1);
for(; b > 0; b /= 2, a *= a) if(b & 1) c *= a;
return c;
}
mint minv(const mint &a) {return mexp(a, MOD - 2); };
mint &operator /= (const mint &b) {*this *= minv(b); return *this; }
friend mint operator + (mint a, const mint &b) {return a += b; }
friend mint operator - (mint a, const mint &b) {return a -= b; }
friend mint operator - (const mint &a) {return 0 - a; }
friend mint operator * (mint a, const mint &b) {return a *= b; }
friend mint operator / (mint a, const mint &b) {return a /= b; }
friend bool operator == (const mint &a, const mint &b) {return a.val == b.val; }
friend bool operator != (const mint &a, const mint &b) {return a.val != b.val; }
friend istream &operator >> (istream &is, mint &a) {long long b; is >> b; a = b; return is; }
friend ostream &operator << (ostream &os, const mint &a) {return os << a.val; }
};
int n;
mint dp[N][N][2], fact[N], invfact[N];
void precalc(){
fact[0] = 1;
for(int i = 1; i < N; i++) fact[i] = fact[i - 1] * i;
invfact[N - 1] = mint().minv(fact[N - 1]);
for(int i = N - 2; i >= 0; i--) invfact[i] = invfact[i + 1] * (i + 1);
}
mint comb(int a, int b){
return fact[a] * (invfact[a - b] * invfact[b]);
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);
precalc();
cin >> n;
dp[0][0][0] = 1;
for(int i = 1; i <= n; i++){
for(int j = 0; j <= n; j++){
for(int k = 0; k <= j; k++){
if(k == i){
dp[i][j][1] += dp[i - 1][j - k][0] * comb(n - (j - k), k);
dp[i][j][1] += dp[i - 1][j - k][1] * comb(n - (j - k), k);
}
else{
dp[i][j][0] += dp[i - 1][j - k][0] * comb(n - (j - k), k);
dp[i][j][1] += dp[i - 1][j - k][1] * comb(n - (j - k), k);
}
}
}
}
cout << dp[n][n][1];
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1236 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1236 KB |
Output is correct |
| 3 |
Correct |
1 ms |
1236 KB |
Output is correct |
| 4 |
Correct |
2 ms |
1236 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1236 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1236 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1236 KB |
Output is correct |
| 3 |
Correct |
1 ms |
1236 KB |
Output is correct |
| 4 |
Correct |
2 ms |
1236 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1236 KB |
Output is correct |
| 6 |
Correct |
1 ms |
1236 KB |
Output is correct |
| 7 |
Correct |
1 ms |
1316 KB |
Output is correct |
| 8 |
Correct |
1 ms |
1312 KB |
Output is correct |
| 9 |
Correct |
1 ms |
1236 KB |
Output is correct |
| 10 |
Correct |
1 ms |
1236 KB |
Output is correct |
| 11 |
Correct |
1 ms |
1236 KB |
Output is correct |
| 12 |
Correct |
1 ms |
1312 KB |
Output is correct |
| 13 |
Correct |
1 ms |
1312 KB |
Output is correct |
| 14 |
Correct |
1 ms |
1312 KB |
Output is correct |
| 15 |
Correct |
1 ms |
1296 KB |
Output is correct |
| 16 |
Correct |
1 ms |
1236 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1236 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1236 KB |
Output is correct |
| 3 |
Correct |
1 ms |
1236 KB |
Output is correct |
| 4 |
Correct |
2 ms |
1236 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1236 KB |
Output is correct |
| 6 |
Correct |
1 ms |
1236 KB |
Output is correct |
| 7 |
Correct |
1 ms |
1316 KB |
Output is correct |
| 8 |
Correct |
1 ms |
1312 KB |
Output is correct |
| 9 |
Correct |
1 ms |
1236 KB |
Output is correct |
| 10 |
Correct |
1 ms |
1236 KB |
Output is correct |
| 11 |
Correct |
1 ms |
1236 KB |
Output is correct |
| 12 |
Correct |
1 ms |
1312 KB |
Output is correct |
| 13 |
Correct |
1 ms |
1312 KB |
Output is correct |
| 14 |
Correct |
1 ms |
1312 KB |
Output is correct |
| 15 |
Correct |
1 ms |
1296 KB |
Output is correct |
| 16 |
Correct |
1 ms |
1236 KB |
Output is correct |
| 17 |
Correct |
149 ms |
1236 KB |
Output is correct |
| 18 |
Correct |
2 ms |
1236 KB |
Output is correct |
| 19 |
Correct |
24 ms |
1236 KB |
Output is correct |
| 20 |
Correct |
1 ms |
1236 KB |
Output is correct |
| 21 |
Correct |
153 ms |
1236 KB |
Output is correct |
| 22 |
Correct |
18 ms |
1236 KB |
Output is correct |
| 23 |
Correct |
3 ms |
1236 KB |
Output is correct |
| 24 |
Correct |
36 ms |
1236 KB |
Output is correct |
| 25 |
Correct |
24 ms |
1236 KB |
Output is correct |
| 26 |
Correct |
82 ms |
1292 KB |
Output is correct |
| 27 |
Correct |
212 ms |
1356 KB |
Output is correct |
| 28 |
Correct |
230 ms |
1288 KB |
Output is correct |
| 29 |
Correct |
225 ms |
1236 KB |
Output is correct |
| 30 |
Correct |
229 ms |
1296 KB |
Output is correct |
| 31 |
Correct |
258 ms |
1288 KB |
Output is correct |
| 32 |
Correct |
225 ms |
1304 KB |
Output is correct |
| 33 |
Correct |
249 ms |
1236 KB |
Output is correct |
| 34 |
Correct |
235 ms |
1236 KB |
Output is correct |
| 35 |
Correct |
258 ms |
1292 KB |
Output is correct |
| 36 |
Correct |
242 ms |
1288 KB |
Output is correct |
| 37 |
Correct |
232 ms |
1296 KB |
Output is correct |
