QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#326771#8171. Colaluyiming123WA 111ms238072kbC++231.2kb2024-02-14 00:11:112024-02-14 00:11:13

Judging History

你现在查看的是最新测评结果

  • [2024-02-14 00:11:13]
  • 评测
  • 测评结果:WA
  • 用时:111ms
  • 内存:238072kb
  • [2024-02-14 00:11:11]
  • 提交

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'