Submission #1231058

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231058		g4yuhg	Binaria (CCO23_day1problem1)	C++20	14 / 25	48 ms	23880 KiB

Main

//Huyduocdithitp
#include <bits/stdc++.h>
typedef long long ll;
#define endl '\n'
#define yes cout<<"YES"<<endl;
#define no cout<<"NO"<<endl;
#define fi first
#define se second
#define pii pair<ll, ll>
#define inf 1e18
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MP make_pair
#define TASK "ghuy4g"
#define start if(fopen(TASK".inp","r")){freopen(TASK".inp","r",stdin);freopen(TASK".out","w",stdout);}
#define LOG 19
#define N 1000006
using namespace std;

bool ghuy4g; 

ll par[N];

ll getRoot(ll u) {
    if (par[u] < 0) return u;
    par[u] = getRoot(par[u]);
    return par[u];
}

void join(ll u, ll v) {
    u = getRoot(u);
    v = getRoot(v);
    if (u == v) return;
    if (par[u] < par[v]) {
        par[u] += par[v];
        par[v] = u;
    }
    else {
        par[v] += par[u];
        par[u] = v;
    }
}

ll n, k;
ll b[N], a[N];

const ll mod = 1e9 + 7;

ll POW(ll a, ll b, ll mod) {
    if (b == 0) return 1;
    ll t = POW(a, b / 2, mod);
    t = t * t % mod;
    if (b % 2 == 1) {
        t = t * a % mod;
    }
    return t;
}

ll C(ll n, ll k){
    if (k<0 || k>n) return 0;
    // lợi dụng C(n,k)=C(n,n-k)
    if (k > n-k) k = n-k;

    // Tính num = (n-k+1)*(n-k+2)*...*n mod p
    ll num = 1;
    for(ll i = 1; i <= k; i++){
        num = num * ((n - k + i) % mod) % mod;
    }
    // Tính den = k! mod p
    ll den = 1;
    for(ll i = 1; i <= k; i++){
        den = den * i % mod;
    }
    // invert den
    ll inv_den = POW(den, mod-2, mod);  // log(mod) time

    return num * inv_den % mod;
}



bool klinh;

signed main(void) {
	memset(par, -1, sizeof(par));
	memset(a, -1, sizeof(a));
    faster;
	cin >> n >> k;
	for (int i = 1; i <= n - k + 1; i ++) {
		cin >> b[i];
	}
	for (int i = 1; i < n - k + 1; i ++) {
		if (b[i] == b[i + 1]) {
			join(i, i + k);
		}
		else if (b[i] == b[i + 1] + 1) {
			if (a[i] != -1 && a[i] == 0) {
				cout << 0;
				return 0;
			}
			a[i] = 1;
			if (a[i + k] != -1 && a[i + k] == 1) {
				cout << 0;
				return 0;
			}
			a[i + k] = 0;
		}
		else if (b[i] + 1 == b[i + 1]) {
			if (a[i] != -1 && a[i] == 1) {
				cout << 0;
				return 0;
			}
			a[i] = 0;
			if (a[i + k] != -1 && a[i + k] == 0) {
				cout << 0;
				return 0;
			}
			a[i + k] = 1;
		}
	}
	for (int i = 1; i <= n; i ++) {
		if (a[i] == -1) continue;
		ll root = getRoot(i);
		if (a[root] != -1 && a[root] != a[i]) {
			cout << 0;
			return 0;
		}
		a[getRoot(i)] = a[i];
	}
	map<ll, ll> mp;
	ll sum = 0, cnt = 0;
	for (int i = 1; i <= k; i ++) {
		ll r = getRoot(i);
		if (a[r] == 1) sum += 1;
		else if (a[r] == 0) sum += 0;
		else {
			//cout << i << " root " << r << " " << a[r] << endl;
			mp[r] ++ ;
			if (mp[r] > 1) {
				cout << "ngu";
				return 0;
			}
			cnt ++ ;
		}
	}
	ll left = b[1] - sum;
	//cout << cnt << " " << left << endl;
	cout << C(cnt, left);
	
    cerr << fabs(&klinh - &ghuy4g) / 1048576.0;
    return 0;
}

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