QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#583799	#8635. 圆	jinhaoxian	100 ✓	35ms	183852kb	C++14	1.1kb	2024-09-22 22:30:21	2024-09-22 22:30:32

Judging History

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

[2024-09-22 22:30:32]
评测

测评结果：100
用时：35ms
内存：183852kb

查看

[2024-09-22 22:30:21]
提交

answer

#include<bits/stdc++.h>
using namespace std;
const long long mod=998244353;
int n;
long long fac[5005],g[5005],dp[5005][5005];
long long qpow(long long a,int b) {
    long long res=1;
    while (b) {
        if (b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
int main() {
    cin>>n;
    if (n<=4) {
        cout<<n-2<<endl;
        return 0;
    }
    n--;
    dp[1][1]=dp[1][2]=dp[1][3]=1;
    for (int i=2;i<=n-1;i++) {
        for (int j=i;j<=n-1;j++) {
            dp[i][j]=(dp[i-1][j-1]+dp[i-1][j-2])%mod;
            if (j>=3) dp[i][j]=(dp[i][j]+dp[i-1][j-3])%mod;
        }
    }
    for (int x=1;x<=n;x++) {
        g[x]=(dp[x][n-1]+dp[x-1][n-1]+dp[x][n-2]+dp[x-1][n-2]+dp[x-1][n-3])%mod;
    }
    fac[0]=1;
    for (int i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod;
    long long ans=0;
    for (int x=1;x<=n;x++) {
        ans=(ans+(mod+g[x]*fac[x]%mod*fac[n-x]%mod
        -g[x-1]*fac[x-1]%mod*fac[n-x+1]%mod)%mod*x)%mod;
    }
    ans=ans*qpow(fac[n],mod-2)%mod;
    cout<<(ans+1)%mod<<endl;
    return 0;
}

源文件, 语言: C++14

详细

Pretests

Final Tests

Test #1:

score: 10

Accepted

time: 0ms

memory: 3660kb

input:

output:

result:

ok 1 number(s): "1"

Test #2:

score: 10

Accepted

time: 0ms

memory: 3628kb

input:

output:

result:

ok 1 number(s): "2"

Test #3:

score: 10

Accepted

time: 0ms

memory: 3636kb

input:

output:

299473309

result:

ok 1 number(s): "299473309"

Test #4:

score: 10

Accepted

time: 0ms

memory: 3584kb

input:

output:

487238321

result:

ok 1 number(s): "487238321"

Test #5:

score: 10

Accepted

time: 0ms

memory: 7788kb

input:

output:

41620761

result:

ok 1 number(s): "41620761"

Test #6:

score: 10

Accepted

time: 2ms

memory: 12036kb

input:

output:

208771764

result:

ok 1 number(s): "208771764"

Test #7:

score: 10

Accepted

time: 3ms

memory: 22232kb

input:

output:

888621375

result:

ok 1 number(s): "888621375"

Test #8:

score: 10

Accepted

time: 28ms

memory: 177132kb

input:

output:

319137015

result:

ok 1 number(s): "319137015"

Test #9:

score: 10

Accepted

time: 35ms

memory: 183448kb

input:

output:

818467659

result:

ok 1 number(s): "818467659"

Test #10:

score: 10

Accepted

time: 19ms

memory: 183852kb

input:

output:

142907477

result:

ok 1 number(s): "142907477"