Submission #967933

#	Time	Username	Problem	Language	Result	Execution time	Memory
967933		phoenix0423	Binaria (CCO23_day1problem1)	C++17	25 / 25	69 ms	29008 KiB

Main

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#pragma GCC optimize("Ofast")
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define int long long
#define lowbit(x) x&-x
const int maxn = 1e6 + 1;
const int N = 1e6 + 3;
const int INF = 1e18;
int f[maxn], inf[maxn];

ll fpow(ll a, ll b){
    ll ret = 1;
    while(b){
        if(b & 1) ret = ret * a % N;
        a = a * a % N;
        b >>= 1;
    }
    return ret;
}

ll inv(ll a){ return fpow(a, N - 2);}

void precal(){
    f[0] = 1;
    for(int i = 1; i < maxn; i++) f[i] = f[i - 1] * i % N;
    inf[maxn - 1] = inv(f[maxn - 1]);
    for(int i = maxn - 2; i >= 0; i--) inf[i] = inf[i + 1] * (i + 1) % N;
}

ll binom(ll n, ll k){
    if(n < k) return 0;
    return f[n] * inf[k] % N * inf[n - k] % N;
}

signed main(void){
    fastio;
    precal();
    int n, k;
    cin>>n>>k;
    vector<int> s(n - k + 1);
    int bad = 0;
    for(auto &x : s){
        cin>>x;
        if(x > k) bad = 1;
    }
    for(int i = 0; i < s.size() - 1; i++){
        if(abs(s[i + 1] - s[i]) >= 2) bad = 1;
    }
    if(bad){
        cout<<0<<"\n";
        return 0;
    }
    int fr = k, cnt = 0;
    for(int i = 0; i < k; i++){
        int nd = -1;
        for(int j = i; j + 1 < s.size(); j += k){
            if(s[j + 1] - s[j] == 0) continue;
            if(s[j + 1] - s[j] == 1){
                nd = 0;
                break;
            }
            if(s[j + 1] - s[j] == -1){
                nd = 1;
                break;
            }
        }
        if(nd != -1) fr--, cnt += nd;
    }
    cout<<binom(fr, s[0] - cnt)<<"\n";
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:53:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for(int i = 0; i < s.size() - 1; i++){
      |                    ~~^~~~~~~~~~~~~~
Main.cpp:63:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |         for(int j = i; j + 1 < s.size(); j += k){
      |                        ~~~~~~^~~~~~~~~~

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