QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#629058 | #8023. The Journey of Geor Autumn | pmt2018 | AC ✓ | 228ms | 161048kb | C++20 | 3.2kb | 2024-10-11 02:25:17 | 2024-10-11 02:25:18 |
Judging History
answer
/*
Problem : E. The Journey of Geor Autumn
Url : https://codeforces.com/gym/102900/problem/E
Date : 2024/10/11 02:06:43
Solver : pmt2018
*/
#include<bits/stdc++.h>
#define y0 pmtx
#define y1 pmtxx
#define x0 pmtxxx
#define x1 pmtxxxx
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define lowbit(x) (x&(-x))
#define DEBUG printf("Passing Line %d in function [%s].\n",__LINE__,__FUNCTION__)
using namespace std;
typedef pair<int ,int > pii;
typedef vector<int > vi;
typedef long long ll;
typedef unsigned long long ull;
namespace FastIO{
const int SIZE=(1<<20);
char in[SIZE],*inS=in,*inT=in+SIZE;
inline char Getchar(){
if(inS==inT){inT=(inS=in)+fread(in,1,SIZE,stdin);if(inS==inT)return EOF;}
return *inS++;
}
char out[SIZE],*outS=out,*outT=out+SIZE;
inline void Flush(){fwrite(out,1,outS-out,stdout);outS=out;}
inline void Putchar(char c){*outS++=c;if(outS==outT)Flush();}
struct NTR{~NTR(){Flush();}}ZTR;
}
#ifndef LOCAL
#define getchar FastIO::Getchar
#define putchar FastIO::Putchar
#endif
template<typename T> inline void read(T &x){
x=0;int f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
x*=f;
}
inline void readstr(char* str){
int len=0;char c=getchar();
while(c==' '||c=='\n')c=getchar();
while(c!=' '&&c!='\n'&&c!='\r')str[len++]=c,c=getchar();
str[len] = '\0';
}
template<typename T>inline void write(T x){
if(!x)putchar('0');
if(x<0)x=-x,putchar('-');
static int sta[20];int tot=0;
while(x)sta[tot++]=x%10,x/=10;
while(tot)putchar(sta[--tot]+48);
}
inline void writestr(char* str){int cur=0;while(str[cur])putchar(str[cur++]);}
const int maxn=10000007,INF=0x3f3f3f3f;
const ll MOD=998244353;
const ll LINF=0x3f3f3f3f3f3f3f3fll;
const ll P=19260817;
template<typename T>inline void ckmax(T &x,T y){x=(y>x?y:x);}
template<typename T>inline void ckmin(T &x,T y){x=(y<x?y:x);}
template<typename T>inline T my_abs(T x){if(x<0)x=-x;return x;}
inline int mod1(int x){return x<MOD?x:x-MOD;}
inline int mod2(int x){return x<0?x+MOD:x;}
inline void add(int &x,int y){x=mod1(x+y);}
inline void sub(int &x,int y){x=mod2(x-y);}
int n,k;
int frac[maxn], ifrac[maxn];
int qpow(int a,int b){
int ret = 1;
while(b){
if(b&1)ret=1ll*ret*a%MOD;
a=1ll*a*a%MOD;
b>>=1;
}
return ret;
}
void init() {
frac[0]=1;
for(int i=1;i<=n;i++){
frac[i]=1ll*i*frac[i-1]%MOD;
}
ifrac[n]=qpow(frac[n], MOD-2);
for(int i=n;i>=1;i--){
ifrac[i-1]=1ll*ifrac[i]*i%MOD;
}
}
int dp[maxn], sum[maxn];
int main(){
read(n), read(k);
init();
dp[n]=1;
sum[n]=1;
for(int i=n-1;i>=1;i--){
dp[i] = 1ll*mod2(sum[i+1]-sum[min(n+1,i+k+1)])*frac[n-i-1]%MOD;
sum[i] = mod1(sum[i+1]+1ll*dp[i]*ifrac[n-i]%MOD);
}
int ans=0;
for(int i=1;i<=k;i++){
add(ans, 1ll*dp[i]*frac[n-1]%MOD*ifrac[n-i]%MOD);
}
write(ans);
return 0;
}
//things to remember
//1.long long
//2.array length
//3.freopen
//4 boarder case
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 11872kb
input:
1 1
output:
1
result:
ok "1"
Test #2:
score: 0
Accepted
time: 0ms
memory: 11756kb
input:
1 2
output:
1
result:
ok "1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 11748kb
input:
1 3
output:
1
result:
ok "1"
Test #4:
score: 0
Accepted
time: 0ms
memory: 11820kb
input:
1 4
output:
1
result:
ok "1"
Test #5:
score: 0
Accepted
time: 2ms
memory: 11832kb
input:
2 1
output:
1
result:
ok "1"
Test #6:
score: 0
Accepted
time: 0ms
memory: 11872kb
input:
2 2
output:
2
result:
ok "2"
Test #7:
score: 0
Accepted
time: 3ms
memory: 11828kb
input:
2 3
output:
2
result:
ok "2"
Test #8:
score: 0
Accepted
time: 0ms
memory: 11908kb
input:
2 4
output:
2
result:
ok "2"
Test #9:
score: 0
Accepted
time: 3ms
memory: 11828kb
input:
3 1
output:
1
result:
ok "1"
Test #10:
score: 0
Accepted
time: 0ms
memory: 11820kb
input:
3 2
output:
4
result:
ok "4"
Test #11:
score: 0
Accepted
time: 3ms
memory: 11824kb
input:
3 3
output:
6
result:
ok "6"
Test #12:
score: 0
Accepted
time: 0ms
memory: 11824kb
input:
3 4
output:
6
result:
ok "6"
Test #13:
score: 0
Accepted
time: 0ms
memory: 11812kb
input:
4 1
output:
1
result:
ok "1"
Test #14:
score: 0
Accepted
time: 0ms
memory: 11828kb
input:
4 2
output:
10
result:
ok "10"
Test #15:
score: 0
Accepted
time: 0ms
memory: 11824kb
input:
4 3
output:
18
result:
ok "18"
Test #16:
score: 0
Accepted
time: 2ms
memory: 11824kb
input:
4 4
output:
24
result:
ok "24"
Test #17:
score: 0
Accepted
time: 3ms
memory: 11760kb
input:
99 50
output:
955866606
result:
ok "955866606"
Test #18:
score: 0
Accepted
time: 0ms
memory: 11772kb
input:
99 70
output:
296999003
result:
ok "296999003"
Test #19:
score: 0
Accepted
time: 0ms
memory: 11884kb
input:
1034 998
output:
637688669
result:
ok "637688669"
Test #20:
score: 0
Accepted
time: 0ms
memory: 11908kb
input:
1099 997
output:
712935289
result:
ok "712935289"
Test #21:
score: 0
Accepted
time: 3ms
memory: 11952kb
input:
10314 998
output:
224695890
result:
ok "224695890"
Test #22:
score: 0
Accepted
time: 0ms
memory: 11864kb
input:
10929 9974
output:
160291286
result:
ok "160291286"
Test #23:
score: 0
Accepted
time: 0ms
memory: 13960kb
input:
103124 99448
output:
695932649
result:
ok "695932649"
Test #24:
score: 0
Accepted
time: 5ms
memory: 14048kb
input:
109139 9937
output:
268916696
result:
ok "268916696"
Test #25:
score: 0
Accepted
time: 22ms
memory: 29756kb
input:
1031234 99238
output:
441457721
result:
ok "441457721"
Test #26:
score: 0
Accepted
time: 25ms
memory: 29468kb
input:
1091239 991237
output:
61047495
result:
ok "61047495"
Test #27:
score: 0
Accepted
time: 228ms
memory: 161048kb
input:
10000000 9982443
output:
224744113
result:
ok "224744113"
Test #28:
score: 0
Accepted
time: 193ms
memory: 160184kb
input:
9999977 5678901
output:
641748125
result:
ok "641748125"
Extra Test:
score: 0
Extra Test Passed