QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#326771 | #8171. Cola | luyiming123 | WA | 111ms | 238072kb | C++23 | 1.2kb | 2024-02-14 00:11:11 | 2024-02-14 00:11:13 |
Judging History
answer
# include <bits/stdc++.h>
# define int long long
using namespace std;
using i64 = long long;
const int N = 1e7 + 5, mod = 998244353;
int n, m, coef[N], fac[N], ifac[N];
int qpow(int x, int p = mod - 2)
{
int ans = 1;
while(p)
{
if(p & 1) ans = 1ll * ans * x % mod;
x = 1ll * x * x % mod, p >>= 1;
}
return ans;
}
void Init(int n = N - 5)
{
for(int k = -5000; k <= 5000; k++)
{
int alpha = (3 * k * k - k) / 2;
if(alpha <= n) coef[alpha] += ((k & 1) ? -1 : 1);
}
fac[0] = ifac[0] = 1;
for(int i = 1; i <= n; i++) fac[i] = 1ll * fac[i - 1] * i % mod;
ifac[n] = qpow(fac[n]);
for(int i = n - 1; i >= 1; i--) ifac[i] = 1ll * ifac[i + 1] * (i + 1ll) % mod;
return;
}
int C(int n, int m)
{
return 1ll * fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}
signed main(void)
{
scanf("%lld%lld", &n, &m);
Init();
int Ans = 0;
for(int s = 0; s <= m - 1; s++)
{
Ans = (1ll * Ans + 1ll * C(n + m - 1 - s, n) * coef[s] % mod + mod) % mod;
}
printf("%lld\n", 1ll * Ans * ifac[n] % mod);
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 64ms
memory: 236944kb
input:
2 1
output:
499122177
result:
ok "499122177"
Test #2:
score: 0
Accepted
time: 79ms
memory: 238072kb
input:
1 1
output:
1
result:
ok "1"
Test #3:
score: 0
Accepted
time: 99ms
memory: 237280kb
input:
167 91
output:
469117530
result:
ok "469117530"
Test #4:
score: -100
Wrong Answer
time: 111ms
memory: 236816kb
input:
9806463 8975779
output:
624282739
result:
wrong answer 1st words differ - expected: '125384417', found: '624282739'