题解 P5072 【[Ynoi2015]盼君勿忘】
rui_er
·
·
题解
2020.1.4 更新：代码被人 hack 了，是光速幂只处理到 \sqrt{n} 导致剩余部分未定义的错误，已经修改，求再次审核。
给定一个序列，每次查询一个区间 [l,r] 中所有子序列分别去重后的和 s\bmod{p} 的结果。
乍一看好像不太可做，仔细分析发现有点规律：
在一个长度为 a 的序列中，一个数出现次数为 b。则有 2^{a-b} 个子序列不包含该元素，它的贡献是 2^a-2^{a-b}。
问题转化为如何快速求出每一个数的贡献值。
我们使用**莫队**记录**双向链表**（建议手写），维护每个数分别的出现次数，下标表示数，内容为出现次数。则这个链表的元素个数大致在 $\sqrt{n}$ 级别。在跳到当前区间后，枚举维护的链表，对于每个元素分别算出贡献值后相加即可。
还剩下最后一个问题：如何快速求出 $2^k$？普通的快速幂可能做不到，因为带一只 $\log$，容易被卡。果断选用**光速幂**。
光速幂是什么呢？就是一种 $\mathcal{O(\sqrt{n})}$ 预处理、$\mathcal{O(1)}$ 查询的，求特定底数的幂的快速方法。具体方案是：预处理 $2^1,2^2,\cdots,2^{\sqrt{n}}$ 和 $2^{\sqrt{n}},2^{2\times\sqrt{n}},\cdots,2^n$，然后根据商和余数即可 $\mathcal{O(1)}$ 求出结果。
---
代码：
```cpp
//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1e5+5;
ll n, m, a[N], SIZE, cnt[N], s[N], ans[N];
#define whichBlock(x) (\
(x-1)/SIZE+1\
)
struct Query {
ll l, r, p, id;
Query(ll a=0, ll b=0, ll c=0, ll d=0) : l(a), r(b), p(c), id(d) {}
~Query() {}
friend bool operator < (const Query &a, const Query &b) {
ll x = whichBlock(a.l), y = whichBlock(b.l);
if(x == y) return a.r < b.r;
return x < y;
}
}q[N];
struct myList {
struct Node {
ll pre, nxt;
Node(ll a=0, ll b=0) : pre(a), nxt(b) {}
~Node() {}
}nd[N];
ll tot;
myList(ll a=0) : tot(a) {}
~myList() {}
void insert(ll x) {
nd[tot].nxt = x;
nd[x].pre = tot;
tot = x;
}
void erase(ll x) {
if(x != tot) {
nd[nd[x].pre].nxt = nd[x].nxt;
nd[nd[x].nxt].pre = nd[x].pre;
}
else {
nd[nd[x].pre].nxt = 0;
tot = nd[x].pre;
}
nd[x] = Node();
}
}lst;
namespace qpow {
ll pow1[N], pow2[N];
void initPow(ll mod) {
pow1[0] = pow2[0] = 1;
for(ll i=1;i<=SIZE+5;i++) pow1[i] = pow1[i-1] * 2 % mod;
for(ll i=1;i<=SIZE+5;i++) pow2[i] = pow2[i-1] * pow1[SIZE] % mod;
}
ll calc(ll x, ll mod) {return pow1[x%SIZE]*pow2[x/SIZE]%mod;}
}
void upd(ll x, ll k) {
if(!(s[cnt[a[x]]]-=a[x])) lst.erase(cnt[a[x]]);
if(!s[cnt[a[x]]+=k]) lst.insert(cnt[a[x]]);
s[cnt[a[x]]] += a[x];
}
int main() {
scanf("%lld%lld", &n, &m);
SIZE = sqrt(n);
for(ll i=1;i<=n;i++) scanf("%lld", &a[i]);
for(ll i=1;i<=m;i++) scanf("%lld%lld%lld", &q[i].l, &q[i].r, &q[i].p), q[i].id = i;
sort(q+1, q+1+m);
ll l = 1, r = 0;
for(ll i=1;i<=m;i++) {
// printf("QUERY #%d: id=%d l=%d r=%d p=%d\n", i, q[i].id, q[i].l, q[i].r, q[i].p);
qpow::initPow(q[i].p);
while(l > q[i].l) upd(--l, 1);
while(r < q[i].r) upd(++r, 1);
while(l < q[i].l) upd(l++, -1);
while(r > q[i].r) upd(r--, -1);
for(ll j=lst.nd[0].nxt;j;j=lst.nd[j].nxt) {
// printf("LIST POSITION: %d\n", j);
ll _1 = qpow::calc(r-l+1, q[i].p);
ll _2 = qpow::calc(r-l+1-j, q[i].p);
ll _3 = ((_1 - _2) * s[j] + q[i].p) % q[i].p;
ans[q[i].id] = (ans[q[i].id] + _3 + q[i].p) % q[i].p;
}
}
for(ll i=1;i<=m;i++) printf("%lld\n", ans[i]);
return 0;
}
```