SSerxhs 和 Serval 的退役纪念赛 题解
SSerxhs
2019-05-08 22:18:17
# 幼儿园唱歌题
出题人：Serval
广义 PAM+倍增板子题。
对原串与反串建广义 PAM，记录每个位置 $p$ 的 $last_p$，那么对于给出的询问串 $S_A$ 与 $S_B$，我们可以先根据原串的 $last_{r_2}$ 与反串的 $last_{l_1}$ 在 PAM 上定位，答案为这两个结点在 PAM 上 LCA 的 $len$ 的相反数。时间复杂度为 $O(n+q\log n)$。
# 幼儿园跳舞题
出题人：Serval
Floyd 基础应用。
Floyd 本质是 DP 以及三重循环每一重的作用作为一名合格的竞赛选手应该都知道，此处不再赘述。
那么我们来考虑在 DAG 上的情况，对于 DAG，我们可以将其先拓扑排序，那么从 $u$ 到 $v$ 可能经过的点仅有拓扑序在 $u$ 与 $v$ 之间的结点，且路径拓扑序单增。不经过特定点 $s$ 可以根据 Floyd 的性质预处理 $f_{k,i,j}$ 表示仅用拓扑序严格在 $k$ 前的点更新距离时 $i$ 与 $j$ 的最短路，$g_{k,i,j}$ 表示仅用拓扑序严格在 $k$ 后的点更新距离时 $i$ 与 $j$ 的最短路。枚举中间的转移点 $p$ 合并 $f_{s,u,p}$ 与 $g_{s,p,v}$ 即可。时间复杂度为 $O(n^3+nq)$。注意本题卡空间，如果开两个数组会MLE。
# 幼儿园rap题：
出题人：SSerxhs
首先致歉，由于出题人做题过少，本题被爆破，导致比赛受到影响。感谢管理员仅爆破此题。以下为题解。
题意：给定一个序列，要求支持区间修改区间求和，区间修改是将区间内所有 $v$ 的倍数除以 $v$。
难度定位: 绿题
先过滤掉所有 $v=1$ 的修改，有一个显然的结论: 每个数 $a_i$ 只会被修改 $log_2{a_i}$次（因为每次修改至少减半），所以可以考虑找到所有可以修改的数进行暴力修改，然后用树状数组暴力维护前缀和。这里有两个思路：
1.枚举 $v$ 的倍数 $u$，然后找到所有值为 $u$ 的位置，这个可以用 $set$ 实现。然而随便构造一组修改全是 $v=2$ 的数据就能卡 $TLE$ 。
2.枚举每个数字 $a_i$ 的约数，在约数对应的 $set$ 中存下这个数的下标，修改直接在 $set$ $lower\_bound()$ 找这段区间再修改。然而一个 $10^5$ 以内的数的约数最多有 $128$ 个，会爆空间。
upd: 用2法、空间常数小的vector可以通过本题。
正解是综合以上两种做法。设定一个参数 $m$，对每个数字 $a_i$ 预处理其小于 $m$ 的约数，在这些 $set$ 中存下 $i$ 这个下标。对于每个修改操作，如果 $v\leq m$，则直接在对应的 $set$ 中修改对应下标；如果 $v>m$，则直接枚举 $v$ 的倍数。实测 $50\leq m\leq100$可过。总复杂度 $O($玄学$)$。
代码
```cpp
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <set>
#include <math.h>
using namespace std;
typedef long long ll;
const int N=1e5+2;
set<int> pos[N],ps[N];
set<int>::iterator it,jt;
ll b[N],s[N];
int a[N],ss[N],st[N][2];
int n,m,q,zd,i,j,x,y,z,c,gs,tp;
bool ed[N];
inline void read(int &x)
{
c=getchar();
while ((c<48)||(c>57)) c=getchar();
x=c^48;c=getchar();
while ((c>=48)&&(c<=57))
{
x=x*10+(c^48);
c=getchar();
}
}
void dfs(int x,int upn)
{
//if (a[i]==28)printf("%d %d\n",x,upn);
if (x>tp)
{
if (upn!=1) ps[upn].insert(i);
return;
}
for (int i=0;(i<=st[x][1])&&(upn<=m);i++)
{
dfs(x+1,upn);
upn*=st[x][0];
}
}
inline void add(register int x,register int y)
{
while (x<=n) b[x]+=y,x+=x&(-x);
}
inline ll sum(register int x)
{
register ll r=s[x];
while (x) r+=b[x],x^=x&(-x);
return r;
}
int main()
{
//freopen("rap11.in","r",stdin);
//freopen("rap11.out","w",stdout);
read(n);read(q);m=50;
for (i=2;i<=m;i++)
{
if (!ed[i]) ss[++gs]=i;
for (j=1;(j<=gs)&&(i*ss[j]<=m);j++)
{
ed[i*ss[j]]=1;
if (i%ss[j]==0) break;
}
}
//for (i=1;i<=gs;i++) printf("%d ",ss[i]);puts("");
for (i=1;i<=n;i++)
{
read(a[i]);pos[x=a[i]].insert(i);zd=max(zd,a[i]);s[i]=s[i-1]+a[i];tp=0;
for (j=1;(j<=gs)&&(x>=ss[j]);j++) if (x%ss[j]==0)
{
//if (a[i]==28) printf("fas %d %d\n",j,ss[j]);
st[++tp][0]=ss[j];st[tp][1]=1;
//cr.first=j;cr.second=1;
x/=ss[j];
while (x%ss[j]==0) ++st[tp][1],x/=ss[j];
//ys[i].insert(cr);
}
dfs(1,1);
//for (j=1;j<=m;j++) if (a[i]%j==0) ys[i].insert(j),ps[j].insert(i);
}//return 0;
while (q--)
{
read(z);read(y);read(x);if (x==1) continue;
if (x)
{
if (x>m)
{
for (i=x;i<=zd;i+=x)
{
it=pos[i].lower_bound(z);
while ((it!=pos[i].end())&&(*it<=y))
{
if (a[c=(*it++)]%x)
{
pos[i].erase(c);
continue;
}
add(c,-a[c]);
a[c]/=x;add(c,a[c]);
pos[i].erase(c);pos[a[c]].insert(c);
}
}
}
else
{
it=ps[x].lower_bound(z);
while ((it!=ps[x].end())&&(*it<=y))
{
if (a[c=(*it++)]%x)
{
ps[x].erase(c);
continue;
}
i=a[c];
add(c,-a[c]);
a[c]/=x;
add(c,a[c]);
//for (jt=ys[c].begin();jt!=ys[c].end();jt++) if (a[c]%(*jt)) {/*if (c==8) printf("%d\n",*jt);*/ j=*(jt--),ys[c].erase(j),ps[j].erase(c);}
pos[i].erase(c);pos[a[c]].insert(c);
}
}
}
else printf("%lld\n",sum(y)-sum(z-1));
}
}
```
# 幼儿园篮球题：
出题人：SSerxhs
注意：题解所用变量名称和题目中是**不同**的
题意：给定系数 $k$，多组询问超几何分布 $x$~$H(N,M,n)$ 的 $k$ 次方期望 $E(x^k)$。
难度定位：简单紫题，文化课选手应该能秒。
前两档部分分分别是套课本期望方差公式和直接暴力枚举投进几个球，用超几何分布公式计算。
超几何分布中， $P(x=i)=\frac{\tbinom{M}{i}\tbinom{N-M}{n-i}}{\tbinom{N}{n}}$
所以
$$ans=\sum_{i=0}^ni^k*\frac{\tbinom{M}{i}\tbinom{N-M}{n-i}}{\tbinom{N}{n}}=\sum_{i=1}^ni^k*\frac{\tbinom{M}{i}\tbinom{N-M}{n-i}}{\tbinom{N}{n}}$$
考虑 $i^k$ 的组合意义是将 $k$ 个**不同**的球放入 $i$ 个**不同**的盒子中的方案数，设 $S_2(k,j)$ (第二类斯特林数)表示把 $k$ 个**不同**的球放入 $j$ 个**相同**的盒子且要求**盒子非空**的方案数，考虑枚举**非空盒子**数目 $j$ 那么显然有
$$i^k=\sum_{j=0}^iS_2(k,j)j!\tbinom{i}{j}$$
代入题中式子可以得到
$$\sum_{i=1}^ni^k\frac{\tbinom{M}{i}\tbinom{N-M}{n-i}}{\tbinom{N}{n}}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $$
$$=\frac{\sum_{i=1}^n\tbinom{M}{i}\tbinom{N-M}{n-i}\sum_{j=0}^kS_2(k,j)j!\tbinom{i}{j}}{{\tbinom{N}{n}}}$$
交换求和次序
$$=\frac{\sum_{j=0}^kS_2(k,j)j!\sum_{i=1}^n\tbinom{M}{i}\tbinom{i}{j}\tbinom{N-M}{n-i}}{{\tbinom{N}{n}}}$$
考虑 $\tbinom{M}{i}\tbinom{i}{j}$ 的组合意义是从 $M$ 个人中选出 $i$ 个参加比赛的，再从 $i$ 个人中选出 $j$ 个获奖。
那么我们可以先硬点 $j$ 个人获奖，然后选 $i-j$ 个人~~爆0~~
可以得到 $\tbinom{M}{i}\tbinom{i}{j}=\tbinom{M}{j}\tbinom{M-j}{i-j}$
因此原式化为下式（与 $i$ 无关扔前面）
$$\ \ \ \ \ \ \ =\frac{\sum_{j=0}^kS_2(k,j)j!\tbinom{M}{j}\sum_{i=1}^n\tbinom{M-j}{i-j}\tbinom{N-M}{n-i}}{{\tbinom{N}{n}}}$$
后面这玩意是一个范德蒙德卷积，进一步化简
$$=\frac{\sum_{j=0}^kS_2(k,j)j!\tbinom{M}{j}\tbinom{N-j}{n-j}}{{\tbinom{N}{n}}}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $$
这样只要知道 $S_2(k,j)$ 就可以 $O(k)$ 计算答案了，而$O(qk)$的复杂度是可以通过这题的。
考虑第二类斯特林数 $S_2(k,j)$ 的组合意义，利用容斥原理可以得到
$$S_2(k,j)=\frac{1}{j!}\sum_{i=0}^j(-1)^i(j-i)^k\tbinom{j}{i}=\sum_{i=0}^j\frac{(-1)^i(j-i)^k}{i!(j-i)!}$$
设生成函数 $f(x)=\sum_i(-1)^ii!*x^i,g(x)=\sum_i\frac{i^k}{i!}*x^i$，显然对于一个给定的 $k$，$S_2(k,j)$ 为 $f*g$ 中 $x^j$ 的系数，可以 $O(k+N)$ 计算 $f(x),g(x)$ （可以用线性筛处理 $i^k$ )，然后 $NTT$ 就可以 $O(klog_2k+N)$ 计算所需要的第二类斯特林数，从而计算出结果。总复杂度 $O(N+k(q+log_2k))$。
代码
```cpp
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N=5.5e5,M=2e7+2,p=998244353;
int f[N],g[N],r[N],yg[N],ig[N],ifac[M],fac[M],ss[N],mc[N];
int c;
inline int ksm(register int x,register int y)
{
register int r=1;
while (y)
{
if (y&1) r=(ll)r*x%p;
x=(ll)x*x%p;
y>>=1;
}
return r;
}
void dft(register int *a,register int xs,register int limit)
{
register int i,j,k,l,w,wn,b,c;
for (i=1;i<limit;i++) if (i<r[i]) swap(a[i],a[r[i]]);
for (i=1;i<limit;i=l)
{
l=i<<1;
if (xs) wn=ig[l]; else wn=yg[l];
for (j=0;j<limit;j+=l)
{
w=1;
for (k=0;k<i;k++,w=(ll)w*wn%p)
{
b=a[j|k];c=(ll)w*a[j|k|i]%p;
a[j|k]=(b+c)%p;
a[j|k|i]=(b-c+p)%p;
}
}
}
if (xs)
{
limit=ksm(limit,p-2);
for (i=0;i<xs;i++) a[i]=(ll)a[i]*limit%p;
}
}
inline void read(int &x)
{
c=getchar();
while ((c<48)||(c>57)) c=getchar();
x=c^48;c=getchar();
while ((c>=48)&&(c<=57))
{
x=x*10+(c^48);
c=getchar();
}
}
int main()
{
register int n,m,q,k,i,j,x,limit=1,l=0,gs=0;
read(n);read(c);read(q);read(k);
while (limit<=k) limit<<=1,++l;
n=max(n,limit-1);
limit<<=1;
for (i=1;i<limit;i++) r[i]=r[i>>1]>>1|(i&1)<<l;
ig[limit]=ksm(yg[limit]=ksm(3,(p-1)/limit),p-2);
for (i=limit>>1;i;i>>=1)
{
yg[i]=(ll)yg[i<<1]*yg[i<<1]%p;
ig[i]=(ll)ig[i<<1]*ig[i<<1]%p;
}
l=limit>>1;ifac[0]=ifac[1]=fac[0]=fac[1]=1;
for (i=2;i<=n;i++) ifac[i]=p-(ll)p/i*ifac[p%i]%p,fac[i]=(ll)fac[i-1]*i%p;
for (i=2;i<=n;i++) ifac[i]=(ll)ifac[i-1]*ifac[i]%p;
mc[1]=1;
for (i=2;i<l;i++)
{
if (!mc[i]) mc[ss[++gs]=i]=ksm(i,k);
for (j=1;(j<=gs)&&(i*ss[j]<l);j++)
{
mc[i*ss[j]]=(ll)mc[i]*mc[ss[j]]%p;
if (i%ss[j]==0) break;
}
}
for (i=0;i<l;i++) if (i&1) f[i]=p-ifac[i]; else f[i]=ifac[i];
for (i=1;i<l;i++) g[i]=(ll)ifac[i]*mc[i]%p;
dft(f,0,limit);dft(g,0,limit);
for (i=0;i<limit;i++) f[i]=(ll)f[i]*g[i]%p;
dft(f,l,limit);
while (q--)
{
read(n);read(m);read(x);
j=0;
for (i=min(min(x,m),k);i;i--) j=(j+(ll)f[i]*ifac[m-i]%p*fac[n-i]%p*ifac[x-i])%p;
printf("%d\n",int((ll)j*ifac[n]%p*fac[x]%p*fac[m]%p));
}
}
```
update：由于时限缩短，此代码已经无法通过此题。请使用高效的阶乘/阶乘逆元预处理手段。