Submission #1138594

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138594		mnbvcxz123	Binaria (CCO23_day1problem1)	C++20	25 / 25	181 ms	110836 KiB

Main

#include<bits/stdc++.h>
using namespace std;
using ll=long long;

constexpr int mod=1e6+3;

ll pw(ll a, ll w){
    a%=mod;
    ll ret=1;
    while(w){
        if(w&1)ret=ret*a%mod;
        a=a*a%mod;
        w>>=1;
    }
    return ret;
}

ll C(ll n, ll k){
    if(n<0 or k<0 or k>n)return 0;
    ll ret=1;
    for(ll i=n-k+1;i<=n;++i)
        ret=ret*i%mod;
    ll p=1;
    for(ll i=1;i<=k;++i)p=p*i%mod;
    p=pw(p,mod-2);
    ret=ret*p%mod;
    return ret;
}

int n,k;
vector<int>g[1000005];
int a[1000005];
int col[1000005];
bool vis[1000005];

void fk(){
    cout<<0<<'\n';
    exit(0);
}

void add(int a, int b){
    g[a].push_back(b);
    g[b].push_back(a);
}

void dfs(int v, int c){
    if(!vis[v] and col[v]!=-1 and col[v]!=c)fk();
    vis[v]=1;
    col[v]=c;
    for(const int&i:g[v])
        if(!vis[i])dfs(i,c);
}

void solve(){
    cin>>n>>k;
    int m=n-k+1;
    for(int i=1;i<=m;++i)cin>>a[i];
    for(int i=1;i<=n;++i)col[i]=-1;
    for(int i=1;i<m;++i){
        if(a[i]==a[i+1])add(i,i+k);
        else if(a[i]==a[i+1]+1){col[i]=1;col[i+k]=0;}
        else if(a[i]==a[i+1]-1){col[i]=0;col[i+k]=1;}
        else fk();
    }
    for(int i=1;i<=n;++i)
        if(col[i]!=-1)dfs(i,col[i]);
    int need=a[1],emp=0;
    for(int i=1;i<=k;++i){
        if(col[i]==-1)++emp;
        else if(col[i]==1)--need;
    }
    cout<<C(emp,need)<<'\n';
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    solve();
}

• Subtask 1: 3 / 3
• Subtask 2: 3 / 3
• Subtask 3: 4 / 4
• Subtask 4: 4 / 4
• Subtask 5: 4 / 4
• Subtask 6: 7 / 7