CF 963A Alternating Sum

传送门

思路

  唉，我太弱了，什么都不会，好不容易做得来一道题，还是 A 题（所以不要瞧不起 A 题），结果还写错了（不知道为什么恰好在某个地方少写了个求余），唉，我太弱啦！

  显然对于第 i(i≥1) i ( i ≥ 1 ) $i \pod {i \ge 1}$ 个求和项来说，有：

  我们先假设 k≈n−−√ k ≈ n $k \approx \sqrt n$。显然我们可以将 cnti,cnti+k,cnti+2k,⋯ c n t i , c n t i + k , c n t i + 2 k , ⋯ $cnt_i, cnt_{i + k}, cnt_{i + 2k}, \cdots$ 合在一起算，因为它们的符号相同。这样我们只需要算 nk n k $\frac {n} {k}$ 次就算出来了，时间复杂度为 O(k+nk)≈O(n−−√) O ( k + n k ) ≈ O ( n ) $O(k + \frac {n} {k}) \approx O(\sqrt n)$。

  现在 k k $k$ 很小怎么办？我们只需要强行把那个序列变长，这样就能在根号时间内算出来了。最后可能还剩了一点无法对齐，直接计算即可，其长度不会超过新的序列的长，即 O(n−−√)$O(\sqrt{n})$$O(\sqrt n)$。因此算法的整体时间复杂度为 O(n−−√) O ( n ) $O(\sqrt n)$。

参考代码

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <cassert>
#include <cctype>
#include <climits>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <list>
#include <functional>
typedef long long LL;
typedef unsigned long long ULL;
using std::cin;
using std::cout;
using std::endl;
typedef int INT_PUT;
INT_PUT readIn()
{
    INT_PUT a = 0; bool positive = true;
    char ch = getchar();
    while (!(ch == '-' || std::isdigit(ch))) ch = getchar();
    if (ch == '-') { positive = false; ch = getchar(); }
    while (std::isdigit(ch)) { a = a * 10 - (ch - '0'); ch = getchar(); }
    return positive ? -a : a;
}
void printOut(INT_PUT x)
{
    char buffer[20]; int length = 0;
    if (x < 0) putchar('-'); else x = -x;
    do buffer[length++] = -(x % 10) + '0'; while (x /= 10);
    do putchar(buffer[--length]); while (length);
}

const int mod = int(1e9) + 9;
const int maxn = int(1e5) + 5;
int n, a, b, k;
char seq[maxn];

LL power(LL x, int y)
{
    LL ret = 1;
    while (y)
    {
        if (y & 1) ret = ret * x % mod;
        x = x * x % mod;
        y >>= 1;
    }
    return ret;
}

void run()
{
    n = readIn();
    a = readIn();
    b = readIn();
    k = readIn();
    for (int i = 0; i < k; i++)
    {
        char ch = getchar();
        while (ch != '+' && ch != '-')
            ch = getchar();
        seq[i] = ch;
    }
    int sqrtN = std::sqrt(n);
    int ratio = std::max<double>(1, (double)sqrtN / k);

    int block = k * ratio;
    int times = (n + 1) / block;
    int remain = (n + 1) - block * times;

    LL inva = power(a, mod - 2);
    LL pwrinva = power(inva, block);
    LL pwrb = power(b, block);
    LL cntA = power(a, n), cntB = 1;
    LL cnt = 0;
    for (int i = 0; i < times; i++)
    {
        cnt = (cnt + cntA * cntB) % mod;
        cntA = cntA * pwrinva % mod;
        cntB = cntB * pwrb % mod;
    }
    LL factor = inva * b % mod;
    LL ans = 0;
    for (int i = 0; i < block; i++)
    {
        ans += cnt * (seq[i % k] == '-' ? -1 : 1) + mod;
        ans %= mod;
        cnt = cnt * factor % mod;
    }
    if (remain)
    {
        cnt = power(a, n - block * times) * power(b, block * times) % mod;
        for (int i = 0; i < remain; i++)
        {
            ans += cnt * (seq[i % k] == '-' ? -1 : 1) + mod;
            ans %= mod;
            cnt = cnt * factor % mod;
        }
    }
    printOut(ans);
}

int main()
{
    run();
    return 0;
}