QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#583509#6417. Classical Summation Problemship2077#WA 1ms6000kbC++23995b2024-09-22 20:18:402024-09-22 20:18:41

Judging History

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

  • [2024-09-22 20:18:41]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:6000kb
  • [2024-09-22 20:18:40]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
constexpr int M=1e6+5,mod=998244353;
int fac[M],ifac[M];
int qpow(int x,int n){
    int s=1; while (n){
        if (n&1) s=1ll*s*x%mod;
        x=1ll*x*x%mod; n>>=1;
    } return s;
}
void init(int n){
    for (int i=fac[0]=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%mod;
    ifac[n]=qpow(fac[n],mod-2);
    for (int i=n;i;i--) ifac[i-1]=1ll*ifac[i]*i%mod;
}
int c(int n,int m){return n<m||m<0?0:1ll*fac[n]*ifac[m]%mod*ifac[n-m]%mod;}
int main(){ int n,k;
    scanf("%d%d",&n,&k);init(n);
    int p=(k+1>>1)-1,ans=0;
    ans=1ll*(n+1>>1)*qpow(n,k)%mod;
    if (n%2==0){
        const int i=n>>1;
        for (int j=0;j<=p;j++)
            ans=(ans+1ll*qpow(i,j)*qpow(n-i,k-j)%mod*c(k,j))%mod;
    }
    if (k%2==0){
        for (int i=0;i<<1<n;i++){
            const int j=k/2;
            ans=(ans-1ll*qpow(i,j)*qpow(n-i,k-j)%mod*c(k,j))%mod;
        }
    }
    if (ans<0) ans+=mod;
    printf("%d\n",ans);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 5912kb

input:

3 2

output:

14

result:

ok 1 number(s): "14"

Test #2:

score: 0
Accepted
time: 1ms
memory: 5844kb

input:

5 3

output:

375

result:

ok 1 number(s): "375"

Test #3:

score: 0
Accepted
time: 1ms
memory: 5824kb

input:

2 2

output:

5

result:

ok 1 number(s): "5"

Test #4:

score: 0
Accepted
time: 1ms
memory: 5840kb

input:

10 9

output:

508778235

result:

ok 1 number(s): "508778235"

Test #5:

score: 0
Accepted
time: 1ms
memory: 5864kb

input:

69 3

output:

11497815

result:

ok 1 number(s): "11497815"

Test #6:

score: 0
Accepted
time: 1ms
memory: 6000kb

input:

994 515

output:

33689623

result:

ok 1 number(s): "33689623"

Test #7:

score: -100
Wrong Answer
time: 1ms
memory: 5868kb

input:

4476 6182

output:

937057422

result:

wrong answer 1st numbers differ - expected: '114894183', found: '937057422'