Subtask 1

Bruteforce ~O(n \times t)~. Ta đánh số lại ~n~ người từ ~0~ đến ~n-1~ theo chiều kim đồng hồ.

Gọi ~tp_{i, j}~ là trạng thái của người thứ ~i~ ở giây thứ ~j~. ~tp_{i, j}~ = ~0~ nếu ở giây thứ ~j~, người thứ ~i~ không bị nhiễm virus, ~tp_{i, j}~ = ~1~ nếu ở giây thứ ~j~, người thứ ~i~ bị nhiễm virus. Ta chuyển trạng thái của ~n~ người này từ giây thứ ~j~ sang giây thứ ~j+1~ bằng cách nếu ~tp_{i, j}~ = ~1~, ta cập nhật ~tp_{(i-k+n)\%n,j+1} := 1~ và ~tp_{(i+k)\%n,j+1} := 1~.

Đáp án bằng tổng số lượng người có ~tp_{i, t}~ = ~1~.

Subtask} 2

Ta nhận thấy sau mỗi lần phân tách ra làm 2, ta xoay bàn tròn theo chiều kim đồng hồ k đơn vị thì ta thấy bản chất sau mỗi giây, virus mới được sinh ra sẽ cách virus cũ ~2 \times k~ đơn vị theo chiều kim đồng hồ. Vì virus sau mỗi giây sinh ra một bản sao nên số virus sau ~t~ giây nhiều nhất sẽ là ~t~. Đương nhiên số virus tồn tại sẽ không thể là vô hạn nên ta cần tìm cận trên của số virus. Cận trên của số virus ta có thể đưa về bài toán:

Cho một chu trình đơn gồm ~n~ đỉnh đánh số từ ~0~, đánh dấu đỉnh ~0~, từ ~i~ đang được đánh dấu, ta đánh dấu thêm đỉnh ~(i+k)\%n~ trên đồ thị, hỏi sau khi lặp lại vô hạn lần hành động trên, sẽ có bao nhiêu đỉnh được đánh dấu.

Ta có thể thấy các đỉnh bình đẳng với nhau, nghĩa là nếu khoảng cách (tính cả 2 phía) giữa 2 đỉnh bất kỳ tồn tại (gọi là ~x~) thì với một đỉnh đã được đánh dấu bất kỳ ~i~ thì ta luôn có thể đánh dấu đỉnh ~(i \pm x)\%n~. Cũng vì tất cả các đỉnh bình đẳng với nhau nên trạng thái ko thể có đỉnh mới được đánh dấu là khi tất cả các đỉnh đó cách đều nhau, nghĩa là khoảng cách giữa 2 đỉnh bất kỳ là gần nhau nhất có thể.

Ta gọi hàm g(x, y) với x khoảng cách nhỏ nhất giữa 2 đỉnh khác nhau bất kỳ, y là khoảng cách nhỏ nhì (khác k/c nhỏ nhất) của 2 đỉnh khác nhau bất kỳ (~y>x~). Ta dễ thấy: ~g(x, y) = g(min(x, y-x), max(x, y-x))~, ~g(x, 2 \times x) = x~. Bản chất g(x, y) là hàm gcd(x, y). Vì thế khoảng cách nhỏ nhất giữa các đỉnh với nhau là ~gcd(n, k)~ và số đỉnh được đánh dấu là ~n / gcd(n, k)~.

Vậy kết quả của sub ~2~ là min(~t+1~, ~n/gcd(n, 2 \times k~)). Độ phức tạp thuật toán: Độ phức tạp của hàm gcd.

Subtask 3

Với cách xoay bảng tương tự subtask 2, có thể thấy đây là bài toán cho trước ~m~ điểm trên đồ thị và yêu cầu ta phải đi đánh dấu điểm cách ~2 \times k~ đơn vị trong ~t~ giây. Từ cách chứng minh của bài trên, ta nhận ra trên bàn tròn của ta có đúng ~gcd(n, 2 \times k)~ thành phần liên thông (nếu xét ~t = \inf~), đỉnh ~i~ thuộc thành phần liên thông thứ ~i \% gcd(n, 2 \times k)~. Với nhận xét trên ta có thể tách vòng tròn của mình ra thành ~gcd(n, 2 \times k)~ phần độc lập và giải quyết nó riêng lẻ với nhau, mỗi phần sẽ có ~n/gcd~ đỉnh và độ lớn bước nhảy là ~2 \times k/gcd~. Từ lúc này trở đi ta xem ~n := n / gcd~ và ~k := 2 \times k / gcd~ tương ứng với số đỉnh và khoảng cách bước nhảy khi nói về mỗi phần độc lập, các đỉnh trong mỗi phần đánh số từ ~0~.

