题意：给出 \(l,n,mod\) 和一个序列 \(a\)，表示现在有一个 \(l\) 长由 \(a,b\) 构成的字符串，要求 \(a_1,a_2\cdots a_n\) 长的前缀都是回文串，问有多少种。\(l\le 10^9,n\le 5\times 10^5\)。
做法：
首先算个数就是先算连通块个数，然后就可以快速幂直接计算。重点是怎么计算。
我们先考察两个限制 \(x>y\)，如果 \(x\ge 2y\)，那么意味着 \((2y,x-2y]\) 这一部分没有限制了，只有单独的这一部分要回文，那么有 \(\lceil\frac{x}{2}\rceil-y\) 的贡献。
否则考虑 \(x<2y\)，那么我们可以瞎对称两下，你会发现我们把 \(x\) 替换成 \(2y-x\) 具有等价的效果，然后我们去写几项看一看，会发现 \((x,y)\) 在有数比第三大数 \(z\) 小之前，每次等同于把两个数同时减掉 \(d=y-x\)，那么我们就可以除法加速这个过程，然后再判断最后的 \(x,2y\) 的关系，如果 \(x\ge 2y\) 那么有贡献，否则我们令 \(x,y\) 都减去 \(d\) 再扔回去。
但是这样有个问题，我们该怎么样保证扔回去的次数并不多呢？我们考虑当我们扔回去之后，大概序列从大到小会形如一个 \(x,z,y\) 的形态，考虑 \(z\) 的位置，如果 \(z\ge \frac{x+y}{2}\)，那么最大值减次大值之差会减半，否则如果 \(2z\le x\)，显然 \(z,y\) 也满足差减半，如果还是丢回去的情况，那应该形如 \(z,y,2z-x\)，发现此时 \(y,z\) 相比于 \(x,y\) 会减半，可以在数轴上画一画讨论一下，所以这个扔回去的操作是只有 \(O(\log n)\) 次的。
所以直接用堆维护一下就可以，复杂度 \(O((n+\log n)\log n)\)。
代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 5e5 + 5;
int n, m, l, a[maxn], ans;
priority_queue<int> q;
int qpow(int x, int k, int p) {int res = 1;while(k) {if(k & 1)res = res * x % p;x = x * x % p, k >>= 1;}return res;
}
signed main() {cin >> l >> n >> m;for (int i = 1; i <= n; i++)cin >> a[i], q.push(a[i]);q.push(0);ans += l - q.top();while(!q.empty()) {int x = q.top(); q.pop();if(x == 0)break;while(q.top() == x)q.pop();// cout << x << " " << q.empty() << endl;int y = q.top();if(x >= 2 * y) {ans += (x + 1) / 2 - y;continue;}q.pop();//cout << y << endl;int z = q.top();int d = (y - z) / (x - y), t = x - y;x -= t * d, y -= t * d;if(x >= 2 * y) {ans += (x + 1) / 2 - y;q.push(y);continue;}else {cout << x << " " << y << endl;q.push(x - t), q.push(y - t);continue;}}cout << qpow(2, ans, m) << endl;return 0;
}