Sequence
题目描述
小 F 是一位 Hack 国的居民，他生活在一条长度为 $n$ 的街道上，这个街道上总共有 $n$ 个商店。每个商店里售卖着不同的 Hack 技能包，每个商店本身也会有个便利值。初始时，每个商店的便利值均为 0。每一天，街道上都会有一些商店优化改造。
具体来说，对于每一天，优化改造的商店都是一个连续的区间 $l ∼ r$，每次优化改造也会有一个优化参数 $k$。对于所有 $l ≤ i ≤ r$ ，第 $i$ 个商店的便利值会增加 $\binom {i+k-l}{k}$。
小 F 想知道，$m$ 天之后，每个商店的便利值分别是多少。由于小 F 并不喜欢高精度，因此你只需要输出便利值对 $10^9 + 7$ 取模的结果。
思路
可以发现组合数有一个简单的性质，即 $\binom {n}{k} = \binom {n-1}{k} + \binom {n-1}{k-1}$，我们可以从这个式子中获得启发。考虑一个下标从 $0$ 开始的数列，这个数列的每个数均为 $1$。容易发现这个数列 $k$ 阶前缀和的第 $i$ 项即为 $\binom {k+i}{k}$。（经典的矩形最短路径数量问题的方案数列）
对于这个数列，维护这个数列的 $k$ 阶差分。对于一次修改操作，我们只需要在各阶差分数组上修改，最后做一遍 $k$ 阶的前缀和即可。注意差分数组上修改时，区间边界要相应地减掉一些值。时间复杂度 $O(nk)$，期望得分 $100pts$。
代码
#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
题目描述
常数国与 Hack 国近年来战火纷飞。
常数国共有 n 个城市，每两个城市之间均有一条交通线联通。如今常数国遭到 Hack 国的重创，岌岌可危。Hack 国国王小 K 决定轰炸常数国的交通线，对常数国发起最后的攻击。
面对危难之时，常数国国王决定更换首都。在 Hack 国的轰炸结束之后，常数国的领土将会分成若干个联通块。常数国的首都，将会从联通块大小最大的联通块中，随机选择一个城市，作为首都。
小 K 得知了常数国的应对方案之后，他想知道，Hack 国有多少种不同的轰炸方案，使得常数首都所在的联通块大小恰好为 k。两种轰炸方案是不同的，当且仅当一条交通线在一种方案中存在，在另一种方案中被轰炸。由于方案数可能很大，你需要输出方案数对 998244353 取模的结果。
思路
我们先考虑 $k=n$ 的情况，也就是 $n$ 个点的带标号连通图个数。设 $g_i$ 为共有 $i$ 个点的情况，我们容斥一下，求出不连通的情况，可以得到
$$g_i=2^{\binom{i}{2}} – \sum_{j=1}^{i-1}2^{\binom{i-j}{2}}\binom{i-1}{j-1}g_j$$
上式中，$2^{\binom{i}{2}}$ 枚举所有可能的边的状态。现在我们只关心 1 号节点，假设它所在的联通块大小为 $j$，那么我们要从剩下的 $i-1$ 个点中选出 $j-1$ 个点与之相连，剩下 $i-j$ 个点不与选出的这 $j$ 个点连边，那么方案数为 $2^{\binom{i-j}{2}}\binom{i-1}{j-1}g_j$。时间复杂度 $O(n^2)$。
现在我们考虑不受限制的 $k$。如果我们令 $f_{i,j}$ 为共有 $i$ 个点，其中最大联通块大小为 $j$，我们需要 $O(n^2)$ 来转移，时间复杂度为 $O(n^3)$。但是，如果我们令 $f_i$ 为 $i$ 个点的图中最大联通块大小不大于 $k$ 的方案，那么我们可以枚举与 1 号点相连的点的个数 $j$，得到转移方程
$$f_{i,k}=\sum_{j=1}^{\min (i,k)}f_{i-j,k}\binom{i-1}{j-1}g_j$$
分别求出 $f_k, f_{k-1}$，答案为两者之差。在上个式子中不需要枚举 $k$，时间复杂度 $O(n^2)$。
代码
#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 的
考验。小 B 觉得 Hometown 比较菜，于是就扔了一道小水题给 Hometown。
给定一个长度为 $n$ 的数列 $a_i$，接下来会对这个序列进行 $m$ 次操作。操作类型分为以下两种：
- $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$ 的个数。
可惜 Hometown 还是不会做，他只能期待你能解决这个问题了。
思路
一开始我把题目看成了区间翻转，就花了很久写了一个 $Splay$，发现真相以后我就决定这场比赛不交题了。
发现每次修改其实是将 $a_r$ 插入到 $a_l$ 的前面，其他点的相对位置不动，就可以用链表维护这个序列的状态；又发现每次查询只询问一种数值出现的个数，那么我们可以分块回答询问。我的做法是记录下每个块内部的不同数值出现次数，用 $deque$ 维护每个块存储的数字。那么直接翻译题面就行了，简直就是暴力。由于本题开启 $\text {-O2}$，还是跑得很快的。
代码
#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();
}
}