Một vấn đề của subtask này là trong mỗi phần, có thể có nhiều đỉnh xuất phát, vì thế ta cần tìm cách để giải quyết những đỉnh được thăm trùng lặp. Gọi ~d[i]~ là thời gian mà đỉnh ~i~ được thăm nếu xuất phát từ đỉnh ~0~, vậy thì với mỗi đỉnh ~i~ trong bàn tròn, ta sẽ đánh dấu các số từ ~d[i]~ đến ~(d[i] + k) \% n~, ta có thể sử dụng kỹ thuật 2 con trỏ để giải quyết tuyến tính bài toán này.

Vậy cách tìm ~d[i]~ như thế nào, đơn giản là ~d[i]~ cần thỏa ~(0 + d[i] \times k) \equiv i (mod n)~, nói cách khác là ~i + j \times n = d[i] \times k (j \in \mathbb{Z})~ hay ~d[i] \times k + j \times n = i (j \in \mathbb{Z})~. Phương trình trên chính là dạng ~ax+by=c~ có thể giải bằng cách tìm nghiệm của ~ax+by=gcd(a, b)~ rồi nhân nghiệm 1 khoảng ~c/gcd(a, b)~, ở phương trình trên thì ~(a, b, c, x, y) = (k, n, i, d[i], j)~ và dễ thấy ~gcd(k, n) = 1~ nên khoảng phải nhân thêm đơn giản chỉ là ~i~. Lưu ý khi tìm thấy nghiệm ~d[i]~ bằng thuật Extended Euclid thì phải đưa ~d[i]~ về với giới hạn ~0 \le d[i] < n~.

Độ phức tạp thuật toán: ~O(log(m))~.

Code mẫu

#include <bits/stdc++.h>
#define BIT(x, i) (((x)>>(i))&1)
#define MASK(i) (1LL<<(i))
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define mp make_pair
#define pb push_back
#define TASK ""

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<ll> vll;
typedef vector<pll> vlll;

template<typename T1, typename T2> bool mini(T1 &a, T2 b) {if(a>b) a=b; else return 0; return 1;}
template<typename T1, typename T2> bool maxi(T1 &a, T2 b) {if(a<b) a=b; else return 0; return 1;}
template<typename T1> T1 abs(T1 a) {if(a<0) a*=-1; return a;}

mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll l, ll h){return l + ll(rd()) * rd() %(h-l+1);}

ll n, m, k, t;
ll p;
map<ll, vll> M;
ll ans = 0;

ll solve(vlll v)
{
    sort(all(v));
    ll ans = 0, last = 0, fin = 0;
    for(auto &[l, r]: v)
    {
        r++;
        ans += min(l, fin) - last;
        last = l;
        fin = r;
    }
    ans += fin - last;
    return ans;
}

void gcd(ll a, ll b, ll &x, ll &y)
{
    if(b == 0) tie(x, y) = mp(1, 0);
    else
    {
        gcd(b, a%b, x, y);
        tie(x, y) = mp(y, x - (a/b)*y);
    }
}

ll mul(ll a, ll x, ll p)
{
    if(x==0) return 0;
    ll tmp = mul(a, x>>1, p);
    tmp = 2 * tmp % p;
    if(x&1) tmp = (tmp + a) % p;
    return tmp;
}

ll trans(ll x, ll n, ll j)
{
    ll a, b;
    gcd(n, j, b, a);
    a = (a%n + n)%n;
    return mul(a, x, n);
}

void proc(const int &TTT)
{
    cin>>n>>m>>k>>t;
    p = __gcd(n, 2*k);
    mini(t, n/p-1);
    for(int i=0; i<m; i++)
    {
        ll x;
        cin>>x;
        x--;
        M[x%p].pb(x);
    }
    for(auto &[x, v]: M)
    {
        ll l, r;
        vlll h;

        for(ll &a: v)
        {
            a = (a-x) / p;

            a = trans(a, n/p, 2*k/p);

            tie(l, r) = mp(a, (a+t)%(n/p));
            if(l < r) h.pb(mp(l, r));
            else
            {
                h.pb(mp(l, n/p-1));
                h.pb(mp(0, r));
            }
        }

        ans += solve(h);
    }
    cout<<ans;
}

int main()
{
//    freopen(TASK".inp", "r", stdin);
//    freopen(TASK".out", "w", stdin);
    ios_base::sync_with_stdio(0); cin.tie(0);
    int numTest = 1; //cin>>numTest;
    for(int i=1; i<=numTest; i++) proc(i);
    return 0;
}