「Ynoi2015」盼君勿忘

发表于 | 分类于 | | 浏览量： 次

Ynoi最有趣了个鬼啊！

传送门

洛谷P5072

题解

首先这是一道Ynoi的题，并且数据范围非常友好，直接上莫队。

但是这题的模数并不固定，考虑如何处理。

首先考虑一个数$x$，如果他在区间$[L,R]$内出现了$k$次，那么就一共有$2^{R-L+1}-2^{R-L+1-K}$个子序列包含$x$。

不难发现，出现次数相同的数可以一起处理。

而且，不同的出现次数是$O(\sqrt{n})$级别的。设出现了$k$次的数的和为$sum$，那么这些出现次数为$k$的数对答案的贡献就是$sum\cdot(2^{R-L+1}-2^{R-L+1-K})$。

所以，我们可以通过莫队来维护每一种出现次数的数的和，并用一个类似链表的东西来维护当前存在的不同的出现次数。

考虑如何在每次的模数变化之后快速计算$2^k \mod p$。

可以用一个类似于BSGS的算法，先在$O(\sqrt n)$的复杂度内预处理出$2^1,2^2,\cdots,2^{\sqrt n} \mod p$以及$2^{\sqrt n},2^{2\sqrt n},\cdots 2^{n} \mod p$的值，然后每次就可以$O(1)$计算$2^k \mod p$了。

所以在莫队的过程中，对于每个询问先预处理$2$的幂，然后更新出现次数的信息，再遍历每种出现次数计算贡献即可。

时间复杂度$O(n\sqrt n)$。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=100005;
int n,m,a[maxn],Area[maxn],S,ans[maxn],nxt[maxn],pre[maxn],til,cnt[maxn],Pow[400][2];LL sum[maxn];
inline int read()
{
	int ret=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=getchar();}
	return ret*f;
}
inline int QP(int a,int b,int TT)
{
	int ret=1,w=a;
	while(b)
	{
		if(b&1) ret=(LL)ret*w%TT;
		w=(LL)w*w%TT;b>>=1;
	}
	return ret;
}
struct Query
{
	int L,R,p,id;
	bool operator < (const Query& b)const{return Area[L]<Area[b.L]||(Area[L]==Area[b.L]&&((Area[L]&1)?R>b.R:R<b.R));}
}Q[maxn];
inline void Ins(int x){nxt[til]=x;pre[x]=til;til=x;}
inline void Del(int x){x==til?til=pre[x]:nxt[pre[x]]=nxt[x],pre[nxt[x]]=pre[x];nxt[x]=pre[x]=0;}
inline void upt(int x,int del){sum[cnt[x]]-=x;if(!sum[cnt[x]]) Del(cnt[x]);cnt[x]+=del;if(!sum[cnt[x]]) Ins(cnt[x]);sum[cnt[x]]+=x;}
inline void init(int TT)
{
	Pow[0][0]=Pow[0][1]=1;
	int ps=QP(2,320,TT);
	for(int i=1;i<=320;i++)
	{
		Pow[i][0]=(LL)Pow[i-1][0]*2%TT;
		Pow[i][1]=(LL)Pow[i-1][1]*ps%TT;
	}
}
inline int CP(int x,int TT){return (LL)Pow[x%320][0]*Pow[x/320][1]%TT;}
inline void Solve()
{
	int L=1,R=0;
	for(int i=1;i<=m;i++)
	{
		init(Q[i].p);
		while(R<Q[i].R) upt(a[++R],1);
		while(L>Q[i].L) upt(a[--L],1);
		while(R>Q[i].R) upt(a[R--],-1);
		while(L<Q[i].L) upt(a[L++],-1);
		int po=nxt[0];
		while(po)
		{
			ans[Q[i].id]=(ans[Q[i].id]+(LL)sum[po]*(CP(R-L+1,Q[i].p)-CP(R-L+1-po,Q[i].p)+Q[i].p)%Q[i].p)%Q[i].p;
			po=nxt[po];
		}
	}
}
int main()
{
	n=read();m=read();S=sqrt(n)+1e-10;
	for(int i=1;i<=n;i++) a[i]=read();
	for(int i=1;i<=n;i++) Area[i]=(i-1)/S+1;
	for(int i=1;i<=m;i++){Q[i].L=read();Q[i].R=read();Q[i].p=read();Q[i].id=i;}
	sort(Q+1,Q+1+m);Solve();
	for(int i=1;i<=m;i++)
		printf("%d\n",ans[i]);
	return 0;
}