TheJourneyofGeorAutumn

Once upon a time, there was a witch named Geor Autumn, who set off on a journey across the world. Along the way, she would meet all kinds of people, from a country full of ICPC competitors to a horse in love with dota---but with each meeting, Geor would become a small part of their story, and her own world would get a little bit bigger.

Geor just arrived at the state of Shu where people love poems. A poem is a permutation ${(a_1,\ldots, a_n)}$ of ${[n]}$ . ( $(a_1,\ldots, a_n)$ is a permutation of ${[n]}$ means that each ${a_i}$ is an integer in ${[1,n]}$ and that ${a_1,\ldots, a_n}$ are distinct.) One poem is good if for all integer ${i}$ satisfying ${i> k}$ and ${i\le n}$ , ${a_i>\min(a_{i-k}, \ldots, a_{i-1})}$ . Here ${\min(a_{i-k}, \ldots, a_{i-1})}$ denotes the minimum value among ${a_{i-k}, \ldots, a_{i-1}}$ .

Help Geor calculate how many good poems there are, given ${n}$ and ${k}$ . To avoid huge numbers, output the answer modulo ${998244353}$ .

#include<bits/stdc++.h> #define ll long long using namespace std; const int mod=998244353; const int maxn=1e7+10; ll inv[maxn],p[maxn]; int n,k; int main(){ inv[1]=1; for(int i=2;i<maxn;i++) inv[i]=mod-mod/i*inv[mod%i]%mod; scanf("%d%d",&n,&k); ll s=p[0]=1; for(int i=1;i<=n;i++){ p[i]=inv[i]*s%mod; s+=p[i]; if(i>=k) s-=p[i-k]; s%=mod; } ll ans=p[n]%mod+mod; for(int i=1;i<=n;i++) ans=ans*i%mod; printf("%lld",ans); }

详情