题解 | #Alternating Sum#

【Alternating Sum】 由上图可知，可以将求和式${\sum }_{i=0}^n{s}_i{a}^{n-i}{b}^i\backslash sum\_\{i=0\}^ns\_ia^\{n-i\}b^i$∑i=0n​si​an−ibi分成$cnt=(n+1)/kcnt=(n+1)/k$cnt=(n+1)/k个小段，每一段内的求和值为$t\left[i\right]=t[i-1]\times a^{-k}{b}^k,t\left[1\right]={\sum }_{i=0}^{k-1}{s}_i{a}^{n-i}{b}^{i}t[i]=t[i-1]\backslash times\; a^\{-k\}b^k,t[1]=\backslash sum\_\{i=0\}^\{k-1\}s\_ia^\{n-i\}b^i$t[i]=t[i−1]×a−kbk,t[1]=∑i=0k−1​si​an−ibi，可以用等比数列前$nn$n项和的公式求出，公比为$a^{-k}{b}^{k}a^\{-k\}b^k$a−kbk。

注意：当公比为1时，不能用等比数列前$nn$n项和来计算，需要特判。

对于最后剩下的长度不足$kk$k​的一段，可以直接暴力求解。

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

const int N = 1e5 + 10;
const int mod = 1e9 + 9;

int n, a, b, k, pre[N];
int res, w;
char s[N];

int power(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

int inv(int x) { return power(x, mod - 2); }

signed main() {
    scanf("%lld%lld%lld%lld", &n, &a, &b, &k);
    scanf("%s", s);
    w = power(b, k) * inv(power(a, k)) % mod;
    for (int i = 0; i < k; i++) {
        if (i != 0) pre[i] = pre[i - 1];
        if (s[i] == '+') {
            pre[i] = (pre[i] + power(a, n - i) * power(b, i) % mod) % mod;
        } else {
            pre[i] = (pre[i] - power(a, n - i) * power(b, i) % mod + mod) % mod;
        }
    }
    int cnt = (n + 1) / k;
    if (w == 1) {    // 特判分母为0的情况
        res = pre[k - 1] * cnt % mod;
    } else {    // 等比数列前cnt项和
        res = pre[k - 1] * ((power(w, cnt) - 1 + mod) % mod) % mod *
              inv((w - 1 + mod) % mod) % mod;
    }

    res = (res + pre[n - (n + 1) / k * k] * power(w, (n + 1) / k) % mod) % mod;

    printf("%lld", res);

    return 0;
}