Virtual NOIP II Day 3 总结
Sweetlemon
2018-11-01 15:52:01
### T1 平均数
$40$分：直接枚举所有连续子段，计算其平均值并加入数组中，对数组进行排序，再输出第$k$小元素即可。$\text{O}(n^2\log n)$。
$100$分：直接计算第$k$小元素是很困难的，我们考虑二分，即二分一个第$k$小元素的大小，二分可行的条件是存在至少$k$个连续子段的平均值大于等于$x$，则输出可行的最小解即可。
把上述模型数学化，即：有数列$a_1,a_2,a_3,\cdots,a_n$，设它的前缀和为$S_1,S_2,S_3,\cdots,S_n$。请验证是否存在$k$组$(i,j)(0\le i< j\le n)$，使$\frac{S_j-S_i}{j-i}\le x$。
在数学上，我们一般是如何求解$f(x)\le x_0$这类不等式的呢？通常，我们会进行移项，转化为$g(x)=f(x)-x_{0}\le 0$。
这里我们不妨也进行这样的转化。原不等式等价于$\frac{S_j-S_i}{j-i}-x\le 0$，即$\frac{(S_j-jx)-(S_i-ix)}{j-i}\le 0$。
接下来我们要进一步进行变换。令$a'_{i}=a_{i}-x$，设其前缀和为$S'_{i}=S_{i}-ix$，则上面的不等式又可以化为$\frac{S'_{j}-S'_{i}}{j-i}\le 0$。即我们通过把整个数列的所有数减去我们二分的平均值，把问题转化为，是否存在至少$k$个连续子段的均值（或和）非正。
认真观察上面的分式不等式，根据我们熟悉的技巧，这个不等式可以转化为$(S'_{j}-S'_{i})(j-i)\le 0$，这不就是我们熟悉的单调性表述式（单调不增）吗？于是，问题转化为，在新数列$\left\{ S' \right\}$中，是否有至少$k$个非正序对。用归并排序或树状数组即可简单解决（这里用归并排序更好，因为数列元素是浮点数，用树状数组需要额外做离散化）。
附上代码：
```cpp
#include <cstdio>
#include <cctype>
#include <algorithm>
#define MAXIOLOG 25
#define MAXN 100005
#define INF 1019260817
#define EPS 0.00003
//EPS是经过反复试验得出的值（逃
using namespace std;
int n,k;
int a[MAXN]; //原数组
double b[MAXN]; //调整后的数组
double tarr[MAXN]; //归并排序的临时数组
long long poss; //记得这里一定要用long long!
int check(void);
void merge_sort(int l,int r); //半开区间[l,r)
int main(void){
int maxx=0,minx=INF;
n=uread(),k=uread();
for (int i=1;i<=n;i++)
a[i]=uread();
for (int i=1;i<=n;i++){
maxx=max(maxx,a[i]);
minx=min(minx,a[i]);
}
double ll,rr;
ll=minx-0.1;
rr=maxx;
//(ll,rr]
while (rr-ll>EPS){
double mid=(ll+rr)/2.0;
for (int i=1;i<=n;i++){
b[i]=double(a[i])-mid;
}
for (int i=1;i<=n;i++)
b[i]+=b[i-1];
if (check())
rr=mid;
else
ll=mid;
}
printf("%.4lf\n",ll);
return 0;
}
int check(void){
poss=0;
merge_sort(0,n+1);
return poss>=k;
}
void merge_sort(int l,int r){
if (r==l+1)
return;
int mid=(l+r+1)>>1;
//[l,mid),[mid,r)
merge_sort(l,mid);
merge_sort(mid,r);
int i=l;
int j=mid;
int tpos=0;
while (i<mid && j<r){
if (b[j]<=b[i]){
tarr[tpos]=b[j];
j++,tpos++;
poss+=(mid-i);
}
else {
tarr[tpos]=b[i];
i++,tpos++;
}
}
while (i<mid){
tarr[tpos]=b[i];
tpos++,i++;
//poss+=(r+1-mid);
}
while (j<r){
tarr[tpos]=b[j];
tpos++,j++;
}
for (i=0,j=l;i<tpos;i++,j++)
b[j]=tarr[i];
}
```
### T2 涂色游戏
这题看数据范围就觉得像数学题，果然如此。
$20$分：直接暴力搜索即可。
$70$分：考虑按列递推。我们发现某一列的方案数只和上一列所选的颜色数有关，因此我们设状态$f[i][j]$表述当前考虑到第$i$列，且第$i$列所选颜色数为$j$的方案数。
这个方案可以由$f[i-1][x]$转移而来，我们枚举$x$，再求和。
第$i$列和第$i-1$列合起来要出现$q$种颜色，因此第$i$列一定至少要出现第$i-1$列没有出现过的$q-x$种颜色。我们把枚举填色方案分为选色和涂色两步，再相乘即得方案数。
首先考虑较为简单的涂色。假设我们已经选出了$j$种要涂的颜色，现在考虑把这一列（含$n$个格子）涂成$j$种颜色的方案数。设这个方案数为$g[j]$，则$$g[j]=\text{C}^{j}_{j}j^{n}-\text{C}^{j-1}_{j}(j-1)^{n}+\text{C}^{j-2}_{j}(j-2)^n-\cdots+(-1)^{j-i}\text{C}^{i}_{j}i^n+\cdots+(-1)^{j-1}\text{C}^{1}_{j}1^{n}$$
上式可结合容斥原理理解，基本上的意思是，把最多$j$种颜色的方案数减去最多$j-1$种颜色的方案数，再加上减重复的最多$j-2$种颜色的方案数，再减去……
接着考虑更为复杂的选色。现在要选出$j$种颜色，其中必须有$q-x$种颜色选自上一列未选的$p-x$种中，剩下的颜色可以任选。我们设上一列未选的$p-x$种颜色构成的集合为$A$，上一列选了的$x$种颜色构成的集合为$B$，则可以枚举选择$A$中和$B$中元素的个数。设$a$为选择的$A$中元素个数$(a\ge q-x)$，$b=j-a$为选择的$B$中元素的个数，那么这种情况下的方案数就是$\text{C}^{a}_{p-x}\text{C}^{b}_{x}$。对每个可能的$a$求和即可。
于是，我们在计算时，对于$f[i][j]$，枚举所有$f[i-1][x]$，把$f[i-1][x]$乘上涂色方案数和选色方案数，累加到$f[i][j]$中去。
$100$分：观察上面的方案，$f[i][j]$是不是$f[i-1][x]$的固定线性组合呢？即在转移时，涂色方案数和选色方案数并不随着列的改变而改变（影响它的只是上一列的颜色数和这一列的颜色数）。而观察数据范围，$m$很大，可能要简化这一重复过程。于是我们采用矩阵Kasumi加速计算。
附注：这道题当时我在考场上写的时候没有搞清楚容斥原理，算错了$g$的值。后来订正时发现了问题，却又发现了一个诡异的问题：得分随着数组大小的增大而增大，数据范围只有$100$，但数组要开到$171$才$\text{AC}$。经过`assert`的仔细检查，终于发现是当$x>q$时$q-x<0$导致下标负向越界。因此数组下标一定要考虑清楚，否则很难查错！
```cpp
#include <cstdio>
#include <cctype>
#include <algorithm>
#define MAXIOLOG 25
#define MAXN 105
#define MOD 998244353
using namespace std;
typedef long long ll;
ll io_temp[MAXIOLOG];
typedef ll io_t;
io_t uread(void);
void uwrite(io_t x,char spliter='\n');
ll maxx;
ll c[MAXN][MAXN];
ll tpow[MAXN];
ll color_methods[MAXN];
ll choose_methods[MAXN][MAXN];
ll tmatrix[MAXN][MAXN];
ll tpowm[MAXN][MAXN];
ll f0[MAXN];
ll qpow(ll x,ll p);
void matrix_pow(ll p);
void t_times_t(void);
void t_times_ans(void);
int main(void){
ll n,m,p,q;
n=uread(),m=uread(),p=uread(),q=uread();
c[0][0]=1;
for (ll i=1;i<=100;i++){
c[i][0]=1;
for (ll j=1;j<=i;j++)
c[i][j]=(c[i-1][j-1]+c[i-1][j])%MOD;
}
tpow[0]=0;
for (ll i=1;i<=100;i++)
tpow[i]=qpow(i,n);
//tpow[x]=x^n
for (ll i=1;i<=100;i++){
for (ll j=1;j<=i;j++){
ll tres;
tres=(ll)(c[i][j])*tpow[j]%MOD;
if ((i^j)&1)
tres=-tres;
color_methods[i]=((color_methods[i]+tres+MOD)%MOD);
}
}
maxx=min(n,p); //Max colors in a column
//Choose methods
for (ll i=1;i<=maxx;i++){
ll lbound=q-i; //The last column has at least lbound colors
//Important!
(lbound<0)?(lbound=0):(0);
for (ll j=lbound;j<=maxx;j++){
//j->i
//j colors in last column, i colors in this column
ll part_a_tot=p-j; //Part A:not chosen
ll part_b_tot=j; //Part B:chosen
ll llbound=max(i-part_b_tot,q-j);
(llbound<0)?(llbound=0):(0); //Choose at least llbound colors in part A
ll uubound=min(i,part_a_tot); //Choose at most uubound colors in part A
ll tmethods=0;
for (ll pa_choose=llbound;pa_choose<=uubound;pa_choose++){
ll pb_choose=i-pa_choose;
//Choose .. from part a,choose .. from part b
tmethods=(tmethods+c[part_a_tot][pa_choose]*c[part_b_tot][pb_choose]%MOD)%MOD;
}
choose_methods[i][j]=tmethods*color_methods[i]%MOD;
}
}
//i=1(f_0)
for (ll j=1;j<=maxx;j++){
f0[j]=(ll)(c[p][j])*(color_methods[j])%MOD;
}
//f=matrix_pow(choose_methods,m-1)*f0
matrix_pow(m-1);
ll aans=0;
for (ll i=1;i<=maxx;i++){
ll tans=0;
for (ll j=1;j<=maxx;j++) //matrix times vector
tans=(tans+f0[j]*choose_methods[i][j]%MOD)%MOD;
aans=(aans+tans)%MOD;
}
uwrite(aans); //aans=f[0]+f[1]+...+f[maxx]
return 0;
}
ll qpow(ll x,ll p){
//x^p % mod;
ll ans=1;
ll tx=x;
while (p){
if (p&1)
ans=(ans*tx)%MOD;
tx=(tx*tx)%MOD;
p>>=1;
}
return ll(ans);
}
void matrix_pow(ll p){ //ans=ans^p
for (ll i=1;i<=maxx;i++){
for (ll j=1;j<=maxx;j++){
tpowm[i][j]=choose_methods[i][j];
choose_methods[i][j]=(i==j); //Make the ans matrix e
}
}
while (p){
if (p&1)
t_times_ans(); //ans*=t;
t_times_t(); //t*=t
p>>=1;
}
}
void t_times_t(void){ //t*=t
//Ans stored in tmatrix
for (ll i=1;i<=maxx;i++){
for (ll j=1;j<=maxx;j++){
//Calc row i column j
ll tans=0;
for (ll k=1;k<=maxx;k++)
tans=(tans+ll(tpowm[i][k])*tpowm[k][j]%MOD)%MOD;
tmatrix[i][j]=tans;
}
}
//Move
for (ll i=1;i<=maxx;i++)
for (ll j=1;j<=maxx;j++)
tpowm[i][j]=tmatrix[i][j];
}
void t_times_ans(void){ //ans*=t
//Ans stored in tmatrix
for (ll i=1;i<=maxx;i++){
for (ll j=1;j<=maxx;j++){
//Calc row i column j
ll tans=0;
for (ll k=1;k<=maxx;k++)
tans=(tans+ll(choose_methods[i][k])*tpowm[k][j]%MOD)%MOD;
tmatrix[i][j]=tans;
}
}
//Move
for (ll i=1;i<=maxx;i++)
for (ll j=1;j<=maxx;j++)
choose_methods[i][j]=tmatrix[i][j];
}
```
### T3 序列
$40$分：先计算出所有询问的答案，再对每次修改维护它对答案的变化，即可得到答案。
这里有个巨大的锅，就是我在写这题程序时忘记了把修改应用到数组中，居然能过样例，结果当然是全部$\text{WA}$。因此所有的程序在提交前一定要仔细检查一遍程序行为！
$100$分：据说是什么“可持久化线段树”，可惜我不会这玩意儿。