世纪诈骗题
首先,所有子序列分别去重的和的意思是什么?
令可重集 \(S\) 为序列 \(a_l, a_{l+1}\dots a_r\) 的所有子序契合。
假设我们有一个序列 \(T\),对 \(T\) 去重后变为 \(T'\),令 \(f(T)=\sum_{x \in T'} x\),则题目所求为 \(\sum_{T \in S} f(T)\)。
显然我们不能把所有的子序列都弄出来,那样就是 \(2^{r-l+1}\) 级别的,考虑每种数的贡献。为什么是每种而不是每个呢?因为去重后我们就丢失了原来的下标(意思就是多个随便选),贡献不好统计。
那么这种数的贡献应该是多少呢?
设其出现次数为 \(cnt_x\),只要出现了这种数贡献 +1,那么应该就是总子序列数 - 没有出现这种数的子序列数。
就是 \(2^{r-l+1}-2^{r-l+1-cnt_x}\),最后还要乘上这个数本身,即 \(x(2^{r-l+1}-2^{r-l+1-cnt_x})\)。
你发现 \(cnt\) 相同的 \(x\) 珂以合并到一起,然后你实际上就是维护一个 \(sum_{cnt}\),和 \(2^{r-l+1-cnt}\) 这么个玩意。
首先把询问简单化,如果只询问全局,把底数从 \(2\) 变成 \(3 \dots 114514\) 之类的,怎么做?
其实有个很简单的东西:暴力。
为什么?高斯告诉我们 \(1+2+\dots \sqrt n \to n\),所以不同的 \(cnt\) 最多 \(\sqrt n\) 种,所以复杂度肥肠正确。
转回到原题,我们需要快速的整出 \(cnt\) 和对应的 \(sum\),注意到这是对区间信息的一个整体查询,又没有强制在线,所以直接莫队。
在移动的时候,会产生/消失某个 \(cnt\),我们需要一个能支持 单个插入/删除 和 整体遍历 的数据结构,显然就是链表了。
复杂度 \(O(n\sqrt m + m\sqrt n)\),非常好写。
Code:
const int N=1e5+5;
const int R=320;//sqrt N
struct Edge{int lst, nxt;}d[N];//上一个,下一个,下标 出现次数
int n, m, mi1[R], mi2[R], a[N];
int Mp[N], head, vis[N];
long long sum[N];
int Mod, dis, sq, ans[N];
inline int add(int x, int y){return (x+y)%Mod;}
inline int mul(int x, int y){return 1ll*x*y%Mod;}
void pre(int mo){
Mod=mo;mi1[0]=mi2[0]=1;
for(int i=1; i<=sq; i++) mi1[i]=add(mi1[i-1], mi1[i-1]);
mi2[1]=mi1[sq];
for(int i=2; i*sq<=n; i++) mi2[i]=mul(mi2[i-1], mi2[1]);
return ;
}
int ksm(int b){
return 1ll*mi2[b/sq]*mi1[b%sq]%Mod;
}
struct Query{
int x, y, P, id;
bool operator < (const Query &S) const{
if(x/dis!=S.x/dis) return x/dis<S.x/dis;
return y<S.y;
}
void get(int s){x=read(), y=read(), P=read(), id=s;}
}Q[N];
inline void doit(int x, int v){
#define pos Mp[a[x]]
if(pos){
sum[pos]-=a[x];
if(--vis[pos]==0){
if(pos==head) head=d[pos].lst;
else d[d[pos].nxt].lst=d[pos].lst;
d[d[pos].lst].nxt=d[pos].nxt;
}
}
pos+=v;
if(pos){
sum[pos]+=a[x];
if(++vis[pos]==1){
d[pos].lst=head;
d[head].nxt=pos;head=pos;
d[pos].nxt=0;
}
}
#undef pos
}
inline void add(int x){doit(x, 1);}
inline void del(int x){doit(x, -1);}
inline int mis(int x, int y){return x<y?x-y+Mod:x-y;};
inline void move(int &l, int &r, int x, int y){
while(l>x) add(--l);
while(r<y) add(++r);
while(r>y) del(r--);
while(l<x) del(l++);
return ;
}
signed main(){
n=read(), m=read();if(!m) return 0;dis=n/sqrt(m);sq=sqrt(n);
for(int i=1; i<=n; i++) a[i]=read();
for(int i=1; i<=m; i++) Q[i].get(i);
sort(Q+1, Q+m+1);int L=1, R=0;
for(int i=1; i<=m; i++){
pre(Q[i].P);
move(L, R, Q[i].x, Q[i].y);
int pwp=Q[i].y-Q[i].x+1, qwq=ksm(pwp);
for(int s=head; s; s=d[s].lst)
ans[Q[i].id]=add(ans[Q[i].id], mul(sum[s]%Mod, mis(qwq, ksm(pwp-s))));
ans[Q[i].id]=(ans[Q[i].id]%Mod+Mod)%Mod;//(2^len-2^{len-k})*x
}
for(int i=1; i<=m; i++) printf("%d\n", ans[i]);
return 0;
}
标签:cnt,勿忘,int,sum,Ynoi2015,sqrt,盼君,序列,Mod
From: https://www.cnblogs.com/sizeof127/p/16609231.html