记录编号	616239	评测结果	AAAAAAAAAA
题目名称	数列求和	最终得分	100
用户昵称	RpUtl	是否通过	通过
代码语言	C++	运行时间	13.557 s
提交时间	2026-06-02 20:30:55	内存使用	14.91 MiB

#include <bits/stdc++.h>
using namespace std;
const int N = 2005;
typedef long long ll;
ll C[N][N], s, a, k, val[N], bas[N], res[N];
int mod;
ll ksm(ll a, ll b) {
    a %= mod;
    ll ans = 1;
    while (b) {
        if (b & 1) {
            ans = (ans * a) % mod;
        }
        a = (a * a) % mod;
        b >>= 1;
    }
    return ans;
}
void solve(ll n) {
    if (n <= 2000) {
        for (int i = 1; i <= n; i++) {
            bas[i] = 1;
        }
        for (int i = 0; i <= k; i++) {
            ll prd = a;
            for (int j = 1; j <= n; j++) {
                (val[i] += bas[j] * prd % mod) %= mod;
                (bas[j] *= j) %= mod, (prd *= a) %= mod;
            }
        }
        return;
    } else {
        solve(n / 2);
        ll m = (n / 2) % mod;
        if (!(n & 1)) {
            ll P = ksm(a, n / 2);
            for (int i = 0; i <= k; i++) {
                ll prd = 1;
                for (int j = 0; j <= i; j++) {
                    res[i] += C[i][j] * prd % mod * val[i - j] % mod;
                    prd = (prd * m) % mod;
                }
                res[i] = (res[i] % mod * P % mod + val[i]) % mod;
            }
        } else {
            ll P = ksm(a, n / 2 + 1), Q = P;
            for (int i = 0; i <= k; i++) {
                ll prd = 1;
                for (int j = 0; j <= i; j++) {
                    res[i] += C[i][j] * prd % mod * val[i - j] % mod;
                    prd = (prd * (m + 1)) % mod;
                }
                res[i] = (res[i] % mod * P % mod + val[i]) % mod;
                res[i] = (res[i] + Q) % mod, Q = (Q * (m + 1)) % mod;
            }
        }
        for (int i = 0; i <= k; i++) {
            val[i] = res[i];
            res[i] = 0;
        }
    }
    return;
}
int main() {
    freopen("oeis.in", "r", stdin);
    freopen("oeis.out", "w", stdout);
    scanf("%lld %lld %lld %d", &s, &a, &k, &mod);
    for (int i = 0; i <= k; i++) {
        C[i][0] = C[i][i] = 1;
        for (int j = 1; j < i; j++) {
            C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
        }
    }
    solve(s);
    printf("%lld\n", val[k]);
    return 0;
}