-数论-逆元- [洛谷 P4881]hby与tkw的基情

题目描述

Link

Solution

先把题目转换为人话：

给定一个数字 $n$，求：

$$\sum^{\lfloor \frac{n+1}{2} \rfloor}_{i=1}(2 \times i-1) \times 26 ^ i​$$

对于求等差数列平方和等比数列的积的前 $n$ 项和我们可以用错位相减法。

设 $k=\lfloor \frac{n+1}{2} \rfloor, S _ k=\sum^{\lfloor \frac{n+1}{2} \rfloor}_{i=1}(2 \times i-1) \times 26 ^ i​$。

则：$26 \times S_k=\sum^{\lfloor \frac{n+1}{2} \rfloor}_{i=1}(2 \times i-1) \times 26 ^ {i+1}​$

所以：

$$\begin{align}25 \times S_k &= 26 \times S_k-S_k \\\ &= \sum^{\lfloor \frac{n+1}{2} \rfloor}_{i=1}(2 \times i-1) \times 26 ^ {i+1}-\sum^{k}_{i=1}(2 \times i-1) \times 26 ^ i \\\ &= (2\times k-1)\times 26^k -\frac{2 \times 26 \times(26^k-1)}{25}-26 \end{align}$$

再用快速幂和逆元随便瞎搞搞就可以了。

Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MOD 1000000007
#define ll long long
int T;
ll n;
ll qpow(ll a, ll b, ll p) {
    ll res = 1;
    while (b) {
        if (b & 1) res = (res * a) % p;
        b >>= 1;
        a = (a * a) % p;
    }
    return res % p;
}
int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%lld", &n);
        n = (n + 1) / 2;
        printf("%lld\n", (((2 * n - 1) * qpow(26, n + 1, MOD) % MOD - 26 * (qpow(26, n, MOD) - 1) % MOD * qpow(25, MOD - 2, MOD) * 2 % MOD + 26 + MOD) % MOD) * qpow(25, MOD - 2, MOD) % MOD);
    }
}