CF814E
其实是对这篇 题解 的一些理解。
Part 1
不难发现最终图大致长这样：
考虑一棵最短路树，以结点 1 为根，往下每一层有若干个结点，表示最短路距离相同的一些编号连续的结点。
其中每一层内部可以自由连边。
除了每层内部的连边和树边，其余边不合法。
Part 2
考虑第 \(i\) 层的情况。假设第 \(i-1\) 层往下连了 \(j\) 条边，那么说明第 \(i\) 层有 \(j\) 个结点。
设当前层有 \(x\) 个度数为 2 的点，\(y\) 个度数为 3 的点。减去上一层连边的度数，实际有 \(x\) 个度数为 1 的点，\(y\) 个度数为 2 的点。
考虑把度数为 2 的点拆为 2 个度数为 1 的点。
设内部连了 \(z\) 条边，那么给下一层边的方案为：\((x+2y-2z)!\)。
考虑如何计算 \(x+2y\) 个点连 \(z\) 条边的方案。
先让 \(x+2y\) 个点选 \(2z\) 个任意排列，钦定相邻两两一对连边。
取消相邻两点的顺序，例如边 \((1,2),(2,1)\) 是等价的。考虑所有可能重复的情况，就是 \(2^z\)。
取消边之间的排列顺序，即 \(z!\)。
即：\({\Large \frac{(x+2y)!}{(x+2y-2z)!\times 2^z \times z!}}\)
由于拆了点，所以拆的点之间会出现重边和自环。
枚举出现了 \(p\) 条重边，\(q\) 个自环，进行容斥。
设这些不合法的边涉及到的边数 \(s=2p+q\)。
从 \(y\) 个度数为 \(2\) 的点选出这些边的方案：\({\Large \frac{y!}{(y-s)!\times p! \times q!}}\)
就是选 \(s\) 个点，前 \(2p\) 个相邻两两一对，后 \(q\) 个每个连自环。取消一下顺序，然后不取消相邻两点的顺序就是重边了，原理和上面差不多。
那么现在选了 \(s\) 条边，\(2s\) 个点（因为拆点了），还剩 \(x+2y-2s\) 个点，\(z-s\) 条边。
所以还要乘上选择这 \(z-s\) 条边的方案，这个怎么算上面已经提过多次了。
注意还要取消拆点的顺序，还是考虑所以可能重复的情况，就是 \(2^y\)。
记得容斥一下，那么有 \(x\) 个度数为 \(1\) 的点，\(y\) 个度数为 \(2\) 的点，内部连 \(z\) 条边并给下一层 \(x+2y-2z\) 条边的方案为：
\({\Large \sum\limits_{s=2p+q ,s\leq \min(y,z)}} {\Large \frac{(-1)^{{p+q}} \times y!}{(y-s)!\times p!\times q!}\times \frac{(x+2y-2s)!}{(x-2y-2z)!\times 2^{z-s}\times (z-s)!}\times (x+2y-2z)!\times \frac{1}{2^y}}\)
Part 3
设 \(t_s={\Large \sum\limits_{s=2p+q} \frac{(-1)^{p+q}}{p! \times q!}}\)
则原式可以写为：
\({\Large \sum\limits_{0\leq s \leq \min(y,z)}^{} \frac{t_s\times y!\times (x+2y-2s)!}{(y-s)!\times 2^y} \times \frac{1}{(z-s)!\times 2^{z-s}}}\)
设 \(f(i,j)\) 表示考虑第 \(i\) 个点，向下一层连了 \(j\) 条边的方案数。
那么可以枚举 \(z,s\) 转移到 \(f(i+j,x+2y-2z)\)。但是这样是 \(O(n^4)\) 的。
注意上面那个式子，前面只需要枚举 \(s\)，后面枚举 \(z-s\) 就能转移。
那么记一个辅助数组 \(g(i,j)\)，先枚举 \(s\) 从 \(f(i,j)\) 转移到 \(g(i+j,x+2y-2s)\)，再枚举 \(z-s\) 转移到 \(f(i+j,x+2y-2z)\)。
时间复杂度 \(O(n^3)\)，空间复杂度 \(O(n^2)\)。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1005,p=1e9+7,iv2=(p+1)/2;
int n,d[N],f[N][N*2],g[N][N*2];
int t[N],fac[N*2]={1},ifac[N*2],ipw[N*2]={1};
int qpow(int a,int b) {int r=1;for(;b;b>>=1,a=a*a%p) if(b&1) r=r*a%p;return r;}
int inv(int x) {return qpow(x,p-2);}
void inc(int &x,int y) {if((x+=y)>=p) x-=p;}
void mul(int &x,int y) {if((x*=y)>=p) x%=p;}
void init()
{
for(int i=1;i<=2000;i++)
fac[i]=fac[i-1]*i%p,
ipw[i]=ipw[i-1]*iv2%p;
ifac[2000]=inv(fac[2000]);
for(int i=2000-1;~i;i--) ifac[i]=ifac[i+1]*(i+1)%p;
}
signed main()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>d[i];
init();
for(int s=0;s<=n;s++)
for(int x=0;x*2<=s;x++)
{
int y=s-x*2;
inc(t[s],ifac[x]*ifac[y]%p*(((x+y)&1)?p-1:1)%p);
}
f[1][d[1]]=1;
for(int i=1;i<=n;i++)
{
for(int j=0;j<=i*2;j++)
{
//g[i][j]->f[i][j-2(z-s)]
if(!g[i][j]) continue;
for(int k=0;k*2<=j;k++)//枚举 z-s
inc(f[i][j-k*2],g[i][j]*ipw[k]%p*ifac[k]%p);
}
for(int j=1;j<=n-i;j++)
{
if(!f[i][j]) continue;
int x=0,y=0;
for(int k=i+1;k<=i+j;k++) d[k]==2?x++:y++;
for(int s=0;s<=y;s++) inc(g[i+j][x+2*y-2*s],fac[y]*fac[x+2*y-2*s]%p*t[s]%p*ifac[y-s]%p*ipw[y]%p*f[i][j]%p);
}
}
cout<<f[n][0];
}
C0930 模拟赛
信心赛了属于是，100+100+100+10。（T4 好像有个 20pts 特殊性质没造数据）
树上的数
送。
如果一个点被修改过，那么其子树也被修改过。记个 vis 数组即可。
时代的眼泪（【模板】换根 dp）
板。
换根 dp 即可。
设 \(f(u)\) 表示以 \(u\) 为子树的答案，\(g(u)\) 表示 \(u\) 子树内有多少点点权大于 \(u\)。
那么 \(f(u)=\sum f(v)+g(u)\)，\(g(u)\) 用树状数组维护即可。
接下来考虑换根，设 \(dp(u)\) 表示以 \(u\) 为根的答案。
那么新的 \(g(u)\) 就是询问整棵树的答案减去 \(g(u)\)。
然后设 \(s(u)\) 表示 \(u\) 子树内有多少点点权大于 \(fa_u\)，从 \(dp(fa_u) \rightarrow dp(u)\) 时减去这个贡献。
则 \(dp(v)=dp(u)+g(v)'-s(v)\)。
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,m,V,a[N],lsh[N],g[N],s[N],c[N];
long long f[N],dp[N];
void upd(int x) {for(;x<=V;x+=x&-x) c[x]++;}
int ask(int x) {int r=0;for(;x>0;x^=x&-x) r+=c[x];return r;}
vector<int> G[N];
int rd()
{
int x=0;char c=getchar();
for(;!isdigit(c);c=getchar());
for(; isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(c^48);
return x;
}
void dfs1(int u,int fa)
{
g[u]-=ask(a[u]-1),s[u]-=ask(a[fa]-1);
for(int v:G[u])
{
if(v==fa) continue;
dfs1(v,u);
f[u]+=f[v];
}
upd(a[u]);
g[u]+=ask(a[u]-1),s[u]+=ask(a[fa]-1);
f[u]+=g[u];
}
void dfs2(int u,int fa)
{
for(int v:G[u])
{
if(v==fa) continue;
dp[v]=dp[u]-s[v]+ask(a[v]-1)-g[v];
dfs2(v,u);
}
}
int main()
{
n=rd(),m=rd();
for(int i=1;i<=n;i++) a[i]=lsh[i]=rd();
sort(lsh+1,lsh+1+n);
V=unique(lsh+1,lsh+1+n)-lsh-1;
for(int i=1;i<=n;i++) a[i]=lower_bound(lsh+1,lsh+1+V,a[i])-lsh;
for(int i=1;i<n;i++)
{
int x=rd(),y=rd();
G[x].push_back(y);
G[y].push_back(x);
}
dfs1(1,0);
dp[1]=f[1];
dfs2(1,0);
for(int i=1;i<=m;i++) printf("%lld\n",dp[rd()]);
}
T3 传统艺能(【模板】ddp)
考虑最简单的 dp。
设 \(f(i,j)\) 表示以考虑前 \(i\) 个数，以 \(j\) 结尾的答案。
显然有转移：
\(\begin{cases} f(i,j)=f(i-1,j) \ \ \ \ c_{i}\neq j \\ f(i,j)=\sum f(i-1,k) +1 \ \ \ \ c_{i} =j \end{cases}\)
然后 \(0 \leq j <3\)。
\(j\) 很小，考虑用矩阵乘法转移。
先写出系数，以 \(c_{i}=A\) 为例。
\(\begin{pmatrix} f(i,0) \\ f(i,1) \\ f(i,2) \\ 1 \end{pmatrix} = \begin{pmatrix} f(i-1,0) \\ f(i-1,1) \\ f(i-1,2) \\ 1 \end{pmatrix} \times \begin{pmatrix} 1 \ 1 \ 1 \ 1 \\ 0 \ 1 \ 0 \ 0 \\ 0 \ 0 \ 1 \ 0 \\ 0 \ 0 \ 0 \ 1 \end{pmatrix} \)
然后就完了。
因为矩阵乘法有结合律，所以可以用线段树维护区间求答案和修改。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,p=998244353;
int n,m,f[N][3];
char s[N];
struct matrix{
int a[4][4];
matrix() {memset(a,0,sizeof(a));}
int* operator[](int i) {return a[i];}
void init() {for(int i=0;i<4;i++) a[i][i]=1;}
matrix operator*(matrix b)
{
matrix c;
for(int i=0;i<4;i++)
for(int k=0;k<4;k++)
if(a[i][k]!=0)//不加这句优化会 TLE
for(int j=0;j<4;j++)
c[i][j]=(c[i][j]+1ll*a[i][k]*b[k][j]%p)%p;
return c;
}
}A[3];
matrix dp[N*4];
#define lc (k<<1)
#define rc (k<<1|1)
#define mid (l+r>>1)
void build(int k=1,int l=1,int r=n)
{
if(l==r) {dp[k]=A[s[l]-'A'];return;}
build(lc,l,mid),build(rc,mid+1,r);
dp[k]=dp[lc]*dp[rc];
}
void upd(int x,int v,int k=1,int l=1,int r=n)
{
if(l==r) {dp[k]=A[v];return;}
x<=mid?upd(x,v,lc,l,mid):upd(x,v,rc,mid+1,r);
dp[k]=dp[lc]*dp[rc];
}
matrix ask(int x,int y,int k=1,int l=1,int r=n)
{
if(l>=x&&r<=y) return dp[k];
matrix res;res.init();
if(x<=mid) res=res*ask(x,y,lc,l,mid);
if(mid<y) res=res*ask(x,y,rc,mid+1,r);
return res;
}
char buf[1<<15],*p1=buf,*p2=buf;
#define nc() (p1==p2&&(p2=buf+fread(p1=buf,1,1<<15,stdin),p1==p2)?-1:*p1++)
inline int rd()
{
int x=0;char c=nc();
for(;!isdigit(c);c=nc());
for(; isdigit(c);c=nc()) x=(x<<3)+(x<<1)+(c^48);
return x;
}
int main()
{
n=rd(),m=rd();
for(int i=1;i<=n;i++) s[i]=nc();
for(int i=0;i<3;i++) for(int j=0;j<4;j++) A[i][i][j]=A[i][j][j]=1;
build();
while(m--)
{
int op=rd(),x=rd(),y,ans=0;char c;
if(op==1) c=nc(),upd(x,c-'A');
else
{
y=rd();
matrix tmp=ask(x,y);
for(int i=0;i<3;i++) ans=(ans+tmp[i][3])%p;
printf("%d\n",ans);
}
}
}
T4 铺设道路
神仙贪心。
考虑求出 \(a\) 的差分数组 \(b\)。
那么每次操作相当于选择一对 \(l,r\)，使 \(b_l -1,b_r+1\)，代价是 \((r-l)^2\)。
最少天数显然是 \(\sum \max(b_i,0)\)。
对于一个位置 \(b_i<0\)，寻找前面的 \(b_l\)，并操作使得 \(b_i=0\)。
由于是差分数组，显然每个 \(b_i<0\) 都能找到对应的一些 \(b_l\)，但最后会剩一些 \(b_i\) 且 \(b_i>0\)。
这时只需要令 \(r=n+1,b_r=inf\) 即可，然后消去这些 \(b_i>0\)。
剩下的 \(b_i\) 的和显然是不变的。
对于 \(b_i>0\)，肯定是留在最后消代价最大。
那么应该让消去剩下这些 \(b_i\) 的代价最大/小。
这里考虑令代价最大的情况，那每次对于 \(b_i<0\) 选择离其最近的 \(b_l\)，也就是尽可能留住那些离 \(n+1\) 远的 \(b_i>0\)。
这个过程可以用队列维护。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e5+5,p=1e9+7;
int n,t,ans1,ans2,a[N];
deque<pair<int,int>> q1,q2;
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=n;i;i--) a[i]-=a[i-1];
for(int i=1;i<=n;i++) t+=max(a[i],0ll);
a[n+1]=-1e18;
for(int i=1;i<=n+1;i++)
{
if(a[i]>0) q1.push_back({a[i],i}),q2.push_back({a[i],i});
else
{
int x=-a[i];
while(x&&q1.size())
{
int &y=q1.front().first,l=q1.front().second;
if(x<y) y-=x,ans1=(ans1+(i-l)*(i-l)%p*x)%p,x=0;
else ans1=(ans1+(i-l)*(i-l)%p*y)%p,x-=y,q1.pop_front();
}
x=-a[i];
while(x&&q2.size())
{
int &y=q2.back().first,l=q2.back().second;
if(x<y) y-=x,ans2=(ans2+(i-l)*(i-l)%p*x)%p,x=0;
else ans2=(ans2+(i-l)*(i-l)%p*y)%p,x-=y,q2.pop_back();
}
}
}
cout<<t<<'\n'<<ans2<<'\n'<<ans1<<'\n';
}