【做題記錄】2025提高刷題-dp
A. Min-Fund Prison (Medium)
考慮一個邊雙連通分量一定不可能分為合法的兩部分，于是進行縮點?？s完后顯然是一個森林。
設 \(dp_{i,j,0/1}\) 表示第一堆有 \(i\) 個點，第二堆有 \(j\) 個點，兩堆點有沒有用一條邊連起來的最小花費。對于每棵樹，考慮將它加入第一堆/加入第二堆/一部分加入第一堆另一部分加入第二堆。時間復雜度 \(O(n^3)\)。
Code
#include<bits/stdc++.h>
#define int long long
#define il inline
#define pb push_back
#define mem(a,b) memset(a,b,sizeof a)
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
namespace IO{
const int bufsz=1<<20;
char ibuf[bufsz],*p1=ibuf,*p2=ibuf;
#define getchar() (p1==p2&&(p2=(p1=ibuf)+fread(ibuf,1,bufsz,stdin),p1==p2)?EOF:*p1++)
template<typename T=int>il T read(){
char ch=getchar();
while(ch<'0'||ch>'9'){
ch=getchar();
}
T x=0;
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x;
}
#undef getchar
char obuf[bufsz],*p3=obuf,s[50];
il int flush(){
fwrite(obuf,1,p3-obuf,stdout);
p3=obuf;
return 0;
}
#define putchar(ch) (p3==obuf+bufsz&&flush(),*p3++=(ch))
template<typename T>il void write(T x,bool typ=1){
if(x<0){
putchar('-');
x=-x;
}
int top=0;
do{
s[++top]=x%10|48;
x/=10;
}while(x);
while(top){
putchar(s[top--]);
}
putchar(typ?'\n':' ');
}
#undef putchar
}
using IO::read;
using IO::write;
const int maxn=305,inf=0x3f3f3f3f3f3f3f3f;
int T,n,m,c,enm,hd[maxn];
struct edge{
int v,nxt;
}e[maxn<<1];
il void addedge(int u,int v){
e[++enm]=(edge){v,hd[u]};
hd[u]=enm;
}
int dfn[maxn],low[maxn],cnt;
bool geb[maxn<<1];
il void tarjan(int u,int fa){
dfn[u]=low[u]=++cnt;
for(int i=hd[u],v;i;i=e[i].nxt){
v=e[i].v;
if(!dfn[v]){
tarjan(v,i);
low[u]=min(low[u],low[v]);
if(low[v]>dfn[u]){
geb[i]=geb[i^1]=1;
}
}
else if(i!=fa&&i!=(fa^1)){
low[u]=min(low[u],dfn[v]);
}
}
}
int bel[maxn],bcn,sz[maxn];
bool vis[maxn];
il void dfs1(int u){
vis[u]=1,bel[u]=bcn,sz[bcn]++;
for(int i=hd[u],v;i;i=e[i].nxt){
v=e[i].v;
if(!vis[v]&&!geb[i]){
dfs1(v);
}
}
}
int dp[maxn][maxn][2],nf[maxn][maxn][2],tot;
vector<int> ed[maxn];
il void dfs2(int u,int fa){
vis[u]=1;
for(int v:ed[u]){
if(v==fa){
continue;
}
dfs2(v,u);
sz[u]+=sz[v];
}
}
il void upd(int &x,int y){
x=min(x,y);
}
il void dfs3(int u,int fa,int rt){
for(int v:ed[u]){
if(v==fa){
continue;
}
for(int i=0;i<=tot;i++){
upd(nf[i+sz[v]][tot-i+sz[rt]-sz[v]][1],dp[i][tot-i][0]+2*i*sz[v]+sz[v]*sz[v]+2*(tot-i)*(sz[rt]-sz[v])+(sz[rt]-sz[v])*(sz[rt]-sz[v])+c*(i?1:0)+c*(tot-i?1:0));
upd(nf[i+sz[rt]-sz[v]][tot-i+sz[v]][1],dp[i][tot-i][0]+2*i*(sz[rt]-sz[v])+(sz[rt]-sz[v])*(sz[rt]-sz[v])+2*(tot-i)*sz[v]+sz[v]*sz[v]+c*(i?1:0)+c*(tot-i?1:0));
}
dfs3(v,u,rt);
}
}
il void solve(){
n=read(),m=read(),c=read();
enm=1;
for(int i=1,u,v;i<=m;i++){
u=read(),v=read();
addedge(u,v);
addedge(v,u);
}
cnt=0;
for(int i=1;i<=n;i++){
if(!dfn[i]){
tarjan(i,0);
}
}
bcn=0;
for(int i=1;i<=n;i++){
if(!vis[i]){
bcn++;
dfs1(i);
}
}
// for(int i=1;i<=bcn;i++){
// cout<<sz[i]<<" ";
// }
// puts("");
for(int u=1;u<=n;u++){
for(int i=hd[u],v;i;i=e[i].nxt){
v=e[i].v;
if(bel[u]!=bel[v]){
ed[bel[u]].pb(bel[v]);
ed[bel[v]].pb(bel[u]);
}
}
}
for(int i=1;i<=bcn;i++){
sort(ed[i].begin(),ed[i].end());
ed[i].erase(unique(ed[i].begin(),ed[i].end()),ed[i].end());
}
mem(dp,0x3f);
dp[0][0][0]=0;
tot=0;
mem(vis,0);
for(int i=1;i<=bcn;i++){
if(!vis[i]){
// cout<<i<<"\n";
dfs2(i,0);
memcpy(nf,dp,sizeof dp);
for(int j=0;j<=tot;j++){
upd(nf[j+sz[i]][tot-j][0],dp[j][tot-j][0]+2*j*sz[i]+sz[i]*sz[i]+c*(j?1:0));
upd(nf[j][tot-j+sz[i]][0],dp[j][tot-j][0]+2*(tot-j)*sz[i]+sz[i]*sz[i]+c*(tot-j?1:0));
upd(nf[j+sz[i]][tot-j][1],dp[j][tot-j][0]+2*j*sz[i]+sz[i]*sz[i]+c+c*(j?1:0));
upd(nf[j+sz[i]][tot-j][1],dp[j][tot-j][1]+2*j*sz[i]+sz[i]*sz[i]+c*(j?1:0));
upd(nf[j][tot-j+sz[i]][1],dp[j][tot-j][0]+2*(tot-j)*sz[i]+sz[i]*sz[i]+c+c*(tot-j?1:0));
upd(nf[j][tot-j+sz[i]][1],dp[j][tot-j][1]+2*(tot-j)*sz[i]+sz[i]*sz[i]+c*(tot-j?1:0));
}
dfs3(i,0,i);
tot+=sz[i];
memcpy(dp,nf,sizeof nf);
}
}
// cout<<tot<<"\n";
int ans=inf;
for(int i=1;i<tot;i++){
ans=min(ans,dp[i][tot-i][1]);
}
write(ans>=inf?-1:ans);
mem(hd,0),mem(dfn,0),mem(low,0);
mem(vis,0),mem(geb,0),mem(sz,0);
for(int i=1;i<=bcn;i++){
ed[i].clear();
}
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
signed main(){
T=read();
while(T--){
solve();
}
IO::flush();
return 0;
}
}
signed main(){return asbt::main();}
/*
1
6 6 2
1 4
2 5
3 6
1 5
3 5
6 5
*/
B. Construct Tree
考慮如果構造出了一條直徑，若對于剩下的每一條邊都可以找到一個點使加上后新的路徑不大于直徑，那就是有解的。
因此我們考慮將直徑拆成兩段，設 \(dp_{i,j}\) 表示第一段長度為 \(i\) 第二段長度為 \(j\) 是否可行，枚舉每條邊向兩段里面加。最后如果兩段長度都大于最長的邊則合法?？梢杂?bitset 優化，\(O(\frac{nm^2}{w})\)。
然而這樣是有問題的，考慮如果最大的邊在其中一段中，另一段是有可能小于這個最大值的，然而這樣也是可以合法的。因此再加一個判斷，如果可以找到一個邊集長度滿足 \(m\) 使最大的邊在集合中，那就也合法。可以用可行性背包。
然而其實還是有問題，新的兩條邊之和有可能直接大于 \(m\)。因此再判斷，如果最大值與次大值之和大于 \(m\) 就不合法。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define read(x){\
char ch;\
int fu=1;\
while(!isdigit(ch=getchar()))\
fu-=(ch=='-')<<1;\
x=ch&15;\
while(isdigit(ch=getchar()))\
x=(x<<1)+(x<<3)+(ch&15);\
x*=fu;\
}
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=2e3+5;
int T,n,m,a[maxn];
int g[maxn];
bool f[maxn];
bitset<maxn> dp[maxn];
il void solve(){
read(n)read(m);
for(int i=1;i<=n;i++){
read(a[i]);
}
sort(a+1,a+n+1);
if(a[n-1]+a[n]>m){
puts("NO");
return ;
}
for(int i=0;i<=m;i++){
f[i]=g[i]=0;
}
f[0]=1;
for(int i=1;i<=n;i++){
for(int j=m;j>=a[i];j--){
if(f[j-a[i]]){
f[j]=1;
g[j]=max({g[j],g[j-a[i]],a[i]});
}
}
}
if(!f[m]){
puts("NO");
return ;
}
if(g[m]==a[n]){
puts("YES");
return ;
}
for(int i=0;i<=m;i++){
dp[i].reset();
}
dp[0][0]=1;
for(int i=1;i<=n;i++){
for(int j=m;j;j--){
dp[j]|=dp[j]<<a[i];
if(j>=a[i]){
dp[j]|=dp[j-a[i]];
}
}
}
for(int i=0;i<=m;i++){
if(min(i,m-i)>=a[n]&&dp[i][m-i]){
puts("YES");
return ;
}
}
puts("NO");
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
read(T);
while(T--){
solve();
}
return 0;
}
}
int main(){return asbt::main();}
C. Light Bulbs (Hard Version)
若在一個區間 \([l,r]\) 中，每種顏色都出現偶數次（\(2\) 或 \(0\)），且這個區間不能再被分割成這樣的區間，則在這個區間中只要一開始點亮了一個就可以點亮全部。使用異或哈希判斷每個顏色的出現次數。\(ans1\) 即為這樣的區間數量。
然而在一個這樣的區間中，并不是點亮每一個都是合法的。比如這個區間 \((3,1,2,1,2,3)\)，選第一個或最后一個 \(3\) 點亮是沒問題的，但是點亮 \(1\) 或 \(2\) 是不行的。因此我們需要跳過這些位置。存儲每一個哈希值最后出現的位置，當這個值不是 \(0\) 時，這個位置就是合法的位置。于是對于每一個區間累加這樣的位置個數，再乘起來就好了。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define read(x){\
char ch;\
int fu=1;\
while(!isdigit(ch=getchar()))\
fu-=(ch=='-')<<1;\
x=ch&15;\
while(isdigit(ch=getchar()))\
x=(x<<1)+(x<<3)+(ch&15);\
x*=fu;\
}
#define ull unsigned ll
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=4e5+5;
const int mod=998244353;
int T,n,p1[maxn],p2[maxn];
ull ha[maxn<<1],hc[maxn];
mt19937_64 rdsd(time(0));
il void solve(){
read(n);
for(int i=1;i<=n;i++){
hc[i]=rdsd();
// cout<<hc[i]<<"\n";
}
map<ull,int> cun;
int ans=0;
for(int i=1,x;i<=n<<1;i++){
read(x);
ha[i]=ha[i-1]^hc[x];
cun[ha[i]]=i;
if(!ha[i]){
ans++;
}
}
printf("%d ",ans);
ans=1;
for(int i=0,j;i<n<<1;i++){
if(!ha[i]){
j=i+1;
int res=1;
while(ha[j]){
j=cun[ha[j]]+1;
res++;
}
ans=ans*1ll*res%mod;
}
}
printf("%d\n",ans);
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
read(T);
while(T--){
solve();
}
return 0;
}
}
int main(){return asbt::main();}
D. Twin Friends
計數題，用桶存儲每個字母的出現次數。
首先對于 \(A\)，它的排列有 \(\frac{n!}{\prod_{i=1}^{26} toa_i!}\) 種。于是只需再計算字母的對應方式即可。
設 \(dp_{i,j}\) 表示第 \(i\) 個字母，用了 \(j\) 個 \(i+1\) 來替換的方案數。即在這 \(toa_i\) 個子母中可以選擇 \(j\) 個。于是有方程：
\[dp_{i,j}={toa_i\choose j}\sum_{k=0}^{tob_i-toa_i+j}dp_{i-1,k}
\]
使用前綴和即可。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define read(x){\
char ch;\
int fu=1;\
while(!isdigit(ch=getchar()))\
fu-=(ch=='-')<<1;\
x=ch&15;\
while(isdigit(ch=getchar()))\
x=(x<<1)+(x<<3)+(ch&15);\
x*=fu;\
}
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=2e5+5;
const int mod=998244353;
int n,m,toa[30],tob[30];
int dp[30][maxn];
int fac[maxn],inv[maxn];
char a[maxn],b[maxn];
il int qpow(int x,int y){
int res=1;
while(y){
if(y&1){
res=res*1ll*x%mod;
}
x=x*1ll*x%mod,y>>=1;
}
return res;
}
il int C(int x,int y){
if(x<y||y<0){
return 0;
}
return fac[x]*1ll*inv[y]%mod*inv[x-y]%mod;
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
read(n)read(m);
scanf(" %s %s",a+1,b+1);
for(int i=1;i<=n;i++){
toa[a[i]-'A'+1]++;
}
for(int i=1;i<=m;i++){
tob[b[i]-'A'+1]++;
}
fac[0]=1;
for(int i=1;i<=n;i++){
fac[i]=fac[i-1]*1ll*i%mod;
}
inv[n]=qpow(fac[n],mod-2);
for(int i=n;i;i--){
inv[i-1]=inv[i]*1ll*i%mod;
}
for(int i=0;i<=m;i++){
dp[0][i]=1;
}
int ans=fac[n];
for(int i=1;i<=26;i++){
ans=ans*1ll*inv[toa[i]]%mod;
for(int j=max(0,toa[i]-tob[i]);j<=min(toa[i],tob[i+1]);j++){
(dp[i][j]+=dp[i-1][tob[i]-toa[i]+j]*1ll*C(toa[i],j)%mod)%=mod;
}
for(int j=1;j<=m;j++){
(dp[i][j]+=dp[i][j-1])%=mod;
}
}
// for(int i=1;i<=26;i++){
// for(int j=0;j<=n;j++){
// cout<<dp[i][j]<<" ";
// }
// puts("");
// }
// cout<<ans<<"\n";
printf("%d",ans*1ll*dp[26][0]%mod);
return 0;
}
}
int main(){return asbt::main();}
E. One-X
對于節點 \(p\)，設長度為 \(len\)，則貢獻為 \(p(2^{\lceil\frac{len}{2}\rceil}-1)(2^{\lfloor\frac{len}{2}\rfloor}-1)\)。
擴展一下，對于某一層，若長度為 \(len\) 的點編號之和為 \(p\)，則貢獻可以方便地計算。
而我們知道，線段樹上的一層中，節點維護的區間長度最多只有 \(2\) 個值。
如果不知道：
首先第一層只有 \(1\) 個值。設為 \(len\)。
則第二層最多有兩個值，即 \(\lceil\frac{len}{2}\rceil\) 和 \(\lfloor\frac{len}{2}\rfloor\)。
第三層會出現上面兩個值的一半的上、下取整。而 \(\lceil\frac{\lceil\frac{len}{2}\rceil}{2}\rceil\) 和 \(\lfloor\frac{\lfloor\frac{len}{2}\rfloor}{2}\rfloor\) 最多只相差 \(1\)。于是可以歸納法證明。
于是每一層的 \(len\) 就只有 \(2\) 種情況，直接統計答案即可?？紤]將編號和下傳。顯然左兒子編號之和為當前編號和的二倍，右兒子編號和為當前編號和的二倍再加上當前編號數。復雜度 \(O(\log^2n)\)。
Code
#include<bits/stdc++.h>
#define int long long
#define il inline
#define read(x){\
char ch;\
int fu=1;\
while(!isdigit(ch=getchar()))\
fu-=(ch=='-')<<1;\
x=ch&15;\
while(isdigit(ch=getchar()))\
x=(x<<1)+(x<<3)+(ch&15);\
x*=fu;\
}
#define pii pair<int,int>
#define mp make_pair
#define fir first
#define sec second
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int mod=998244353;
int T,n;
il int qpow(int x,int y){
int res=1;
while(y){
if(y&1){
res=res*1ll*x%mod;
}
x=x*1ll*x%mod,y>>=1;
}
return res;
}
il void solve(){
read(n);
int ans=0;
map<int,pii> cun[70];
cun[1][n]=mp(1,1);
for(int i=1;i<=65;i++){
for(auto j:cun[i]){
int len=j.fir,num=j.sec.fir,sum=j.sec.sec;
if(j.fir==1){
(ans+=sum)%=mod;
continue;
}
(ans+=sum*1ll*(qpow(2,(len+1)>>1)-1)%mod*(qpow(2,len>>1)-1)%mod)%=mod;
(cun[i+1][(len+1)>>1].fir+=num)%=mod;
(cun[i+1][(len+1)>>1].sec+=sum<<1)%=mod;
(cun[i+1][len>>1].fir+=num)%=mod;
(cun[i+1][len>>1].sec+=sum*2+num)%=mod;
}
}
printf("%lld\n",ans);
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
signed main(){
read(T);
while(T--){
solve();
}
return 0;
}
}
signed main(){return asbt::main();}
F. Jellyfish and EVA
設 \(f_u\) 表示從 \(u\) 走到 \(n\) 的概率。有方程：
\[f_u=\sum_{v\in son_u}f_vP_{u\to v}
\]
考慮 Jellyfish 的策略，一定是從 \(u\) 的所有后繼結點中選擇 \(f\) 最大的一個。因此我們需要知道對于出度為 \(i\) 的節點 \(u\)，走到第 \(j\) 優先的點 \(v\) 的概率。記為 \(g_{i,j}\)。則 \(f\) 的轉移方程：
\[f_u=\sum_{v\in son_u}f_vg_{deg_u,i}
\]
其中 \(v\) 是第 \(i\) 優先的點。
考慮轉移 \(g\)，顯然 \(g_{i,1}=\frac{1}{i}\)。考慮使最優先的點被刪去的那個點優先級大于或小于 \(j\)，有方程：
\[g_{i,j}=g_{i-2,j-1}\times\frac{i-j}{i}+g_{i-2,j-2}\times\frac{j-2}{i}
\]
時間復雜度為 \(O(n^2)\)。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define read(x){\
char ch;\
int fu=1;\
while(!isdigit(ch=getchar()))\
fu-=(ch=='-')<<1;\
x=ch&15;\
while(isdigit(ch=getchar()))\
x=(x<<1)+(x<<3)+(ch&15);\
x*=fu;\
}
#define pb push_back
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=5e3+5;
int T,n,m,deg[maxn];
double f[maxn],g[maxn][maxn];
vector<int> e[maxn];
il void solve(){
read(n)read(m);
for(int i=1,u,v;i<=m;i++){
read(u)read(v);
e[u].pb(v),deg[u]++;
}
f[n]=1;
for(int u=n-1;u;u--){
sort(e[u].begin(),e[u].end(),[](const int &x,const int &y){return f[x]>f[y];});
for(int i=0;i<e[u].size();i++){
f[u]+=f[e[u][i]]*g[deg[u]][i+1];
}
}
printf("%.10f\n",f[1]);
for(int i=1;i<=n;i++){
e[i].clear();
f[i]=deg[i]=0;
}
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
g[1][1]=1;
for(int i=2;i<=5e3;i++){
g[i][1]=1.0/i;
for(int j=2;j<=i;j++){
g[i][j]=g[i-2][j-1]*(i-j)/i+g[i-2][j-2]*(j-2)/i;
}
}
read(T);
while(T--){
solve();
}
return 0;
}
}
int main(){return asbt::main();}
G. Another MEX Problem
設 \(f_{i,j}\) 表示用前 \(i\) 個數能否使答案為 \(j\)。顯然可以枚舉最后一段的起點與答案進行 \(O(n^3)\) 轉移。
考慮優化。對于一個區間 \([l,r]\)，如果 \([l+1,r]\) 或 \([l,r-1]\) 的 \(\operatorname{mex}\) 等于 \([l,r]\) 的 \(\operatorname{mex}\)，則用 \([l,r]\) 轉移顯然不優。因此考慮只用無法縮小成 \(\operatorname{mex}\) 不變的子區間的區間進行轉移?？梢杂梅醋C法證明這樣的區間個數是 \(O(n)\) 的。于是復雜度優化為 \(O(n^2)\)。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define pb push_back
using namespace std;
namespace asbt{
namespace IO{
const int bufsz=1<<20;
char ibuf[bufsz],*p1=ibuf,*p2=ibuf;
#define getchar() (p1==p2&&(p2=(p1=ibuf)+fread(ibuf,1,bufsz,stdin),p1==p2)?EOF:*p1++)
template<typename T=int>il T read(){
char ch=getchar();
while(ch<'0'||ch>'9'){
ch=getchar();
}
T x=0;
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x;
}
#undef getchar
}
using IO::read;
il void solve(){
int n=read();
vector<int> a(n+5,0),tong(n+5,0);
vector<vector<int> > mex(n+5,vector<int>(n+5,0));
vector<vector<int> > f(n+5,vector<int>(n+5,0));
vector<vector<int> > e(n+5,vector<int>());
for(int i=1;i<=n;i++){
a[i]=read();
}
for(int l=1;l<=n;l++){
for(int i=0;i<=n;i++){
tong[i]=0;
}
for(int r=l;r<=n;r++){
mex[l][r]=mex[l][r-1];
tong[a[r]]++;
while(tong[mex[l][r]]){
mex[l][r]++;
}
}
}
// for(int l=1;l<=n;l++){
// for(int r=l;r<=n;r++){
// cout<<l<<" "<<r<<" "<<mex[l][r]<<"\n";
// }
// }
for(int i=1;i<=n;i++){
if(!a[i]){
e[i].pb(i);
continue;
}
for(int j=i;j<=n;j++){
if(a[i]>a[j]&&mex[i][j]>a[i]){
e[j].pb(i);
break;
}
}
for(int j=i;j;j--){
if(a[i]>a[j]&&mex[j][i]>a[i]){
e[i].pb(j);
break;
}
}
}
f[0][0]=1;
for(int i=1;i<=n;i++){
f[i]=f[i-1];
for(int j:e[i]){
for(int k=0;k<=n;k++){
if((k^mex[j][i])>n){
continue;
}
f[i][k]|=f[j-1][k^mex[j][i]];
}
}
}
for(int i=n;~i;i--){
if(f[n][i]){
printf("%d\n",i);
break;
}
}
}
int main(){
int T=read();
while(T--){
solve();
}
return 0;
}
}
int main(){return asbt::main();}
H. Travel Plan
對于確定的最大值 \(x\) 和路徑上的點數 \(y\)，對答案的貢獻是好搞的，即為 \(m^{n-y}(x^y-(x-1)^y)\)。又有路徑長度是 \(O(\log n)\) 的，因此我們只需求出每個長度的路徑有多少條。
原圖是一棵完全二叉樹，即只有最后一層是不滿的，切最后一層的點緊貼著左側。我們發現它的左子樹和右子樹中一定有一棵是完全二叉樹，另一棵是滿二叉樹（就是最后一層也滿了）。
于是設 \(g2_i\) 表示在這棵樹中長為 \(i\) 的路徑數，\(g1_{i,j}\) 表示一棵 \(i\) 層的滿二叉樹上長為 \(j\) 的路徑有多少條?？梢灶A處理出 \(g1\)，那么對于一棵樹就只需要遞歸完全二叉子樹了。
考慮 \(g\) 如何轉移，我們再設 \(f\) 表示相應的樹的形態從根出發的長為 \(i\) 的鏈的條數。于是 \(f\) 就可以從兩個子樹的 \(f\) 相加得到，而 \(g\) 的轉移分別是兩棵子樹內的、從根出發的和穿過根的情況。時間復雜度為 \(O(T(m\log n+\log^3n))\)。
Code
#include<bits/stdc++.h>
#define int long long
#define il inline
#define read(x){\
char ch;\
int fu=1;\
while(!isdigit(ch=getchar()))\
fu-=(ch=='-')<<1;\
x=ch&15;\
while(isdigit(ch=getchar()))\
x=(x<<1)+(x<<3)+(ch&15);\
x*=fu;\
}
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=1e5+5;
const int mod=998244353;
int T,n,m,f2[130],g2[130];
int f1[70][130],g1[70][130];
int pw[maxn][130];
il int qpow(int x,int y){
int res=1;
while(y){
if(y&1){
(res*=x)%=mod;
}
(x*=x)%=mod,y>>=1;
}
return res;
}
il int depl(int x){
if(x>n){
return 0;
}
return depl(x<<1)+1;
}
il int depr(int x){
if(x>n){
return 0;
}
return depr(x<<1|1)+1;
}
il bool check(int x){
return depl(x)==depr(x);
}
il void dfs(int x){
if(x<<1>n){
f2[0]=g2[0]=1;
return ;
}
if(x<<1==n){
f2[0]=f2[1]=g2[1]=1;
g2[0]=2;
return ;
}
int d;
if(check(x<<1)){
d=depl(x<<1);
dfs(x<<1|1);
}
else{
d=depl(x<<1|1);
dfs(x<<1);
}
for(int i=0;i<=d<<1;i++){
(g2[i]+=g1[d][i])%=mod;
for(int j=0;j<=i;j++){
(g2[i+2]+=f2[j]*f1[d][i-j])%=mod;
}
}
for(int i=d<<1;i;i--){
f2[i]=(f2[i-1]+f1[d][i-1])%mod;
}
for(int i=0;i<=d<<1;i++){
(g2[i]+=f2[i])%=mod;
}
}
il void solve(){
memset(f2,0,sizeof f2);
memset(g2,0,sizeof g2);
read(n)read(m);
dfs(1);
int ans=0,d=depl(1);
for(int i=0,tmp;i<=2*d-2;i++){
if(i+1>n){
break;
}
tmp=0;
for(int j=1;j<=m;j++){
(tmp+=(pw[j][i+1]-pw[j-1][i+1]+mod)*j)%=mod;
}
// cout<<tmp<<"\n";
(ans+=tmp*g2[i]%mod*qpow(m,n-i-1))%=mod;
}
printf("%lld\n",ans);
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
signed main(){
for(int i=1;i<=60;i++){
f1[i][0]=1;
for(int j=1;j<i;j++){
f1[i][j]=f1[i-1][j-1]*2%mod;
}
for(int j=0;j<=2*i-2;j++){
(g1[i][j]+=g1[i-1][j]*2+f1[i][j])%=mod;
for(int k=0;k<=j;k++){
(g1[i][j+2]+=f1[i-1][k]*f1[i-1][j-k])%=mod;
}
}
}
for(int i=1;i<=1e5;i++){
pw[i][0]=1;
for(int j=1;j<=120;j++){
pw[i][j]=pw[i][j-1]*i%mod;
}
}
read(T);
while(T--){
solve();
}
return 0;
}
}
signed main(){return asbt::main();}
I. Mighty Rock Tower
設 \(f_i\) 表示從第 \(i-1\) 層堆到第 \(i\) 層的期望步數。枚舉往下掉到哪一層，有方程：
\[\begin{aligned}
f_i&=1+p_i^i\sum_{j=1}^{i}f_j+\sum_{j=1}^{i-1}p_i^{i-j}(1-p_i)\sum_{k=j+1}^{i}f_k\\
&=1+p_i^i\sum_{j=1}^{i}f_j+\sum_{j=1}^{i-1}p_i^{i-j}\sum_{k=j+1}^{i}f_k-\sum_{j=1}^{i-1}p_i^{i-j+1}\sum_{k=j+1}^{i}f_k\\
&=1+\sum_{j=0}^{i-1}p_i^{i-j}\sum_{k=j+1}^{i}f_k-\sum_{j=0}^{i-2}p_i^{i-j}\sum_{k=j+2}^{i}f_k\\
&=1+p_if_i+\sum_{j=0}^{i-2}p_i^{i-j}f_{j+1}
\end{aligned}
\]
移項，得：
\[f_i=\frac{1+\sum_{j=0}^{i-2}p_i^{i-j}f_{j+1}}{1-p_i}
\]
考慮前綴和優化，但是式子中有一個 \(p_i^{i-j}\) 比較討厭，考慮到 \(p_i\) 只有 \(100\) 種取值，我們只要做 \(100\) 個前綴和就行了。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define read(x){\
char ch;\
int fu=1;\
while(!isdigit(ch=getchar()))\
fu-=(ch=='-')<<1;\
x=ch&15;\
while(isdigit(ch=getchar()))\
x=(x<<1)+(x<<3)+(ch&15);\
x*=fu;\
}
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=2e5+5,mod=998244353;
int n,a[maxn],f[maxn];
int g[105][maxn],p[maxn];
il int qpow(int x,int y){
int res=1;
while(y){
if(y&1){
res=res*1ll*x%mod;
}
x=x*1ll*x%mod,y>>=1;
}
return res;
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
read(n);
int inv100=qpow(100,mod-2);
for(int i=1;i<=n;i++){
read(a[i]);
}
for(int i=0;i<100;i++){
p[i]=i*1ll*inv100%mod;
}
int ans=0;
for(int i=1;i<=n;i++){
for(int j=0;j<100;j++){
g[j][i]=(p[j]*1ll*g[j][i-1]+p[j]*1ll*p[j]%mod*f[i-1])%mod;
}
f[i]=(1+g[a[i]][i])*1ll*qpow((1-p[a[i]]+mod)%mod,mod-2)%mod;
(ans+=f[i])%=mod;
}
printf("%d",ans);
return 0;
}
}
int main(){return asbt::main();}
J. BZOJ2164 采礦
問題顯然可以分為兩部分：\(u\) 的子樹內和 \(fa_u\) 到 \(v\) 的鏈上。前者需要樹上背包，后者需要取 \(\max\)。
考慮用線段樹維護這兩個值。子樹內的答案只需要一次區間查詢，再加上樹上背包的 \(O(m^2)\)，總共為 \(O(m^2\log n)\)。鏈上的答案需要進行樹鏈剖分。取 \(\max\) 線性復雜度即可完成，因此為 \(O(m\log^2n)\)?？倳r間復雜度為 \(O(C(m^2\log n+m\log^2n))\)。修改就直接在線段樹上單點更新即可。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define read(x){\
char ch;\
int fu=1;\
while(!isdigit(ch=getchar()))\
fu-=(ch=='-')<<1;\
x=ch&15;\
while(isdigit(ch=getchar()))\
x=(x<<1)+(x<<3)+(ch&15);\
x*=fu;\
}
#define pb push_back
#define lid id<<1
#define rid id<<1|1
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
namespace Data{
int A,B,Q,X=1<<16,Y=(1ll<<31)-1;
il void init(){
read(A)read(B)read(Q);
}
il int getint(){
A=((A^B)+(B/X)+(B*X))&Y;
B=((A^B)+(A/X)+(A*X))&Y;
return (A^B)%Q;
}
}
const int maxn=2e4+5;
int n,m,q,fa[maxn],a[maxn][55];
int dep[maxn],sz[maxn],hes[maxn];
int top[maxn],dfn[maxn],idx[maxn],cnt;
vector<int> e[maxn];
il void dfs1(int u){
dep[u]=dep[fa[u]]+1;
sz[u]=1;
int mxs=0;
for(int v:e[u]){
dfs1(v);
sz[u]+=sz[v];
if(mxs<sz[v]){
mxs=sz[v],hes[u]=v;
}
}
}
il void dfs2(int u){
dfn[u]=++cnt;
idx[cnt]=u;
if(!top[u]){
top[u]=u;
}
if(hes[u]){
top[hes[u]]=top[u];
dfs2(hes[u]);
}
for(int v:e[u]){
if(v!=hes[u]){
dfs2(v);
}
}
}
struct node1{
int f[55];
node1(){
memset(f,0,sizeof f);
}
il int&operator[](int x){
return f[x];
}
il node1 operator+(node1 x)const{
node1 res;
for(int i=0;i<=m;i++){
for(int j=0;j<=m-i;j++){
res[i+j]=max(res[i+j],f[i]+x[j]);
}
}
return res;
}
}tr1[maxn<<2];
struct node2{
int f[55];
node2(){
memset(f,0,sizeof f);
}
il int&operator[](int x){
return f[x];
}
il node2 operator+(node2 x)const{
node2 res;
for(int i=0;i<=m;i++){
res[i]=max(f[i],x[i]);
}
return res;
}
}tr2[maxn<<2];
il void pushup(int id){
tr1[id]=tr1[lid]+tr1[rid];
tr2[id]=tr2[lid]+tr2[rid];
}
il void pushtag(int id,int p){
for(int i=0;i<=m;i++){
tr1[id][i]=tr2[id][i]=a[idx[p]][i];
}
}
il void build(int id,int l,int r){
if(l==r){
pushtag(id,l);
return ;
}
int mid=(l+r)>>1;
build(lid,l,mid);
build(rid,mid+1,r);
pushup(id);
}
il void upd(int id,int l,int r,int p){
if(l==r){
pushtag(id,l);
return ;
}
int mid=(l+r)>>1;
if(p<=mid){
upd(lid,l,mid,p);
}
else{
upd(rid,mid+1,r,p);
}
pushup(id);
}
il node1 query1(int id,int L,int R,int l,int r){
if(L>=l&&R<=r){
return tr1[id];
}
int mid=(L+R)>>1;
if(r<=mid){
return query1(lid,L,mid,l,r);
}
if(l>mid){
return query1(rid,mid+1,R,l,r);
}
return query1(lid,L,mid,l,r)+query1(rid,mid+1,R,l,r);
}
il node2 query2(int id,int L,int R,int l,int r){
if(L>=l&&R<=r){
return tr2[id];
}
int mid=(L+R)>>1;
if(r<=mid){
return query2(lid,L,mid,l,r);
}
if(l>mid){
return query2(rid,mid+1,R,l,r);
}
return query2(lid,L,mid,l,r)+query2(rid,mid+1,R,l,r);
}
il node2 query(int u,int v){
if(top[u]==top[v]){
return query2(1,1,n,dfn[v],dfn[u]);
}
node2 res=query2(1,1,n,dfn[top[u]],dfn[u]);
u=fa[top[u]];
while(top[u]!=top[v]){
res=res+query2(1,1,n,dfn[top[u]],dfn[u]);
u=fa[top[u]];
}
return res+query2(1,1,n,dfn[v],dfn[u]);
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
// cout<<cplx::usdmem();
read(n)read(m);
Data::init();
for(int i=2;i<=n;i++){
read(fa[i]);
e[fa[i]].pb(i);
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
a[i][j]=Data::getint();
// cout<<a[i][j]<<" ";
}
sort(a[i]+1,a[i]+m+1);
// for(int j=1;j<=m;j++){
// cout<<a[i][j]<<" ";
// }
// puts("");
}
dfs1(1),dfs2(1);
build(1,1,n);
read(q);
while(q--){
int opt,u,v;
read(opt)read(u);
if(opt){
read(v);
node1 res1=query1(1,1,n,dfn[u],dfn[u]+sz[u]-1);
int ans=0;
if(u==v){
for(int i=0;i<=m;i++){
ans=max(ans,res1[i]);
}
}
else{
node2 res2=query(fa[u],v);
for(int i=0;i<=m;i++){
for(int j=0;j<=m-i;j++){
ans=max(ans,res1[i]+res2[j]);
}
}
}
printf("%d\n",ans);
}
else{
for(int i=1;i<=m;i++){
a[u][i]=Data::getint();
}
sort(a[u]+1,a[u]+m+1);
upd(1,1,n,dfn[u]);
// for(int i=1;i<=m;i++){
// cout<<a[u][i]<<" ";
// }
// puts("");
}
}
return 0;
}
}
int main(){return asbt::main();}
浙公網安備 33010602011771號