题解

#include<iostream>
#include<vector>
using namespace std;
typedef long long ll;
typedef __int128 i128;

ll gcd(ll a, ll b) {
while(b) { a %= b; swap(a, b); }
return a;
}

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int c, T;
cin >> c >> T;
while(T--) {
ll d, n, m, t;
cin >> d >> n >> m >> t;
vector<ll> a(n), pre(n + 1, 0);
for(int i = 0; i < n; i++) {
cin >> a[i];
pre[i + 1] = (pre[i] + a[i]) % d;
}
ll total_sum = (pre[n] + d) % d;

    auto get_sum = [&](ll pos, ll len) -> ll {
        if(!len) return 0;
        ll full = len / n, rem = len % n;
        ll res = (i128)full * total_sum % d;
        if(pos + rem <= n)
            res = (res + pre[pos + rem] - pre[pos] + d) % d;
        else {
            res = (res + (pre[n] - pre[pos] + d) % d) % d;
            res = (res + pre[pos + rem - n]) % d;
        }
        return res;
    };

    ll S = t / m, R = t % m;
    ll d_step = (m - 1) % n;
    ll pos0 = n - 1;

    ll sum_full = 0;
    ll m_div_n = m / n;
    sum_full = (i128)(S % d) * (m_div_n % d) % d;
    sum_full = (i128)sum_full * total_sum % d;

    ll rem_m = m % n;
    if(S && rem_m) {
        ll g = gcd(d_step, n);
        ll T_cycle = n / g;
        ll cycle_sum = 0;
        for(ll k = 0; k < T_cycle; k++) {
            ll pos = (pos0 + (i128)k * d_step) % n;
            cycle_sum = (cycle_sum + get_sum(pos, rem_m)) % d;
        }
        ll full_cycles = S / T_cycle;
        ll rem_items = S % T_cycle;
        sum_full = (sum_full + (i128)full_cycles * cycle_sum) % d;
        for(ll k = 0; k < rem_items; k++) {
            ll pos = (pos0 + (i128)k * d_step) % n;
            sum_full = (sum_full + get_sum(pos, rem_m)) % d;
        }
    }

    ll sum_tail = 0;
    if(R) {
        ll pos = (pos0 + (i128)S * d_step) % n;
        sum_tail = get_sum(pos, R);
    }

    ll ans = (sum_full + sum_tail + d) % d;
    cout << ans << '\n';
}
return 0;

}