Submission #988771

#TimeUsernameProblemLanguageResultExecution timeMemory
988771HD1Binaria (CCO23_day1problem1)C++14
25 / 25
63 ms24404 KiB
//we all are lost trying to be someone //The best way to predict the future is to create it #include<bits/stdc++.h> #define fastio ios_base::sync_with_stdio(0); cin.tie(0); #define sz(x) ll(x.size()) #define all(x) x.begin(), x.end() #define pb push_back #define ff first #define ss second using namespace std; typedef long long ll; typedef long double ld; typedef pair<ll,ll> ii; typedef pair<ii,ll> tri; const ll mod=1e6+3; const ll MAX=1e6; ll n, k; ll bin[MAX+20], A[MAX+20], fact[MAX+20]; bool id[MAX+20]; ll mul(ll a, ll b){ return (a*b)%mod; } ll binpow(ll base, ll expo){ if(expo==0)return 1; ll aux=binpow(base, expo/2); if(expo%2==1){ return mul(mul(aux,aux),base); } return mul(aux, aux); } ll comb(int a, int b){ return (mul(fact[a],binpow(mul(fact[b],fact[a-b]), mod-2))); } void solve(){ cin>>n>>k; ll aux=-1; ll pos=0; ll num=0; fact[0]=1; for(int i=1; i<=MAX; i++){ fact[i]=fact[i-1]*i; fact[i]%=mod; } //cout<<3<<' '<<2<<endl; //cout<<comb(3,2)<<endl; for(int i=0; i<n-k+1; i++){ cin>>A[i]; if(aux==-1){ aux=A[i]; continue; } if(aux!=A[i]){ if(!id[pos%k]){ id[pos%k]=true; if(A[i]>aux)bin[pos%k]=0; else bin[pos%k]=1; } } else num++; aux=A[i]; pos++; } //if(num==n-k){ //cout<<"here"<<endl; // cout<<comb(k,A[0])<<'\n'; // return; //} ll sum=0; ll cant=0; for(int i=0; i<k; i++){ sum+=bin[i]; if(!id[i])cant++; //cout<<bin[i]<<' '; } //cout<<endl; //cout<<cant<<' '<<A[0]-sum<<endl; cout<<comb(cant,A[0]-sum)<<'\n'; } int main(){ fastio; solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...