CQBZ round 10
心态考爆炸了，emmmm。
最大挂点：T5
原因：
主要：对二项式反演本质理解有问题。
次要：不会及时止损。
jump
不妨设 \(h_0=0\)，且固定这个位置，则原问题化为找到一种排列，求出：
\[\max\left\lbrace\sum_{i=1}^n(h_i-h_{i-1})^2\right\rbrace \]将其拆开，化简，可以得到：
\[\begin{align*} &\sum_{i=1}^n(h_i-h_{i-1})^2\\ &=\sum_{i=1}^n{h^2_i+h^2_{i-1}-2h_ih_{i-1}}\\ &=\sum_{i=1}^n 2h_i^2-h_n^2-2\sum_{i=1}^nh_ih_{i-1} \end{align*} \]而式子前半部分是定值，也即需要最小化 \(h_n^2+\sum_{i=1}^nh_ih_{i-1}\)
而显然，我们通过比较四个值 \(i<j<k<p\)，显然有 \(pi+kj<ik+pj\)。故头尾相接显然最优。
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
sort(a+1,a+n+1);int ans=0;
for(int i=1;i<=n;i++){
b[++m]=a[n-i+1];b[++m]=a[i];
if(m>=n)break;
}
for(int i=1;i<=m;i++)ans+=(b[i]-b[i-1])*(b[i]-b[i-1]);
segment
显然是一个动态规划问题。
设 \(f_{i,0/1}\) 表示从 \((1,1)\) 走到第 \(i\) 层线段的左/右端点的最小代价。
则显然根据上一个区间的左右端点判断是否需要走“冤枉路”即可。
cin>>n;for(int i=1;i<=n;i++)cin>>l[i]>>r[i];
f[0][1]=f[0][0]=0;l[0]=r[0]=1;r[n+1]=l[n+1]=n;++n;
for(int i=1;i<=n;i++){
if(l[i-1]>r[i])f[i][0]=f[i-1][0]+l[i-1]-l[i];
else f[i][0]=f[i-1][0]+r[i]-l[i-1]+r[i]-l[i];
if(r[i-1]<l[i])f[i][1]=f[i-1][1]+r[i]-r[i-1];
else f[i][1]=f[i-1][1]+r[i-1]-l[i]+r[i]-l[i];
if(r[i-1]>r[i])f[i][0]=min(f[i][0],f[i-1][1]+r[i-1]-l[i]);
else f[i][0]=min(f[i][0],f[i-1][1]+r[i]-r[i-1]+r[i]-l[i]);
if(l[i-1]<l[i])f[i][1]=min(f[i][1],f[i-1][0]+r[i]-l[i-1]);
else f[i][1]=min(f[i][1],f[i-1][0]+l[i-1]-l[i]+r[i]-l[i]);
}
cout<<f[n][0]+n-2<<"\n";
color
括号序列问题，注意到 \(|s|\le 800\)，这意味着 \(O(|s|^2)\) 可过。
trick:括号序列上 \(O(n^2)\) 及其以上复杂度的问题，一般是区间DP问题，且根据配对括号进行处理。
注意到转移只与端点有关，所以可以考虑直接开DP记录端点状态。
我们处理出配对的括号，用栈。然后不妨设 \(f_{l,r,0/1/2,0/1/2}\)
按照题意转移即可。。。
signed main(){
ios::sync_with_stdio(false);
cin>>a+1;n=strlen(a+1);
for(int i=1;i<=n;i++){
if(a[i]=='(')s.push(i);
else nxt[s.top()]=i,s.pop();
}
for(int len=2;len<=n;++len){
for(int l=1,r=len;r<=n;++r,++l){
if(a[l]=='('&&a[r]==')'){
if(len==2){
f[l][r][1][0]=f[l][r][0][1]=f[l][r][2][0]=f[l][r][0][2]=1;continue;
}
else if(nxt[l]==r){
for(int p=0;p<3;++p)for(int q=0;q<3;++q){
f[l][r][0][1]+=f[l+1][r-1][p][q]*(q!=1);
f[l][r][0][2]+=f[l+1][r-1][p][q]*(q!=2);
f[l][r][1][0]+=f[l+1][r-1][p][q]*(p!=1);
f[l][r][2][0]+=f[l+1][r-1][p][q]*(p!=2);
}
for(int s=0;s<3;++s)for(int q=0;q<3;++q)f[l][r][s][q]%=p;
}
else if(nxt[l]<=r){
for(int a=0;a<3;++a){
for(int b=0;b<3;++b){
for(int c=0;c<3;++c){
for(int d=0;d<3;++d){
if(d==c&&c!=0)continue;
f[l][r][a][b]+=f[l][nxt[l]][a][c]*f[nxt[l]+1][r][d][b];
f[l][r][a][b]%=p;
}
}
}
}
}
}
}
}
int ans=0;
for(int i=0;i<3;i++)for(int j=0;j<3;j++)ans+=f[1][n][i][j];
ans=(ans%p+p)%p;
cout<<ans<<"\n";
}
cloud
trick：
- 注意到题目中的维度限制。
- 注意到题目中的花费与收益不在同一维度的问题，可以考虑抽象为背包模型。
- 01背包问题特征：有两个维度，分属不同的物品（钱和道具），最优化。
在本题中，若考虑简化版问题，不考虑 \(f\) 的限制，则容易发现题目为一个裸0/1背包问题。
考虑 \(f\) 的限制又能怎么办？
不妨思考其与普通01背包的具体差别在哪里。
即 \(f\) 较低的物品无法更新 \(f\) 更高的需求。也即更新有一定限制。
对于这种单一的大小关系限制，对转移顺序做出调整即可。
我们将 \(f\) 从大到小排序，转移01背包，为了避免后面的 \(f\) 更新前面的需求，限制背包剩余容量 \(\ge 0\) 即可。
最后对DP数组取个最大值即可。
int d=0;
memset(f,-0x3f,sizeof f);
cin>>n;for(int i=1;i<=n;i++){
cin>>a[i].c>>a[i].f>>a[i].v;a[i].v*=-1;d+=a[i].c;
}
f[0][0]=0;
cin>>m;
for(int i=n+1;i<=n+m;i++){
cin>>a[i].c>>a[i].f>>a[i].v;a[i].c*=-1;
}n+=m;
sort(a+1,a+n+1);//f==b.f?v<b.v:f>b.f;
for(int i=1;i<=n;i++){
for(int j=0;j<=d;++j){
f[i&1][j]=f[(i^1)&1][j];
if(j-a[i].c>=0&&j-a[i].c<=d)f[i&1][j]=max(f[(i^1)&1][j-a[i].c]+a[i].v,f[i&1][j]);
}
}
int ans=0;
for(int i=0;i<=d;++i)ans=max(ans,f[n&1][i]);
martix
对于此题，我用了 \(3h\)，叉掉了正解，乱搞以失败告终，喜提罚坐3h+200pts
这里先甩几个二项式反演式子，免得搞忘了。
\[\begin{align*} &g_n=\sum{n\choose i}f_i\Longleftrightarrow f_n=\sum (-1)^{n-i}{n \choose i}g_i\\ &g_n=\sum_{i=n}^N{i\choose n}f_i\Longleftrightarrow f_n=\sum_{i=n}^N (-1)^{i-n}{i\choose n}g_i\\ &g_n=\sum(-1)^n{n\choose i}f_i\Longleftrightarrow f_n=\sum (-1)^n{n\choose i}g_i\\ &g_n=\sum_{i=n}^N(-1)^i{i\choose n}f_i\Longleftrightarrow f_n=\sum_{i=n}^N (-1)^i{i\choose n}g_i\\ \end{align*} \]对于式一，式二中 \(g\) 的组合意义，请注意，并不是至多至少选 \(i\) 个，而是 钦定选 \(i\) 个，其余自选。
至少：钦定了 \(i\) 个性质必选，其余性质可选可不选。
至多：钦定了 \(i\) 个性质不选，其余性质可选可不选。
比如并非是要在 \(g\) 中还要再挑 \(i\) 个出来。
事实上，四个式子都可以扩展到高维情况。
例如：
\[\begin{align*} &g(a,b)=\sum\sum{a\choose i}{b\choose j}f(i,j)\Longleftrightarrow f(a,b)=\sum\sum (-1)^{a+b-i-j}{a\choose i}{b\choose j}g(i,j)\\ &g(a,b)=\sum^N\sum^N{i\choose a}{j\choose b}f(i,j)\Longleftrightarrow f(a,b)=\sum^N\sum^N (-1)^{i+j-a-b}{i\choose a}{j\choose b}g(i,j)\\ \end{align*} \]扯了这么远，现在我们来提一提正事。
首先，由于值域是 \([1,k]\)，所以原符合条件的解是满足每一行每一列都出现一个至少 \(1\) 个 \(1\) 的方案数。
那么，设 \(f(i,j)\) 为恰好有 \(i\) 行 \(j\) 列不含有 \(1\) 的方案数，则 \(f(0,0)\) 即为所求。
然后，我们设 \(g(i,j)\) 为至少有 \(i\) 行 \(j\) 列不含有 \(1\) 的方案数。
根据性质，我们钦定了 \(i\) 行不能有 \(1\) ，\(j\) 列不能有 \(1\)，则等价于令 \(n(i+j)-ij\) 个数强制性不为 \(1\)，而其余 \((n-i)(n-j)\) 个数随意。
所以有 \(g(i,j)={n\choose i}{n\choose j}(k-1)^{n(i+j)-ij}k^{(n-i)(n-j)}\)。
根据定义，显然有：
\[\begin{align*} &g(a,b)=\sum_{i=a}^N\sum_{j=b}^N f(i,j)\\ \Longleftrightarrow & f(a,b)=\sum_{i=a}^N\sum_{j=b}^N(-1)^{i+j-a-b}g(i,j) \end{align*} \]进而，由于所求为 \(f(0,0)\)，则答案为：
\[\sum_{i=0}^n\sum_{j=0}^n(-1)^{i+j}{n\choose i}{n\choose j}k^{(n-i)(n-j)}(k-1)^{n(i+j)-ij} \]复杂度可以通过预处理做到 \(O(n^2)\)，不过 \(O(n^2\log n)\) 已经足够。
反演之前一定要想清楚 \(f,g\) 的真正含义，再三确定代码是否打挂
virus
艹，不太难的问题貌似。
首先注意到，原题意等价于给出一颗无根树，任选一个点为根，并给所有节点附上不同的 \(1\sim n\) 的值 \(a_i\)，满足儿子的权值大于父亲，求期望的 \(a\) 的逆序对数。
注意到 \(n\le 200\)，考虑枚举这个根。
设 \(s_i\) 为节点 \(i\) 作为根时，期望的逆序对数。
则显然答案为 \(\frac{\sum s_i}{n}\)。
统计 \(s_i\)？根据期望的定义，显然枚举每一对 \(i<j\)，对其为逆序对的概率求个和就行了，因为每一对数贡献独立。
说详细点就是其在 \(p\) 种情况下贡献为1，其余为0，总有 \(q\) 种情况，则其贡献为 \(\frac{p}{q}\)，也即概率。
然后考虑统计这个概率。
枚举 \(i<j\)，设 \(t=lca(i,j)\)。这时候我们只关心 \(Path(i,t,j)\) 上的点的情况，其余无需管（对答案没影响）,也即只考虑相对关系。
什么样的情况才是答案呢？显然是先走到 \(j\) 再走到 \(i\) 的情况。
设 \(x=dep_i-dep_t,y=dep_j-dep_t\)，若 \(x=0\)，则这概率显然为0，若 \(y=0\)，则这概率显然为1。
否则，由于我们只关心这两条链的进度，则只需关心对这两条链的某次操作是属于其中哪一条的。
问题就得到了转化：有两个数 \(x,y\)，每一次可以等概率选一个数让其减去 \(1\)，求 \(y\) 先减到0的概率。
这里有两种解决方式：动态规划与数学。
不过这里DP显然更容易实现，但还是两个都说说吧。
先说数学，我们可以枚举减去的 \(x'\in [0,x-1]\)。就可以得到当前概率是 \(\frac{{y+x'-1\choose x'}}{2^{y+x'}}\)。因为最后一次必然是给到 \(y\) 令其变成0的。
所以所求为 \(\sum_{x'=0}^{x-1}\frac{{y+x'-1\choose x'}}{2^{y+x'}}\)。
可以 \(O(n^2\log n)\) 预处理出所有 \((x,y)\) 的答案。
再说DP，设 \(g_{x,y}\) 为所求，则枚举第一次操作是减掉的谁即可，故有 \(g_{x,y}=\frac{g_{x-1,y}+g_{x,y-1}}{2}\)。
不过有 \(g_{0,0}=0,g_{0,x}=0,g_{x,0}=1\)。
最后我们求和即可求解，时间复杂度 \(O(n^3\log n)\)，可以通过。
void init(){
cin>>n;
for(int i=2;i<=n;i++){
int u,v;cin>>u>>v;add(u,v);
}
jc[0]=inv[0]=1;
for(int i=1;i<=n;i++)jc[i]=jc[i-1]*i%p;
inv[n]=power(jc[n],p-2);
for(int i=n-1;i;--i)inv[i]=inv[i+1]*(i+1)%p;
inv_n=inv[n]*jc[n-1]%p;
for(int i=0;i<=n;i++){
for(int j=0;j<=n;j++){
if(j==0)g[i][j]=(i!=0);
else if(i!=0)g[i][j]=(g[i-1][j]+g[i][j-1])*inv_2%p;
}
}
}
int ans=0;
void solve(int rt){
dfs(rt,0);int k=ans;
for(int j=1;j<=n;j++)for(int i=1;i<j;++i){//j is before i
int s=lca(i,j);
if(s==i)continue;
if(s==j){
++ans;continue;
}
int x=dep[s]-dep[i],y=dep[s]-dep[j];x=-x,y=-y;
ans+=g[x][y];
ans%=p;
}
}
signed main(){
ios::sync_with_stdio(false);
init();
for(int i=1;i<=n;i++)solve(i);
ans=ans*inv_n%p;
cout<<ans<<"\n";
}