QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#522146 | #8483. Count the Christmas Trees | STnofarjo# | WA | 2ms | 4460kb | C++14 | 974b | 2024-08-16 19:01:14 | 2024-08-16 19:01:15 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+3, mod = 1e9+7;
int fac[maxn], ifac[maxn];
int modpow(int a, int b) {
int ret = 1;
for (; b; b>>=1) {
if (b&1) ret = 1LL * ret * a % mod;
a = 1LL * a * a % mod;
}
return ret;
}
void init() {
fac[0] = 1;
for (int i=1; i<maxn; i++) fac[i] = 1LL * fac[i-1] * i % mod;
ifac[maxn-1] = modpow(fac[maxn-1], mod-2);
for (int i=maxn-1; i>=0; i--) ifac[i-1] = 1LL * ifac[i] * i % mod;
assert(1LL * fac[5] * ifac[5] % mod == 1);
}
void solve() {
int n;
cin >> n;
int ans = 1;
for (int i=2; i<=n; i++) {
int mul = 0;
for (int j=1; j*2<=i; j++) {
int k = i - 1 - j;
mul = (mul + 1LL * fac[j+k] * ifac[j] % mod * ifac[k] % mod) % mod;
}
ans = 1LL * ans * mul % mod;
}
cout << ans << '\n';
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
init();
int tcs = 1;
// cin >> tcs;
while (tcs--) {
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 4448kb
input:
3
output:
2
result:
ok 1 number(s): "2"
Test #2:
score: 0
Accepted
time: 2ms
memory: 4388kb
input:
4
output:
12
result:
ok 1 number(s): "12"
Test #3:
score: 0
Accepted
time: 2ms
memory: 4324kb
input:
1
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 2ms
memory: 4388kb
input:
2
output:
1
result:
ok 1 number(s): "1"
Test #5:
score: -100
Wrong Answer
time: 2ms
memory: 4460kb
input:
5
output:
120
result:
wrong answer 1st numbers differ - expected: '192', found: '120'