求问跨年赛 T2

#include<bits/stdc++.h>
using namespace std;
int lcm(int x, int y){
    int a = x, b = y;
    while(b){
        int temp = a % b;
        a = b;
        b = temp;
    }
    return x / a * y;
}
unsigned long long mul(unsigned long long a, unsigned long long b, unsigned long long mod){
    if(a == 0 || b == 0){
        return 0;
    }
    unsigned long long res = 0;
    a %= mod;
    while(b){
        if(b & 1){
            res = (res + a) % mod;
        }
        a = (a <<= 1) % mod;
        b >>= 1;
    }
    return res;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    unsigned long long d, n, m, t;
    cin >> d >> n >> m >> t;
    if(d == 1){
        cout << 0;
        return 0;
    }
    unsigned long long a[3005], b[3005];
    for(int i = 0; i < n; i++){
        cin >> a[i];
        a[i] %= d;
        b[i] = a[i];
    }
    int re = lcm(n, m);
    unsigned long long flag = 0;
    for(int i = 0; i < re; i++){
        if(i % m == 0){
            unsigned long long k = a[n - 1];
            for(int j = n - 1; j >= 1; j--){
                a[j] = a[j - 1];
            }
            a[0] = k;
        }
        flag = (flag + a[i % n]) % d;
    }
    flag = mul(flag, t / re, d);
    long long el = t % re;
    memcpy(a, b, n * sizeof(unsigned long long));
    for(int i = 0; i < el; i++){
        if(i % m == 0){
            unsigned long long k = a[n - 1];
            for(int j = n - 1; j >= 1; j--){
                a[j] = a[j - 1];
            }
            a[0] = k;
        }
        flag = (flag + a[i % n]) % d;
    }
    cout << flag;
}