제출 #1162266

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1162266		sofija6	Binaria (CCO23_day1problem1)	C++20	25 / 25	93 ms	70728 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define MAXN 1000010
#define MOD 1000003
using namespace std;
ll a[MAXN],val[MAXN],fact[MAXN];
vector<ll> p[MAXN];
void Init()
{
    fact[0]=1;
    for (ll i=1;i<MAXN;i++)
        fact[i]=(fact[i-1]*i)%MOD;
    return;
}
ll Exp(ll n,ll k)
{
    ll val[30];
    val[0]=n;
    for (ll i=1;i<30;i++)
        val[i]=(val[i-1]*val[i-1])%MOD;
    ll ans=1,cur=29;
    while (k)
    {
        if ((1<<cur)<=k)
        {
            k-=(1<<cur);
            ans=(ans*val[cur])%MOD;
        }
        cur--;
    }
    return ans;
}
ll Binomial_Coefficient(ll n,ll k)
{
    return (((fact[n]*Exp(fact[k],MOD-2))%MOD)*Exp(fact[n-k],MOD-2))%MOD;
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll n,k;
    cin >> n >> k;
    for (ll i=1;i<=n-k+1;i++)
        cin >> a[i];
    if (k==1)
    {
        cout << 1;
        return 0;
    }
    Init();
    for (ll i=1;i<=n;i++)
        val[i]=-1;
    for (ll i=1;i<=k;i++)
        p[i%k].push_back(i);
    for (ll i=2;i<=n-k+1;i++)
    {
        if (a[i]==a[i-1])
            val[i+k-1]=val[p[(i+k-1)%k].back()];
        else if (a[i]>a[i-1])
        {
            val[i+k-1]=1;
            val[p[(i+k-1)%k].back()]=0;
        }
        else
        {
            val[i+k-1]=0;
            val[p[(i+k-1)%k].back()]=1;
        }
        p[(i+k-1)%k].push_back(i+k-1);
    }
    for (ll i=0;i<k;i++)
    {
        ll lastt=-1;
        for (ll j=p[i].size()-1;j>=0;j--)
        {
            if (val[p[i][j]]==-1)
                val[p[i][j]]=lastt;
            else
                lastt=val[p[i][j]];
        }
    }
    ll sum=0,cnt=0;
    for (ll i=1;i<=k;i++)
    {
        if (val[i]!=-1)
            sum+=val[i];
        else
            cnt++;
    }
    cout << Binomial_Coefficient(cnt,a[1]-sum);
    return 0;
}

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