QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#619725#8635. 圆NianFeng100 ✓28ms124556kbC++143.5kb2024-10-07 15:11:022024-10-07 15:11:05

Judging History

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

  • [2024-10-07 15:11:05]
  • 评测
  • 测评结果:100
  • 用时:28ms
  • 内存:124556kb
  • [2024-10-07 15:11:02]
  • 提交

answer

/* 年挽红枫,溪傍芦荻。*/
#define DEBUG false
#if DEBUG
    #include <cassert>
    #include <iostream>
    #include <cmath>
    #include <ctime>
    bool Mbe;
    void _dihan();
#endif
#include <cstdio>
#include <string>
#define i128 __int128
#define i64 long long
#define mod 998244353
#define uit unsigned int
#define ull unsigned i64
template <class T> bool chkmax(T &x,T y){ return x<y?x=y,true:false; }
template <class T> bool chkmin(T &x,T y){ return x>y?x=y,true:false; }
#define add(x,y) (x+=y)>=mod&&(x-=mod)
#define dec(x,y) (x-=y)<0&&(x+=mod)
using namespace std;
namespace io{
    #define file(s,x)\
        freopen(#s#x".in","r",stdin);\
        freopen(#s".out","w",stdout);
    const int SIZE=1<<21;
    short plc[50],rof=0u;
    char ibuf[SIZE],*p1=ibuf,*p2=ibuf,obuf[SIZE],*p3=obuf;
    #define flush() (fwrite(obuf,1,p3-obuf,stdout),p3=obuf)
    #define gc() (p1==p2&&(p2=(p1=ibuf)+fread(ibuf,1,SIZE,stdin),p1==p2)?EOF:*p1++)
    #define pc(ch) (p3==obuf+SIZE&&flush(),*p3++=ch)
    class Flush{ public: ~Flush(){ flush(); } }_;
    template <class T> inline void read(T &x){
        x=0; bool flag=true; char c=gc();
        while(!isdigit(c)){ if(c=='-') flag=false; c=gc(); }
        while(isdigit(c)){ x=(x<<1)+(x<<3)+(c^48); c=gc(); }
        !flag&&(x=~(x-1));
    }
    inline void read(char &c){ while((c=gc())<'a'||c>'z'); }
    inline void read(string &s){
        s=""; char c; while((c=gc())<'a'||c>'z') ;
        s+=c; while((c=gc())>='a'&&c<='z') s+=c;
    }
    template <class T,class ...Args>
    inline void read(T &first,Args &...args){
        read(first);
        read(args...);
    }
    template <class T> inline void print(T x){
        x<0?pc('-'),x=-x:0;
        do plc[++rof]=x%10; while(x/=10);
        while(rof) pc(plc[rof--]|48);
    }
    inline void print(char c){ pc(c); }
    inline void print(string s){ for(char c : s) pc(c); }
    inline void print(const char *s){ print(string(s)); }
    template <class T,class ...Args>
    inline void print(T first,Args ...args){
        print(first);
        print(args...);
    }
}
using namespace io;
namespace math{
    inline i64 Qpow(i64 a,int x,i64 res=1){
        do
            x&1&&(res=res*a%mod),a=a*a%mod;
        while(x>>=1); return res;
    }
}
using namespace math;
const int N=5100;
i64 n,fac[N],f[N][N];
void init(){
    fac[0]=1;
    for(int i=1;i<=n;i++)
        fac[i]=fac[i-1]*i%mod;
}
int main(){
    // file(color,);
    read(n),init();
    if(n==3)
        return print("1\n"),0;
    if(n==4)
        return print("2\n"),0;
    f[2][1]=1;
    for(int i=3;i<n;i++)
        for(int j=1;j<=i;j++){
            add(f[i][j],f[i-1][j-1]);
            add(f[i][j],f[i-2][j-1]);
            add(f[i][j],f[i-3][j-1]);
        }
    i64 u=0,d=0;
    for(int i=1;i<n;i++){
        add(u,f[n-2][i]*fac[i]%mod*fac[n-i-1]%mod*3%mod*(i+1)%mod);
        add(d,f[n-2][i]*fac[i]%mod*fac[n-i-1]%mod*3%mod);
        add(u,f[n-3][i]*fac[i]%mod*fac[n-i-1]%mod*2%mod*(i+1)%mod);
        add(d,f[n-3][i]*fac[i]%mod*fac[n-i-1]%mod*2%mod);
        add(u,f[n-4][i]*fac[i]%mod*fac[n-i-1]%mod*(i+1)%mod);
        add(d,f[n-4][i]*fac[i]%mod*fac[n-i-1]%mod);
    }
    print(u*Qpow(d,mod-2)%mod,'\n');
#if DEBUG
    _dihan();
#endif
    return 0;
}
#if DEBUG
    bool Med;
    void _dihan(){
        cerr<<"Memory: "<<abs(&Med-&Mbe)/1048576.0<<" MB\n";
        cerr<<"Time: "<<1e3*clock()/CLOCKS_PER_SEC<<" ms\n";
    }
#endif

詳細信息


Pretests


Final Tests

Test #1:

score: 10
Accepted
time: 1ms
memory: 7620kb

input:

3

output:

1

result:

ok 1 number(s): "1"

Test #2:

score: 10
Accepted
time: 0ms
memory: 7692kb

input:

4

output:

2

result:

ok 1 number(s): "2"

Test #3:

score: 10
Accepted
time: 0ms
memory: 7640kb

input:

6

output:

299473309

result:

ok 1 number(s): "299473309"

Test #4:

score: 10
Accepted
time: 0ms
memory: 7720kb

input:

10

output:

487238321

result:

ok 1 number(s): "487238321"

Test #5:

score: 10
Accepted
time: 0ms
memory: 8012kb

input:

100

output:

41620761

result:

ok 1 number(s): "41620761"

Test #6:

score: 10
Accepted
time: 2ms
memory: 8632kb

input:

200

output:

208771764

result:

ok 1 number(s): "208771764"

Test #7:

score: 10
Accepted
time: 3ms
memory: 10644kb

input:

500

output:

888621375

result:

ok 1 number(s): "888621375"

Test #8:

score: 10
Accepted
time: 21ms
memory: 116560kb

input:

4798

output:

319137015

result:

ok 1 number(s): "319137015"

Test #9:

score: 10
Accepted
time: 20ms
memory: 124556kb

input:

4999

output:

818467659

result:

ok 1 number(s): "818467659"

Test #10:

score: 10
Accepted
time: 28ms
memory: 124536kb

input:

5000

output:

142907477

result:

ok 1 number(s): "142907477"