This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define ll long long
#define F first
#define S second
using namespace std;
const ll p=1e6+3;
struct Dsu{
int ori[1000010]={};
void init(int n){
for(int i=0;i<=n;i++)ori[i]=i;
}
int f(int a){
if(ori[a]==a)return a;
ori[a]=f(ori[a]);
return ori[a];
}
void onion(int a,int b){
a=f(a);
b=f(b);
ori[a]=b;
return ;
}
}dsu;
int n,k,x[1000010];
ll pre[1000010],erp[1000010];
ll inv(ll a){
return a==1?1:(p-p/a)*inv(p%a)%p;
}
ll c(ll a,ll b){
if(a<b)return 0;
return ((pre[a]*erp[b]%p)*erp[a-b])%p;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n>>k;
dsu.init(n+1);
pre[0]=1;
erp[0]=1;
for(int i=1;i<=k;i++){
pre[i]=(pre[i-1]*i)%p;
erp[i]=inv(pre[i]);
}
for(int i=0;i<n-k;i++){
cin>>x[i];
}
for(int i=0;i<n-k-1;i++){
int f=i+2,b=f+k;
if(x[i]==x[i+1])dsu.onion(f,b);
if(x[i]>x[i+1]){
dsu.onion(f,1);
dsu.onion(b,0);
}
if(x[i]<x[i+1]){
dsu.onion(f,0);
dsu.onion(b,1);
}
}
if(dsu.f(0)==dsu.f(1)){
cout<<"0\n";
return 0;
}
int u=dsu.f(0),v=dsu.f(1);
int cnt=0,cnt1=0;
for(int i=2;i<2+k;i++){
int w=dsu.f(i);
if(w==v){
cnt1++;
}
if(u!=w&&v!=w){
cnt++;
}
}
cout<<c(cnt,cnt1)<<"\n";
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |