Submission #38976640

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
/*define about others*/
#define ls(k) k<<1
#define rs(k) k<<1|1
#define lson(k) l,mid,ls(k)
#define rson(k) mid+1,r,rs(k)
#define sizea(x,d) x+1,x+d+1
#define all(x) x.begin(),x.end()
#define lowbit(x) (x&-x)
/*define about variable*/
#define re register
#define il inline
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int ui;
/*define about pair*/
#define np pair<int,int>
#define tup pair<int,pair<int,int> >
#define mp(a,b) make_pair(a,b)
#define mpp(a,b,c) make_pair(a,make_pair(b,c))
#define fi first
#define se second
#define _1 first
#define _2 second.first
#define _3 second.second
/*define about loop*/
#define rep(i,l,r) for(int i(l);i<=(r);++i)
#define per(i,r,l) for(int i(r);i>=(l);--i)
#define repe(u) for(int i=head[u];i;i=e[i].nxt)
#define repv(i,s) for(int i:s)
/*define about STL*/
#define pb push_back
#define ppb pop_back
#define pf push_front
#define ppf pop_front
#define lb lower_bound
#define ub upper_bound
#define eb emplace_back
#define ump unordered_map
#define pq priority_queue
#define iter iterator
/*define about function*/
#define clz __builtin_clz
#define ctz __builtin_ctz
#define ppc __builtin_popcount
#define clzl __builtin_clzll
#define ctzl __builtin_ctzll
#define ppcl __builtin_popcountll
/*define about IO*/
//#define EXODUS
//#define online_judge
#ifdef online_judge
#define debug(x) 1428
#define Debug(...) 2857
#else
#define debug(x) cerr<<"In Line "<<__LINE__<<' '<<#x<<" = "<<(x)<<'\n'
#define Debug(...) fprintf(stderr,__VA_ARGS__)
#endif
namespace IO{
    il int read(){
        int ans=0,flag=1;
        char ch=getchar();
        while(!isdigit(ch)){if(ch=='-')flag=-1;ch=getchar();}
        while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
        return ans*flag;
    }
    il string reads(){
        string ans="";char ch=getchar();
        while(ch==' '||ch=='\n')ch=getchar();
        while(ch!=' '&&ch!='\n')ans+=ch,ch=getchar();
        return ans;
    }
    il char readc(){
        char ch=getchar();
        while(ch==' '||ch=='\n')ch=getchar();
        return ch;
    }
    il int sqr(int x){return x*x;}
    il void reada(int *a,int len){for(int i=1;i<=len;i++)a[i]=read();}
    void write(int x){
        if(x<0)putchar('-'),x=-x;
        if(x>9)write(x/10);
        putchar(x%10+'0');
        return;
    }
}
namespace modcalc{
    const int mod=998244353/*1e9+9*/;
    void fix(int &x){if(x>=mod)x-=mod;else if(x<0)x+=mod;return;}
    void inc(int &x,int y){fix(x+=y);return;}
    void dec(int &x,int y){fix(x-=y);return;}
    void mul(int &x,int y){x=1ll*x*y%mod;return;}
    int rem(int x){if(x>=mod)x-=mod;else if(x<0)x+=mod;return x;}
    int add(int x,int y){return rem(x+y);}
    int del(int x,int y){return rem(x-y);}
    int tim(int x,int y){return 1ll*x*y%mod;}
    int qp(int b,int m){
    	int res=1;
    	for(;m;m>>=1,mul(b,b))if(m&1)mul(res,b);
    	return res;
	}
}
namespace chkmath{
    int chkmin(int &x,int y){x=x>y?y:x;return x;}
    int chkmax(int &x,int y){x=x<y?y:x;return x;}
    int chkeql(int &x,int y){x=y;return x;}
}
using namespace modcalc;
using namespace chkmath;
using namespace IO;

bool mem1=0;
int Datas=0,T=1;

const int N=4e5+7;
int n,k;
int f[N],vis[N],a[N];
int fac[N],inv[N];
int nd;

bool mem2=0;

int C(int x,int y){
	if(x<y)return 0;
	return tim(fac[x],tim(inv[y],inv[x-y])); 
}

void Main(){
	n=read(),k=read();
	for(int i=1;i<=n;i++)
		a[i]=read(),vis[a[i]]=1;
	nd=0;
	int ans=0;
	for(int i=0;i<=4e5;i++){
		if(k-nd-1<0)break;
		inc(ans,C(k-(nd+1)+i,i));
		if(!vis[i])nd++;
	}
	cout<<ans;
    return;
}

int main(){
	for(int i=fac[0]=1;i<=4e5;i++)fac[i]=tim(fac[i-1],i);
	inv[400000]=qp(fac[400000],mod-2);
	for(int i=4e5-1;i>=0;i--)inv[i]=tim(inv[i+1],i+1);
#ifdef EXODUS
    printf("%.5lfMB\n",abs(&mem2-&mem1)/1024.0/1024.0);
    freopen("Data.in","r",stdin);
    freopen("Code.out","w",stdout);
#endif
#ifdef online_judge
    freopen("input.in","r",stdin);
    freopen("user_out.out","w",stdout);
#endif
    if(Datas)T=read();
    while(T--)Main();
#ifdef EXODUS
    cerr<<clock()<<"ms"<<endl;
#endif
    return 0;
}
//LOJ loyal users:EXODUS
/*
0. Enough array size? Enough array size? Enough array size? Interger overflow?

1. Think TWICE, Code ONCE!
Are there any counterexamples to your algo?

2. Be careful about the BOUNDARIES!
N=1? P=1? Something about 0?

3. Do not make STUPID MISTAKES!
Time complexity? Memory usage? Precision error? Use The TRUE MODULE?

4. Do not forget to CHECK YOUR CODE before submitting!
Delete the DEBUGGING? Add FILE I/O?
*/

Submission Info

Judge Result