### Sequence

#### 代码

#include <bits/stdc++.h>
#define md 1000000007
#define maxn 500100
using namespace std;
int f[25][maxn],c[25][maxn],n,m;
void inc(int &x,int y){x=x+y>=md?x+y-md:x+y;}
void dec(int &x,int y){x=x-y<0?x-y+md:x-y;}
int main(){
freopen("sequence.in","r",stdin);
freopen("sequence.out","w",stdout);
scanf("%d%d",&n,&m);
for (int i=0;i<=n+20;i++){
c[0][i]=1;
for (int j=1;j<=min(20,i);j++)
c[j][i]=(c[j-1][i-1]+c[j][i-1])%md;
}
for (int i=1;i<=m;i++){
int x,y,k;
scanf("%d%d%d",&x,&y,&k);
inc(f[k][x],1);
for (int j=0;j<=k;j++)
dec(f[k-j][y+1],c[j][y-x+j]);
}
for (int k=20;~k;k--) for (int i=1;i<=n;i++)
inc(f[k][i],(f[k][i-1]+f[k+1][i])%md);
for (int i=1;i<=n;i++)
printf("%d\n",f[0][i]);
}


### Bomb

#### 思路

$$g_i=2^{\binom{i}{2}} – \sum_{j=1}^{i-1}2^{\binom{i-j}{2}}\binom{i-1}{j-1}g_j$$

$$f_{i,k}=\sum_{j=1}^{\min (i,k)}f_{i-j,k}\binom{i-1}{j-1}g_j$$

#### 代码

#include <bits/stdc++.h>
#define mod 998244353
#define ll long long
#define maxn 2010
#define fop(i,x,y) for (int i=x;i<=y;++i)
#define foc(i,x,y) for (int i=x;i>=y;--i)
void inc(int &x,int y){x=x+y>=mod?x+y-mod:x+y;}
void dec(int &x,int y){x=x<y?x-y+mod:x-y;}
using namespace std;
int jc[maxn],ny[maxn];
int ksm(int a,int b){
int res=1;
while(b){
if (b&1) res=1ll*res*a%mod;
a=1ll*a*a%mod;b>>=1;
}
return res;
}
void init(int x){
jc[0]=1;
fop(i,1,x) jc[i]=(1ll*jc[i-1]*i)%mod;
ny[x]=ksm(jc[x],mod-2);
foc(i,x,1) ny[i-1]=(1ll*ny[i]*i)%mod;
}
int c(int n,int k){
if (!k) return 1;
return 1ll*jc[n]*ny[k]%mod*ny[n-k]%mod;
}
int f[maxn],g[maxn],p[maxn],n,k;
int cag(){
fop(i,1,n){
g[i]=p[i]=ksm(2,(i-1)*i/2);
fop(j,1,i-1)
dec(g[i],1ll*g[j]*p[i-j]%mod*c(i-1,j-1)%mod);
}
}
int caf(int k){
f[0]=1;
fop(i,1,n){
f[i]=0;
fop(j,1,min(k,i))
inc(f[i],1ll*g[j]*f[i-j]%mod*c(i-1,j-1)%mod);
}
return f[n];
}
int main(){
scanf("%d%d",&n,&k);
init(n);cag();
int ans=caf(k);
dec(ans,caf(k-1));
printf("%d",ans);
}


### Queue

#### 题目描述

Hack 国的居民人人都是 OI 大师，Hometown 得知便赶紧来到 Hack 国学习。可想要进入 Hack 国并不是件容易的事情，首先就必须通过 Hack 国海关小 B 的

• $1 \ l \ r$，表示将区间 $[l, r]$ 轮转一次，具体来说，$a_l, a_{l+1}, a_{l+2}, · · · , a_{r−1}, a_r$ 经过一次轮转之后，会变为 $a_r, a_l, a_{l+1}, · · · , a_{r−1}$；
• $2 \ l \ r \ k$，询问区间 $[l, r]$ 内 $a_i = k$ 的个数。

#### 代码

#include <bits/stdc++.h>
#define maxn 100100
using namespace std;
int avalen,cnt[320][maxn];
int n,m,tot=1;
deque<int>a[320];
void rever(int l=1,int r=1){
scanf("%d%d",&l,&r);
int pol=(l-1)/avalen+1,curl=(l-1)%avalen;
int por=(r-1)/avalen+1,curr=(r-1)%avalen;
int temp=a[por][curr];
a[por].erase(a[por].begin()+curr);
cnt[por][temp]--;
a[pol].insert(a[pol].begin()+curl,temp);
cnt[pol][temp]++;
for (int k=pol;k<por;k++){
int temp=a[k].back();
cnt[k][temp]--;
a[k].pop_back();
a[k+1].push_front(temp);
cnt[k+1][temp]++;
}
}
void query(int l=1,int r=1,int k=1){
int res=0;
scanf("%d%d%d",&l,&r,&k);
int pol=(l-1)/avalen+1,curl=(l-1)%avalen;
int por=(r-1)/avalen+1,curr=(r-1)%avalen;
deque<int>::iterator cur;
if (pol==por){
for (cur=a[pol].begin()+curl;cur<=a[pol].begin()+curr;cur++)
res+=(*cur==k);
printf("%d\n",res);
return;
}
for (cur=a[pol].begin()+curl;cur!=a[pol].end();cur++)
res+=(*cur==k);
for (cur=a[por].begin();cur<=a[por].begin()+curr;cur++)
res+=(*cur==k);
for (int pos=pol+1;pos<por;pos++)
res+=cnt[pos][k];
printf("%d\n",res);
}
int main(){
scanf("%d%d",&n,&m);
avalen=sqrt(n);
for (int i=1,cur=1,x;i<=n;i++,cur++){
scanf("%d",&x);
if (cur>avalen) cur=1,tot++;
a[tot].push_back(x);
cnt[tot][x]++;
}
for (int i=1,op;i<=m;i++){
scanf("%d",&op);
if (op==1) rever();
if (op==2) query();
}
}