QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#619725 | #8635. 圆 | NianFeng | 100 ✓ | 28ms | 124556kb | C++14 | 3.5kb | 2024-10-07 15:11:02 | 2024-10-07 15:11:05 |
Judging History
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"