Nasser-in Sadə Dilimləri (Həll təhlili)

Həll

Ümumi ideya:

Əvvəlcə Eratosten süzgəcindən istifadə edərək 10^7-ə qədər bütün sadə ədədləri əvvəlcədən hesablayırıq.

Düzgün bir bölünmə mövcud olması üçün massivdəki bütün sadə ədədlərin sayı $k$-ya bölünməlidir. Əgər bölünmürsə, cavab $0$-dır.

Əks halda, problemi elə düşünürük ki, massivi hər birində dəqiq $k$ sadə ədəd olan qruplara bölürük. Hər iki qonşu $k$-lıq qrup arasında bəzi sadə olmayan elementlər ola bilər. Bu elementlər sərhəddə sərbəst şəkildə sol və ya sağ hissəyə aid ola bilər və hər belə seçim cavaba vurma effekti verir.

Daha dəqiq desək, soldan sağa gedərək:

• Cari qrupda görülən sadə ədədlərin sayını $cnt$ ilə izləyirik.

• Cari cut (bölmə) üçün mümkün yerlərin sayını $check$ ilə saxlayırıq.

Qayda:

• Əgər sadə olmayan element görsək və \mathit{cnt} = k olarsa, $check$-i artırırıq (yeni cut variantı yaranır).

• Əgər sadə element görsək və \mathit{cnt} = k olarsa, $ans$-ı $check$-ə vururuq, sonra \mathit{check} = 1, \mathit{cnt} = 0 edirik və yeni qrupa başlayırıq.

Sonda əgər son qrupda dəqiq $k$ sadə ədəd yoxdursa, cavab $0$ olur. Əks halda \mathit{ans} \bmod (10^9 + 7) çap edilir.

Zaman mürəkkəbliyi: \mathcal{O}!\left(A \log \log A + \sum n\right), burada A = 10^7, \sum n \le 2 \cdot 10^5.

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

const int MAX = 1e7 + 1, mod = 1e9 + 7;
vector<bool> is_prime(MAX, true);

void sieve() {
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i * i < MAX; i++)
        if (is_prime[i])
            for (int j = i * i; j < MAX; j += i)
                is_prime[j] = false;
}

void solve() {
    int n, k, cnt = 0, check = 1;
    cin >> n >> k;
    ll ans = 1;
    for (int i = 0; i < n; i++) {
        int x; cin >> x;
        if (!is_prime[x]) {
            if (cnt == k) check++;
        } else {
            if (cnt == k) {
                ans = ans * check % mod;
                check = 1; cnt = 0;
            }
            cnt++;
        }
    }
    if (cnt != k) { cout << 0; return; }
    cout << ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    sieve();
    int t; cin >> t;
    while (t--) { solve(); cout << '\n'; }
    return 0;
}