数列求和
题目背景:
11.07 NOIP模拟T1
分析:递推
作为开场T1,还真是有点脑洞······
考虑我们定义f[i]为以i结尾的所有子段积的和,那么考虑f[i + 1]与f[i]的关系,显然所有以i结尾的子段都可以在后面加上一个a[i + 1], 并且a[i + 1]还能单独成为一个子段,那么显然f[i + 1] = (f[i] + 1) * a[i + 1],最后的ans为f[i]的和,考虑到最后两个点mod <= 1018,相乘就可以爆掉long long,那么加个快速乘就好了。
Source:
/*
created by scarlyw
*/
#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <string>
#include <cstring>
#include <cctype>
#include <vector>
#include <queue>
#include <set>
const int MAXN = 100000 + 10;
long long n, mod, x, ans;
long long f[MAXN];
inline long long ksc(long long a, long long b) {
long long ans = 0;
for (; b; b >>= 1, a = (a + a) % mod)
if (b & 1) ans = (ans + a) % mod;
return ans;
}
int main() {
// freopen("sum.in", "r", stdin);
// freopen("sum.out", "w", stdout);
std::cin >> n >> mod;
for (int i = 1; i <= n; ++i) std::cin >> x, f[i] = ksc(f[i - 1] + 1LL, x);
for (int i = 1; i <= n; ++i) ans = (ans + f[i]) % mod;
std::cout << ans;
return 0;
}