QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#762362#8023. The Journey of Geor AutumnWRuperDAC ✓236ms159952kbC++201.4kb2024-11-19 14:44:582024-11-19 14:45:02

Judging History

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

  • [2024-11-19 14:45:02]
  • 评测
  • 测评结果:AC
  • 用时:236ms
  • 内存:159952kb
  • [2024-11-19 14:44:58]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const long long inf = 1e18;
const int mininf = 1e9 + 7;
#define pb emplace_back
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
inline void write(int x){if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0');}
#define put() putchar(' ')
#define endl puts("")
const int MAX = 1e7 + 10;
const long long mod = 998244353;
int f[MAX];
int preasd[MAX];
int inv123[MAX];
int F114[MAX];

void solve(){
	int n = read(), k = read();
	f[0] = 1;
	int pre = 1ll * f[0] * preasd[n - 1] % mod;
	for(int i = 1; i <= n; i++){
		if(i - k - 1 >= 0){
			pre = 1ll * (1ll * pre + 1ll * mod - 1ll * f[i - k - 1] * 1ll * preasd[n - (i - k - 1) - 1] % mod) % mod;
		}
		f[i] = 1ll * pre * F114[n - i] % mod;
		pre = 1ll * (1ll * pre + 1ll * f[i] * 1ll * preasd[n - i - 1] % mod) % mod; 
	}
	write(f[n]), endl;
}

signed main(){
	// freopen("b.in", "r", stdin);
	// freopen("b.out", "w", stdout);
	preasd[0] = F114[0] = 1;
	preasd[1] = inv123[1] = F114[1] = 1;
	for(int i = 2; i < MAX; i++){
		preasd[i] = 1ll * preasd[i - 1] * i % mod;
		inv123[i] = 1ll * inv123[mod % i] * (mod - mod / i) % mod;
		F114[i] = 1ll * F114[i - 1] * inv123[i] % mod;
	}
	int t = 1;
	while(t--)	solve();
	return 0;
}

这程序好像有点Bug,我给组数据试试?

详细

Test #1:

score: 100
Accepted
time: 111ms
memory: 122244kb

input:

1 1

output:

1

result:

ok "1"

Test #2:

score: 0
Accepted
time: 107ms
memory: 121244kb

input:

1 2

output:

1

result:

ok "1"

Test #3:

score: 0
Accepted
time: 103ms
memory: 122572kb

input:

1 3

output:

1

result:

ok "1"

Test #4:

score: 0
Accepted
time: 100ms
memory: 121436kb

input:

1 4

output:

1

result:

ok "1"

Test #5:

score: 0
Accepted
time: 93ms
memory: 122732kb

input:

2 1

output:

1

result:

ok "1"

Test #6:

score: 0
Accepted
time: 82ms
memory: 122724kb

input:

2 2

output:

2

result:

ok "2"

Test #7:

score: 0
Accepted
time: 93ms
memory: 120968kb

input:

2 3

output:

2

result:

ok "2"

Test #8:

score: 0
Accepted
time: 103ms
memory: 121328kb

input:

2 4

output:

2

result:

ok "2"

Test #9:

score: 0
Accepted
time: 98ms
memory: 122640kb

input:

3 1

output:

1

result:

ok "1"

Test #10:

score: 0
Accepted
time: 106ms
memory: 120928kb

input:

3 2

output:

4

result:

ok "4"

Test #11:

score: 0
Accepted
time: 92ms
memory: 122684kb

input:

3 3

output:

6

result:

ok "6"

Test #12:

score: 0
Accepted
time: 108ms
memory: 121408kb

input:

3 4

output:

6

result:

ok "6"

Test #13:

score: 0
Accepted
time: 94ms
memory: 120916kb

input:

4 1

output:

1

result:

ok "1"

Test #14:

score: 0
Accepted
time: 113ms
memory: 120996kb

input:

4 2

output:

10

result:

ok "10"

Test #15:

score: 0
Accepted
time: 112ms
memory: 121416kb

input:

4 3

output:

18

result:

ok "18"

Test #16:

score: 0
Accepted
time: 93ms
memory: 121488kb

input:

4 4

output:

24

result:

ok "24"

Test #17:

score: 0
Accepted
time: 103ms
memory: 121972kb

input:

99 50

output:

955866606

result:

ok "955866606"

Test #18:

score: 0
Accepted
time: 98ms
memory: 121164kb

input:

99 70

output:

296999003

result:

ok "296999003"

Test #19:

score: 0
Accepted
time: 97ms
memory: 121188kb

input:

1034 998

output:

637688669

result:

ok "637688669"

Test #20:

score: 0
Accepted
time: 99ms
memory: 120908kb

input:

1099 997

output:

712935289

result:

ok "712935289"

Test #21:

score: 0
Accepted
time: 103ms
memory: 122136kb

input:

10314 998

output:

224695890

result:

ok "224695890"

Test #22:

score: 0
Accepted
time: 92ms
memory: 122428kb

input:

10929 9974

output:

160291286

result:

ok "160291286"

Test #23:

score: 0
Accepted
time: 89ms
memory: 122104kb

input:

103124 99448

output:

695932649

result:

ok "695932649"

Test #24:

score: 0
Accepted
time: 125ms
memory: 122440kb

input:

109139 9937

output:

268916696

result:

ok "268916696"

Test #25:

score: 0
Accepted
time: 131ms
memory: 125384kb

input:

1031234 99238

output:

441457721

result:

ok "441457721"

Test #26:

score: 0
Accepted
time: 115ms
memory: 125272kb

input:

1091239 991237

output:

61047495

result:

ok "61047495"

Test #27:

score: 0
Accepted
time: 205ms
memory: 159904kb

input:

10000000 9982443

output:

224744113

result:

ok "224744113"

Test #28:

score: 0
Accepted
time: 236ms
memory: 159952kb

input:

9999977 5678901

output:

641748125

result:

ok "641748125"

Extra Test:

score: 0
Extra Test Passed