動態(tài)規(guī)劃題單4
91.[ARC114F] Permutation Division
Bob 的策略一定是按照開頭從大到小排。
所以最后的答案一定不小于原來的排列。
所以我們要使得最后的排列 \(Q\) 和原排列 \(P\) 的 LCP 盡可能長。
也就是說最后分段的形式滿足：(\(t_i\) 是每一段的開頭)
- \(p_1=p_{t_1} > p_{t_2} > ... > p_{t_m}\)。
不然的話，Bob 可以把后面的放到前面去。
這些段就是 LCP 長度。 - \(p_{t_{m+1}},p_{t_{m+2}},...,p_{t_k} < p_{t_m}\)。
此時 Bob 會把 \(p_{t_{m+1}},p_{t_{m+2}},...,p_{t_k}\) 的 max 作為 \(q_{t_{m+1}}\)。
考慮二分 LCP 的長度 \(len\)，枚舉 \(m\)，對于每個 \(m\) 我肯定是求出 \(p_{t_m}\) 的最大值，這樣后面的段的選擇會變多，設(shè) \([len+1,n]\) 有 \(y\) 個數(shù) < \(p_{t_m}\) 那么，如果 \(y+m\ge k\) 就是可行的，而 \(p_{t_{m+1}},p_{t_{m+2}},...,p_{t_k}\) 一定是選擇最小的那幾個。
于是問題變成求長度為 \(m\) 的下降子序列的末尾的最大值，這可以用 \(O(n\log n)\) 的 DP 來實(shí)現(xiàn)。
code
#include<bits/stdc++.h>
#define PII pair<int,int>
#define fi first
#define se second
using namespace std;
const int N=2e5+5;
inline int read(){
int w = 1, s = 0;
char c = getchar();
for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
return s * w;
}
int n,k,a[N],b[N],pos[N],g[N],d,cnt[N],t[N];
bool flag[N];
int check(int mid){ //返回最大的 m
if(mid==0) return 0;
for(int i=1;i<=n;i++) g[i]=0;
g[1]=-a[1],d=1; //取 - 變成求最長上升子序列
for(int i=2;i<=mid;i++){
int l=upper_bound(g+1,g+d+1,-a[i])-g;
if(l==1) continue;
g[l]=-a[i];
d=max(d,l);
}
for(int i=1;i<=n;i++) cnt[i]=0;
for(int i=mid+1;i<=n;i++) cnt[a[i]]++;
for(int i=1;i<=n;i++) cnt[i]+=cnt[i-1]; //cnt[i] 幾位 [len+1,n] 中小于 i 的個數(shù)
for(int m=d;m>=1;m--){
if(m+cnt[-g[m]]>=k) return m;
}
return 0;
}
signed main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
n=read(),k=read();
for(int i=1;i<=n;i++) a[i]=read(),b[i]=a[i],pos[a[i]]=i;
int l=1,r=n,mid,len=0;
while(l<=r){
mid=(l+r)>>1;
if(check(mid)) len=mid,l=mid+1;
else r=mid-1;
}
int m=min(k,check(len));
sort(b+len+1,b+n+1);
for(int i=len+1,j=1;j<=k-m;i++,j++) t[j]=pos[b[i]],flag[t[j]]=true;
for(int i=1;i<=len;i++) printf("%d ",a[i]);
for(int i=k-m;i>=1;i--){ //注意 Bob 對于后面那幾段是從大到小放的
for(int j=t[i];j<=n&&(j==t[i] || !flag[j]);j++){
printf("%d ",a[j]);
}
}
puts("");
return 0;
}
92.[SDOI2011] 消耗戰(zhàn)
虛樹上 dp 的裸題。
我們稱那些有資源的點(diǎn)為關(guān)鍵點(diǎn)
首先這題單次詢問有個 \(O(n)\) 的樹形 DP。
即設(shè) \(f_u\) 表示 \(u\) 號點(diǎn)與其子樹中的所有關(guān)鍵點(diǎn)不連通的最小代價(jià)，那么枚舉兒子 \(v\)：
- \(v\) 不是關(guān)鍵點(diǎn)：\(f_u += \min(f_v,w(u,v))\)。
- \(v\) 是關(guān)鍵點(diǎn)：\(f_u += w(u,v)\)。
然后對所有關(guān)鍵點(diǎn)建出虛樹在虛樹上做這個 DP 就可以了。（應(yīng)該不會有人看到 \(92\) 題了還不會虛樹吧。）
code
#include<bits/stdc++.h>
#define int long long
#define PII pair<int,int>
#define fi first
#define se second
using namespace std;
const int N=2.5e5+5;
inline int read(){
int w = 1, s = 0;
char c = getchar();
for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
return s * w;
}
int n,T,tot,head[N],to[N<<1],val[N<<1],Next[N<<1];
void add(int u,int v,int w){
to[++tot]=v,val[tot]=w,Next[tot]=head[u],head[u]=tot;
}
int dfn[N],dep[N],fa[N][25],ming[N][25],num;
void dfs(int u){
dfn[u]=++num;
for(int i=head[u];i;i=Next[i]){
int v=to[i],w=val[i];
if(v==fa[u][0]) continue;
fa[v][0]=u,ming[v][0]=w;
dep[v]=dep[u]+1;
dfs(v);
}
}
int LCA(int x,int y){
if(dep[x]<dep[y]) swap(x,y);
for(int t=20;t>=0;t--)
if(dep[fa[x][t]]>=dep[y]) x=fa[x][t];
if(x==y) return x;
for(int t=20;t>=0;t--)
if(fa[x][t] != fa[y][t]) x=fa[x][t],y=fa[y][t];
return fa[x][0];
}
int ask(int x,int y){
int Min=LLONG_MAX;
if(dep[x]<dep[y]) swap(x,y);
for(int t=20;t>=0;t--)
if(dep[fa[x][t]]>=dep[y]) Min=min(Min,ming[x][t]),x=fa[x][t];
if(x==y) return Min;
for(int t=20;t>=0;t--)
if(fa[x][t] != fa[y][t]) Min=min({Min,ming[x][t],ming[y][t]}),x=fa[x][t],y=fa[y][t];
return min({Min,ming[x][0],ming[y][0]});
}
int k,a[N],t[N],cnt;
bool flag[N];
vector<PII> G[N];
void Build_Virtual_Tree(){
sort(a+1,a+k+1,[&](int x,int y){return dfn[x]<dfn[y];});
cnt=0;
t[++cnt]=1,t[++cnt]=a[k];
for(int i=1;i<k;i++){
t[++cnt]=a[i];
t[++cnt]=LCA(a[i],a[i+1]);
}
sort(t+1,t+cnt+1,[&](int x,int y){return dfn[x]<dfn[y];});
cnt=unique(t+1,t+cnt+1)-t-1;
for(int i=1;i<=cnt;i++) G[t[i]].clear();
for(int i=1;i<cnt;i++){
int lca=LCA(t[i],t[i+1]);
G[lca].push_back({t[i+1] , ask(t[i+1],lca)}); //單向邊即可
}
}
int f[N];
void DP(int u){
f[u]=0;
for(PII e:G[u]){
int v=e.fi,w=e.se;
DP(v);
if(flag[v]) f[u]+=w;
else f[u]+=min(w,f[v]);
}
}
signed main(){
n=read();
for(int i=1;i<n;i++){
int u=read(),v=read(),w=read();
add(u,v,w),add(v,u,w);
}
dep[1]=1;
dfs(1);
for(int i=1;i<=20;i++){
for(int u=1;u<=n;u++){
fa[u][i]=fa[fa[u][i-1]][i-1];
ming[u][i]=min(ming[u][i-1] , ming[fa[u][i-1]][i-1]);
}
}
T=read();
while(T--){
k=read();
for(int i=1;i<=k;i++) a[i]=read(),flag[a[i]]=true;
Build_Virtual_Tree();
DP(1);
printf("%lld\n",f[1]);
for(int i=1;i<=k;i++) flag[a[i]]=false;
}
return 0;
}
93.[HEOI2014] 大工程
也是裸題。
建立虛樹，然后簡單樹形 DP 求出：\(Size_i\) 表示 \(i\) 子樹內(nèi)關(guān)鍵點(diǎn)數(shù)量，\(f_i\) 表示 \(i\) 到 \(i\) 子樹內(nèi)關(guān)鍵點(diǎn)的距離和，\(g_i\) 表示最小距離，\(h_i\) 表示最大距離。
注意到求最終答案時一條路徑在有根樹上肯定形如 \(x\to lca\to y\) 所以只要在 \(lca\) 處統(tǒng)計(jì)他即可。
所以求最終答案時只需要合并不同子樹內(nèi)的答案，具體的:
在用兒子 \(v\) 更新 \(u\) 的 DP 值之前， \(u\) 存的是 \(v\) 之前所有 \(v\) 的兄弟的信息，那么更新全局答案 \((sum,Min,Max)\):
- \(f_u\times Size_v + w(u,v)\times Size_u\times Size_v + f_v\times Size_u \to sum\)。
- \(Min= \min(Min, g_u+w(u,v)+g_v)\)。
- \(Max= \max(Max, h_u+w(u,v)+h_v)\)。
\(w(u,v)\) 表示 \(u,v\) 在虛樹上的邊權(quán)，在原樹中就是 \(dep_v-dep_u\)。
code
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5;
inline int read(){
int w = 1, s = 0;
char c = getchar();
for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
return s * w;
}
int n,T,tot,head[N],to[N<<1],val[N<<1],Next[N<<1];
void add(int u,int v){
to[++tot]=v,Next[tot]=head[u],head[u]=tot;
}
int dfn[N],dep[N],fa[N][25],num;
void dfs(int u){
dfn[u]=++num;
for(int i=head[u];i;i=Next[i]){
int v=to[i],w=val[i];
if(v==fa[u][0]) continue;
fa[v][0]=u;
dep[v]=dep[u]+1;
dfs(v);
}
}
int LCA(int x,int y){
if(dep[x]<dep[y]) swap(x,y);
for(int t=20;t>=0;t--)
if(dep[fa[x][t]]>=dep[y]) x=fa[x][t];
if(x==y) return x;
for(int t=20;t>=0;t--)
if(fa[x][t] != fa[y][t]) x=fa[x][t],y=fa[y][t];
return fa[x][0];
}
int k,a[N],t[N],cnt;
bool flag[N];
vector<int> G[N];
void Build_Virtual_Tree(){
sort(a+1,a+k+1,[&](int x,int y){return dfn[x]<dfn[y];});
cnt=0;
t[++cnt]=1,t[++cnt]=a[k];
for(int i=1;i<k;i++){
t[++cnt]=a[i];
t[++cnt]=LCA(a[i],a[i+1]);
}
sort(t+1,t+cnt+1,[&](int x,int y){return dfn[x]<dfn[y];});
cnt=unique(t+1,t+cnt+1)-t-1;
for(int i=1;i<=cnt;i++) G[t[i]].clear();
for(int i=1;i<cnt;i++){
int lca=LCA(t[i],t[i+1]);
G[lca].push_back(t[i+1]);
}
}
int sum,ming,maxn,Size[N],f[N],g[N],h[N];
void DP(int u){
Size[u]=flag[u];
f[u]=0;
if(flag[u]) g[u]=h[u]=0;
else g[u]=INT_MAX,h[u]=INT_MIN;
for(int v:G[u]){
DP(v);
int w=dep[v]-dep[u];
sum += f[u]*Size[v] + w*Size[u]*Size[v] + f[v]*Size[u];
ming = min(ming , g[u]+w+g[v]);
maxn = max(maxn, h[u]+w+h[v]);
Size[u]+=Size[v];
f[u]+=f[v]+Size[v]*w;
g[u]=min(g[u],g[v]+w);
h[u]=max(h[u],h[v]+w);
}
}
signed main(){
n=read();
for(int i=1;i<n;i++){
int u=read(),v=read();
add(u,v),add(v,u);
}
dep[1]=1;
dfs(1);
for(int i=1;i<=20;i++){
for(int u=1;u<=n;u++){
fa[u][i]=fa[fa[u][i-1]][i-1];
}
}
T=read();
while(T--){
k=read();
for(int i=1;i<=k;i++) a[i]=read(),flag[a[i]]=true;
Build_Virtual_Tree();
sum=0,ming=INT_MAX,maxn=INT_MIN;
DP(1);
printf("%lld %lld %lld\n",sum,ming,maxn);
for(int i=1;i<=k;i++) flag[a[i]]=false;
}
return 0;
}
94.[HNOI2014] 世界樹
我也不太確定這個題到底該不該放進(jìn)來，就當(dāng)復(fù)習(xí)虛樹吧。
虛樹是顯然的。
設(shè) \(ans_i\) 表示關(guān)鍵點(diǎn) \(i\) 最后的答案，稱原樹上離點(diǎn) \(u\) 最近的關(guān)鍵點(diǎn)為 \(u\) 的對應(yīng)點(diǎn)。
對于虛樹上的點(diǎn)，可以換根 DP 求出 \(f_i\) 表示距離 \(i\) 號點(diǎn)最近的關(guān)鍵點(diǎn)的編號，我相信大家都會。
那對于不是虛樹上的點(diǎn)怎么辦?
會發(fā)現(xiàn)一個點(diǎn)不在虛樹上只有兩種情況:
- 原樹上，他的這棵子樹里一個關(guān)鍵點(diǎn)都沒有。
- 他在虛樹上的兩個點(diǎn)在原樹的那條鏈上。
對應(yīng)到虛樹上可以變?yōu)?
- 一個虛樹節(jié)點(diǎn) \(u\)，他在原樹上有一個兒子 \(v\)，但 \(v\) 的子樹中沒有關(guān)鍵點(diǎn)，此時 \(v\) 子樹中的所有點(diǎn)的對應(yīng)點(diǎn)一定都是 \(f_u\)，所以把 \(ans_{f_u}\) 加上 \(Size_v\)。
- 虛樹上的兩個節(jié)點(diǎn) \(x,y\) 其中 \(x\) 是 \(y\) 的父親，它們在原樹上可能只是祖先后代關(guān)系，它們之間的鏈上還有一些點(diǎn)。
假設(shè)其中有個點(diǎn) \(c\)，當(dāng)然 \(c\) 上還可能掛了一些子樹，顯然這些子樹的 \(f\) 值和 \(c\) 的 \(f\) 值是一樣。
我們可以找到這條鏈上的一個分割點(diǎn) \(u\)，使得鏈上 \([u,y)\) 這段區(qū)間的對應(yīng)點(diǎn)都是 \(f_y\)，\((x,u)\) 這段區(qū)間的對應(yīng)點(diǎn)都是 \(f_x\)。
那具體怎么求呢？因?yàn)槲覀兪遣荒苋ピ瓨渖媳闅v的。
對于 1. 中的情況：我們可以轉(zhuǎn)換一下，求一個虛樹點(diǎn) \(u\) 所有不存在關(guān)鍵點(diǎn)的子樹的大小的和，可以容斥用 \(Size_u\) 先 \(-1\) （自己），再減去所有有關(guān)鍵點(diǎn)的子樹的大小。
求有關(guān)鍵點(diǎn)的子樹大小只需要遍歷 \(u\) 虛樹上的每個兒子 \(son\)，在原樹上倍增求出 \(son\) 在原樹上的 \(dep_{son}-dep_u-1\) 級祖先 \(v\)，那么 \(v\) 就是 \(u\) 在原樹上的兒子，再讓 \(Size_u\) 減去 \(Size_v\) 即可。
最后 \(Size_u \to ans_{f_u}\)，注意 \(Size_u\) 還要還原。
對于 2. 中的情況：還是一樣的對每個 \(x\)，枚舉虛樹上的兒子 \(y\)，然后還是倍增求出 \(x\) 在原樹上含有 \(y\) 的那個兒子 \(v\)，分界點(diǎn) \(u\) 是可以二分/倍增求的。
求出 \(u,v\) 之后就可以更新答案了：\(Size_v-Size_u \to ans_{f_x}\) ， \(Size_u-Size_y \to ans_{f_y}\)。
一定要注意不是用 \(Size_x-Size_u\) 去更新 \(ans_{f_x}\)。
復(fù)雜度是 \(O(\sum m \times \log n)\) 或者 \(O(\sum m \times \log^2 n)\)（如果你用二分套倍增的話）。
code
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5;
inline int read(){
int w = 1, s = 0;
char c = getchar();
for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
return s * w;
}
int n,T,tot,head[N],to[N<<1],val[N<<1],Next[N<<1];
void add(int u,int v){
to[++tot]=v,Next[tot]=head[u],head[u]=tot;
}
int dfn[N],dep[N],Size[N],fa[N][25],num;
void dfs(int u){
dfn[u]=++num;
Size[u]=1;
for(int i=head[u];i;i=Next[i]){
int v=to[i],w=val[i];
if(v==fa[u][0]) continue;
fa[v][0]=u;
dep[v]=dep[u]+1;
dfs(v);
Size[u]+=Size[v];
}
}
int LCA(int x,int y){
if(dep[x]<dep[y]) swap(x,y);
for(int t=20;t>=0;t--)
if(dep[fa[x][t]]>=dep[y]) x=fa[x][t];
if(x==y) return x;
for(int t=20;t>=0;t--)
if(fa[x][t] != fa[y][t]) x=fa[x][t],y=fa[y][t];
return fa[x][0];
}
int Get(int x,int len){
for(int t=20;t>=0;t--) if(len>>t&1) x=fa[x][t];
return x;
}
int dist(int x,int y){return dep[x]+dep[y]-2*dep[LCA(x,y)];}
int k,h[N],a[N],t[N],cnt;
bool flag[N];
vector<int> G[N];
void Build_Virtual_Tree(){
sort(a+1,a+k+1,[&](int x,int y){return dfn[x]<dfn[y];});
cnt=0;
t[++cnt]=1,t[++cnt]=a[k];
for(int i=1;i<k;i++){
t[++cnt]=a[i];
t[++cnt]=LCA(a[i],a[i+1]);
}
sort(t+1,t+cnt+1,[&](int x,int y){return dfn[x]<dfn[y];});
cnt=unique(t+1,t+cnt+1)-t-1;
for(int i=1;i<=cnt;i++) G[t[i]].clear();
for(int i=1;i<cnt;i++){
int lca=LCA(t[i],t[i+1]);
G[lca].push_back(t[i+1]);
}
}
int f[N],ans[N];
void DP1(int u){ //先求子樹中的關(guān)鍵點(diǎn)到 u 的距離最短的點(diǎn)
f[u]=(flag[u])?u:-1;
for(int v:G[u]){
DP1(v);
if(f[u]==-1) f[u]=f[v];
else if(dist(f[u],u) > dist(f[v],u)) f[u]=f[v];
else if(dist(f[u],u) == dist(f[v],u)) f[u]=min(f[u],f[v]);
}
}
void DP2(int u){ //換根
for(int v:G[u]){
//用 u 取更新兒子,這里直接更新就可以，不需要考慮 f[u] 有沒有可能在 v 子樹的情況，因?yàn)檫@樣一定不會用 f[u] 去更新 f[v]
if(f[v]==-1) f[v]=f[u];
else if(dist(v,f[v]) > dist(v,f[u])) f[v]=f[u];
else if(dist(v,f[v]) == dist(v,f[u])) f[v]=min(f[v],f[u]);
DP2(v);
}
ans[f[u]]++;
}
int check(int u,int x,int y){
if(dist(u,x) < dist(u,y)) return x;
else if(dist(u,x) > dist(u,y)) return y;
else return min(x,y);
}
void dfs1(int u){ //變量名稍有不同
int tmp=Size[u]-1; //tmp 是處理第一種情況的
for(int v:G[u]){
int x=Get(v,dep[v]-dep[u]-1);
tmp-=Size[x];
int l=1,r=dep[v]-dep[u]-1,mid,y=v;
while(l<=r){
mid=(l+r)>>1;
if(check(Get(v,mid) , f[v] , f[u])==f[v]) l=mid+1,y=Get(v,mid);
else r=mid-1;
}
ans[f[u]]+=Size[x]-Size[y];
ans[f[v]]+=Size[y]-Size[v];
dfs1(v);
}
ans[f[u]]+=tmp;
}
signed main(){
n=read();
for(int i=1;i<n;i++){
int u=read(),v=read();
add(u,v),add(v,u);
}
dep[1]=1;
dfs(1);
for(int i=1;i<=20;i++){
for(int u=1;u<=n;u++){
fa[u][i]=fa[fa[u][i-1]][i-1];
}
}
T=read();
while(T--){
k=read();
for(int i=1;i<=k;i++) h[i]=a[i]=read(),ans[a[i]]=0,flag[a[i]]=true;
Build_Virtual_Tree();
DP1(1);
DP2(1);
dfs1(1); //求全局答案
for(int i=1;i<=k;i++) printf("%d ",ans[h[i]]); //不是 a[i],因?yàn)?a[i] 已經(jīng)被排序了
puts("");
for(int i=1;i<=k;i++) flag[a[i]]=false;
}
return 0;
}
95.[HNOI/AHOI2018] 毒瘤
來一道不是那么簡單的虛樹題。
我保證這是最后一道虛樹題了。
題解區(qū)還有 ddp 和 廣義串并聯(lián)圖 的做法，感興趣的可以去看。
這個題就是求一個圖的獨(dú)立集個數(shù)。
對于一個樹的情況，我們有 DP:
- \(f_{u,0}=\prod_{v \in son(u)} f_{v,0}+f_{v,1}\)。
- \(f_{u,1}=\prod_{v \in son(u)} f_{v,0}\)。
會發(fā)現(xiàn)非樹邊只有 \(m-n+1\le 11\) 條，對于這些非樹邊 \((u,v)\) 的兩個端點(diǎn)狀態(tài)只有三種：\((0,0),(0,1),(1,0)\)。
而且會發(fā)現(xiàn)假設(shè) \(u\) 在樹上是 \(v\) 的祖先（無向圖搜索樹沒有橫插邊），那么我們其實(shí)只關(guān)心 \(u\) 的狀態(tài)是什么，即如果 \(u\) 欽定為 \(0\)，那對 \(v\) 是沒有影響的。
所以 \((0,0)\) 和 \((0,1)\) 可以合并成一個情況，合起來之后就只需要?dú)J定 \(u\) 的狀態(tài)是什么。
暴力枚舉是 \(O(2^{11} n)\)。
會發(fā)現(xiàn)對 DP 產(chǎn)生影響的只有這 \(22\) 個點(diǎn)，考慮對他們建立虛樹。
但虛樹上明顯不能用上面那個式子，我們來看虛樹上的一條邊 \((u,v)\) 在原樹上對應(yīng)的那條鏈：\(u \to x_1 \to x_2 \to ... \to x_k \to v\)（\(u\) 是鏈頂）。
對于這條鏈上的一個點(diǎn) \(i\)，如果定義 \(g_{i,0}=\prod f_{j,0} + f_{j,1}，g_{i,1}=\prod f_{j,0}\)，其中 \(j\) 是原樹上 \(i\) 不在這條鏈上的兒子。
那么假設(shè)此時我們已經(jīng)知道 \(v\) 的 \(f\) 值了，那么我們嘗試暴力推導(dǎo)出這條鏈上其他點(diǎn)的 \(f\) 值:
(\(1\))
- \(f_{x_k,0} = g_{x_k,0} \times (f_{v,0} + f_{v,1})\)。
- \(f_{x_k,1} = g_{x_k,1} \times f_{v,0}\)。
(\(2\))
- \(f_{x_{k-1},0}\)
\(= g_{x_{k-1},0} \times (f_{x_k,0} + f_{x_k,1})\)
\(= g_{x_{k-1},0} \times (g_{x_k,0} \times (f_{v,0} + f_{v,1}) + g_{x_k,1} \times f_{v,0})\)
\(= ( g_{x_{k-1},0} \times (g_{x_k,0} + g_{x_k,1}) ) \times f_{v,0} + (g_{x_{k-1},0} \times g_{x_k,0}) \times f_{v,1}\)。 - \(f_{x_{k-1},1}\)
\(= g_{x_{k-1},1} \times f_{x_k,0}\)
\(= g_{x_{k-1},1} \times g_{x_k,0} \times (f_{v,0} + f_{v,1})\)
\(= g_{x_{k-1},1} \times g_{x_k,0} \times f_{v,0} + g_{x_{k-1},1} \times g_{x_k,0} \times f_{v,1}\)。
...
(\(k+1\))
- \(f_{u,0} = k_{v,0,0}\times f_{v,0} + k_{v,1,0}\times f_{v,1}\)。
- \(f_{u,1} = k_{v,0,1}\times f_{v,0} + k_{v,1,1}\times f_{v,1}\)。
會發(fā)現(xiàn)不管這個虛樹上每個點(diǎn)的狀態(tài)欽定為什么，一條邊 \((u,v)\) 的系數(shù) \(k_{v,0/1,0/1}\) 是不變的。
我們只要算出每條邊的系數(shù)就可以快速進(jìn)行虛樹上的樹形 DP。
求系數(shù)其實(shí)也不用上面寫出來的那么麻煩，程序里面你就模擬展開過程即可。
容易證明暴力對于每一條鏈 \((u,v)\) 去計(jì)算每個鏈上的點(diǎn)的 \(g\) 值和系數(shù)的總復(fù)雜度是 \(O(n)\) 的。
但此時會有個問題，就是 \(u\) 可能在虛樹上不止一個兒子，即他可能還有一個虛樹上的兒子 \(w\)，那在處理 \((u,v)\) 算 \(g_u\) 時，會需要用到 \(w\) 那棵子樹的 DP 值，這樣當(dāng)去處理 \((u,w)\) 時就算重了。
處理方法也比較簡單，把 \(g\) 的定義改一下:
\(g_{i,0}=\prod f_{j,0} + f_{j,1}，g_{i,1}=\prod f_{j,0}\)，其中 \(j\) 是 \(i\) 在原樹上的兒子，且 \(j\) 這棵子樹里不存在虛樹上的點(diǎn)。
容易發(fā)現(xiàn)那些 \(x_1,x_2,...,x_k\) 的 \(g\) 值還是不變的。
但注意的是此時在算 \(k_{v,0/1,0/1}\) 時就不要再把 \(u\) 的 \(g\) 值算進(jìn)去了，即此時 \(k_{v,0,0}\times f_{v,0} + k_{v,1,0}\times f_{v,1}\) 算出來的并不是 \(f_{u,0}\) 而是 \(f_{x_k,0}\)。
那么在虛樹上 DP 時，\(f_{u,0}\) 的值就是:
復(fù)雜度是：\(O(2^K K)\)，\(K=m-n+1\)。
code
#include<bits/stdc++.h>
#define PII pair<int,int>
#define int long long
#define fi first
#define se second
using namespace std;
const int N=1e5+15,mod=998244353;
inline int read(){
int w = 1, s = 0;
char c = getchar();
for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
return s * w;
}
int n,m,tot,head[N],to[N<<1],Next[N<<1];
void add(int u,int v){
to[++tot]=v,Next[tot]=head[u],head[u]=tot;
}
int dfn[N],dep[N],fa[N][25],num,cnt;
PII e[N]; //存非樹邊
void dfs1(int u){
dfn[u]=++num;
for(int i=head[u];i;i=Next[i]){
int v=to[i];
if(v==fa[u][0]) continue;
if(!dfn[v]){
fa[v][0]=u,dep[v]=dep[u]+1;
dfs1(v);
}
else if(dfn[v]<dfn[u]) e[++cnt]={v,u};
}
}
int LCA(int x,int y){
if(dep[x]<dep[y]) swap(x,y);
for(int t=20;t>=0;t--)
if(dep[fa[x][t]]>=dep[y]) x=fa[x][t];
if(x==y) return x;
for(int t=20;t>=0;t--)
if(fa[x][t] != fa[y][t]) x=fa[x][t],y=fa[y][t];
return fa[x][0];
}
int k,h[N],a[N],t[N],c;
bool flag[N];
vector<int> G[N];
void Build_Virtual_Tree(){
sort(a+1,a+k+1,[&](int x,int y){return dfn[x]<dfn[y];});
k=unique(a+1,a+k+1)-a-1;
c=0;
t[++c]=1;
if(k) t[++c]=a[k];
for(int i=1;i<k;i++){
t[++c]=a[i];
t[++c]=LCA(a[i],a[i+1]);
}
sort(t+1,t+c+1,[&](int x,int y){return dfn[x]<dfn[y];});
c=unique(t+1,t+c+1)-t-1;
for(int i=1;i<=c;i++) flag[t[i]]=true,G[t[i]].clear();
for(int i=1;i<c;i++){
int lca=LCA(t[i],t[i+1]);
G[lca].push_back(t[i+1]);
}
}
void Init(){
n=read(),m=read();
for(int i=1;i<=m;i++){
int u=read(),v=read();
add(u,v),add(v,u);
}
dep[1]=1;
dfs1(1);
for(int i=1;i<=20;i++)
for(int u=1;u<=n;u++)
fa[u][i]=fa[fa[u][i-1]][i-1];
for(int i=1;i<=cnt;i++) a[++k]=e[i].fi,a[++k]=e[i].se;
Build_Virtual_Tree();
}
int f[N][2],g[N][2];
bool stater[N]; //子樹里是否有虛樹上的點(diǎn)
void dfs2(int u){ //預(yù)處理 g 數(shù)組
stater[u]=flag[u];
f[u][0]=f[u][1]=g[u][0]=g[u][1]=1;
for(int i=head[u];i;i=Next[i]){
int v=to[i];
if(v==fa[u][0] || fa[v][0]!=u) continue;
dfs2(v);
stater[u]|=stater[v];
( f[u][0] *= (f[v][0] + f[v][1]) % mod) %= mod;
( f[u][1] *= f[v][0] ) %= mod;
if(!stater[v]){
( g[u][0] *= (f[v][0] + f[v][1]) % mod) %= mod;
( g[u][1] *= f[v][0] ) %= mod;
}
}
}
int K[N][2][2],tmp[2][2]; //系數(shù)，因?yàn)樯厦嫘?k 用過了，所以大寫
void solve(int u,int v){ //預(yù)處理 K[v][0/1][0/1]
K[v][0][0]=K[v][1][1]=1;
int x=fa[v][0];
while(x!=u){
tmp[0][0]=K[v][0][0],tmp[0][1]=K[v][0][1],tmp[1][0]=K[v][1][0],tmp[1][1]=K[v][1][1];
K[v][0][0] = ( tmp[0][0] + tmp[0][1] ) % mod * g[x][0] % mod;
K[v][1][0] = ( tmp[1][0] + tmp[1][1] ) % mod * g[x][0] % mod;
K[v][0][1] = tmp[0][0] * g[x][1] % mod;
K[v][1][1] = tmp[1][0] * g[x][1] % mod;
x=fa[x][0];
}
}
void Get_DP(){
dfs2(1);
for(int u=1;u<=n;u++)
for(int v:G[u]) solve(u,v);
}
void DP(int u){
(f[u][0]*=g[u][0])%=mod,(f[u][1]*=g[u][1])%=mod;
for(int v:G[u]){
DP(v);
( f[u][0] *= ( (K[v][0][0] * f[v][0] % mod + K[v][1][0] * f[v][1] % mod) % mod + ( K[v][0][1] * f[v][0] % mod + K[v][1][1] * f[v][1] % mod) % mod ) % mod ) %= mod;
( f[u][1] *= (K[v][0][0] * f[v][0] % mod + K[v][1][0] * f[v][1] % mod) % mod ) %= mod;
}
}
void work(){
int ans=0;
for(int S=0;S<(1<<cnt);S++){
for(int i=1;i<=c;i++) f[t[i]][0]=f[t[i]][1]=1;
for(int i=1;i<=cnt;i++)
if(S>>(i-1)&1) f[e[i].fi][0]=0,f[e[i].se][1]=0;
else f[e[i].fi][1]=0;
DP(1);
( ans += (f[1][0] + f[1][1]) % mod ) %= mod;
}
printf("%lld\n",ans);
}
signed main(){
Init();
Get_DP();
work();
return 0;
}
96.[HNOI2004] L 語言
先看樸素的 DP，設(shè) \(f_i\) 表示前綴 \(i\) 可不可以被理解，轉(zhuǎn)移是：\(f_j \to f_i\)，需要滿足 \(s[j+1,i]\) 是一個單詞。
考慮對字典里的模式串建出 AC 自動機(jī)。
如果 \(t\) 的前綴 \(i\) 在 fail 樹上代表點(diǎn) \(u\)，并且他的一個祖先 \(v\) 是一個模式串的終止節(jié)點(diǎn)。
設(shè) \(v\) 代表的模式串長度為 \(len\)，則 \(i\) 的長度為 \(len\) 的后綴就是一個模式串。
也就意味著 \(f_{i-len}\) 可以轉(zhuǎn)移到 \(f_i\)。
如果在 fail 樹上暴力地跳，并挨個判斷每個祖先，那么是 \(O(m|s||t|)\) 的。
注意到 \(|s|\le 20\)，也就是說所有以 \(u\) 結(jié)尾的模式串的長度是可以狀壓的，我們記在 \(g\) 數(shù)組里面，即 \(g_u\) 的第 \(k\) 位是 \(1\) 代表 \(u\) 結(jié)尾有一個長度為 \(k\) 的模式串。
又因?yàn)槟苻D(zhuǎn)移到 \(f_i\) 的 \(f_j\) 必定滿足 \(j\ge i-|s|\)，所以我們也可以對 \(f\) 數(shù)組狀壓，記在 \(h\) 數(shù)組里，即如果 \(h_i\) 的第 \(k\) 位是 \(1\) 那么代表 \(f_{i-k}=true\)。
所以 \(f_i = [(g_u | h_i) \ne 0]\)，\(u\) 是前綴 \(i\) 在 fail 樹上代表的點(diǎn)。
其中 \(g\) 可以預(yù)處理，\(h\) 數(shù)組在轉(zhuǎn)移的時候維護(hù)就可以了。
復(fù)雜度是：\(O(\sum |s| + \sum |t|)\)。
code
#include<bits/stdc++.h>
using namespace std;
const int N=500+5,M=2e6+5;
inline int read(){
int w = 1, s = 0;
char c = getchar();
for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
return s * w;
}
string s;
int n,T,tot,t[N][30],len[N],flag[N];
void insert(string s){
int p=0,dep=0;
for(int i=0;i<s.size();i++){
int ch=s[i]-'a';
if(!t[p][ch]) t[p][ch]=++tot;
p=t[p][ch],++dep;
}
flag[p]=1;
len[p]=dep;
}
int fail[N];
vector<int> G[N];
void getfail(){
queue<int> q;
for(int i=0;i<26;i++){
if(t[0][i]) q.push(t[0][i]);
}
while(q.size()){
int u=q.front(); q.pop();
for(int i=0;i<26;i++){
if(t[u][i])
fail[t[u][i]]=t[fail[u]][i],q.push(t[u][i]);
else
t[u][i]=t[fail[u]][i];
}
}
for(int i=1;i<=tot;i++) G[fail[i]].push_back(i);
}
int g[M];
bool f[M];
void dfs(int u){
for(int v:G[u]){
g[v]=g[u] | (flag[v] * (1<<len[v]));
dfs(v);
}
}
void Init(){
memset(f,false,sizeof f);
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>T;
for(int i=1;i<=n;i++){
cin>>s;
insert(s);
}
getfail();
dfs(0);
while(T--){
Init();
cin>>s; s=' '+s;
int p=0,h=1,ans=0;
for(int i=1;i<s.size();i++){
p=t[p][s[i]-'a'];
h<<=1;
if((h&g[p])!=0) f[i]=true,ans=max(ans,i);
h|=f[i];
}
printf("%d\n",ans);
}
return 0;
}
97.[ARC104C] Fair Elevator
形式化題意：
一個長度為 \(2n\) 的數(shù)軸，有 \(n\) 個區(qū)間，每個點(diǎn)只會作為一個區(qū)間的端點(diǎn)。
當(dāng)兩個區(qū)間相交時，那么他們的長度也必須相等，現(xiàn)在給了你若干個區(qū)間和某些區(qū)間的其中幾個端點(diǎn)。
求是否有合法的分配方案。
首先如果有一個區(qū)間是 \([l,r]\)，那么必然有這些區(qū)間：\([l+1,r+1] , [l+2,r+2] , ... , [r-1,2r-l-1]\)。
即最后的數(shù)軸可以被分成若干個獨(dú)立的小段，每個小段的分配方案都跟上面一樣。
那么因?yàn)榛ハ嗒?dú)立所以就可以比較簡單的 DP 了。
設(shè) \(f_i\) 表示前 \(i\) 段是否可行。
轉(zhuǎn)移為：\(f_j \to f_i\)，需要滿足 \([j+1,i]\) 可以被分配成形如：\([l+1,r+1] , [l+2,r+2] , ... , [r-1,2r-l-1]\)。
具體 check 方法見代碼，挺好理解的。
code
#include<bits/stdc++.h>
#define PII pair<int,int>
#define fi first
#define se second
using namespace std;
const int N=1e5+5;
inline int read(){
int w = 1, s = 0;
char c = getchar();
for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
return s * w;
}
int n,a[N],b[N],cnt[N],f[N];
PII op[N];
bool check(int l,int r){
int mid=(l+r)/2,len=(r-l+1)/2;
for(int i=l;i<=mid;i++){
if(op[i].fi && op[i+len].fi && op[i].fi!=op[i+len].fi) return false; //如果這兩個端點(diǎn)已經(jīng)被占了，但是不是同一個區(qū)間的就不行
if( (op[i].fi && op[i].se==1) || (op[i+len].fi && op[i+len].se==0) ) return false; //有一個被占了，但是這個點(diǎn)應(yīng)該是左端點(diǎn)現(xiàn)在確實(shí)右端點(diǎn)(或反過來)
}
return true;
}
signed main(){
n=read();
for(int i=1;i<=n;i++){
a[i]=read(),b[i]=read();
if(~a[i]) cnt[a[i]]++,op[a[i]]={i,0};
if(~b[i]) cnt[b[i]]++,op[b[i]]={i,1};
}
for(int i=1;i<=2*n;i++)
if(cnt[i]>1){
puts("No");
return 0;
}
f[0]=true;
for(int i=2;i<=2*n;i+=2){ //注意到每一段區(qū)間的長度和一定是偶數(shù)
for(int j=i-2;j>=0;j-=2)
f[i]|=(f[j] && check(j+1,i));
}
puts(f[2*n]?"Yes":"No");
return 0;
}
98.[ARC104D] Multiset Mean
把每個數(shù) \(-x\)，那么就是求和為 \(0\) 的方案數(shù)，此時可選數(shù)的值域是 \([1-x,n-x]\)。
把它分成 \(3\) 段：\([1-x,-1],0,[1,n-x]\)。
\(0\) 可以隨便選，方案數(shù)是 \(k+1\)。
現(xiàn)在相當(dāng)于第一部分和第三部分的絕對值要相等。
預(yù)處理 \(f_{i,j}\) 表示用值域 \([1,i]\) 湊出 \(j\) 的方案數(shù)，那么：\(ans = (k+1) \times \sum_{j\le V} f_{x-1,j}\times f_{n-x,j}\)。
其中 \(V\) 最大是 \(\frac{n(n+1)k}{2}\)。
這里多重背包計(jì)算的是方案數(shù)，所以就不用單調(diào)隊(duì)列優(yōu)化了，直接前綴和優(yōu)化即可。
復(fù)雜度是 \(O(n^3k)\)。
code
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e2+5,M=500005;
inline int read(){
int w = 1, s = 0;
char c = getchar();
for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
return s * w;
}
int n,K,mod,c[N],f[N][M],pre[M],m;
signed main(){
n=read(),K=read(),mod=read();
m=n*(n-1)/2*K;
f[0][0]=1;
for(int i=1;i<=n;i++){
for(int j=0;j<i;j++){
for(int k=0;j+k*i<=m;k++) pre[k]=0;
for(int k=0;j+k*i<=m;k++){
pre[k]=f[i-1][j+k*i];
if(k>0) (pre[k]+=pre[k-1])%=mod;
f[i][j+k*i]=(k-K-1<0)?(pre[k]):((pre[k] - pre[k-K-1] + mod)%mod);
}
}
}
for(int x=1;x<=n;x++){
int ans=0;
for(int j=0;j<=m;j++){
(ans += f[x-1][j]*f[n-x][j]%mod) %= mod;
}
printf("%lld\n",(ans*(K+1)%mod -1 + mod)%mod);
}
return 0;
}
99.[ARC104E] Random LIS
這年頭 \(n\le 6\) 的數(shù)據(jù)真不多見。
首先根據(jù)期望的定義答案就是所有可能的 LIS 的和去除總方案數(shù) \(\prod_{i=1}^1 a_i\)。
因?yàn)?\(n\) 實(shí)在是太小了，所以我們可以大膽地 \(O(n^n)\) 去枚舉每個數(shù)的排名，因?yàn)榭梢韵嗟人圆皇?\(O(n!)\)。說實(shí)話賽時我都沒去想這種復(fù)雜度
然后先求出此時的 LIS，現(xiàn)在就是要統(tǒng)計(jì)有多少滿足當(dāng)前排名數(shù)組的方案了。
對于排名相同的數(shù)，我們可以縮成一個數(shù)，其中這個數(shù)的值域是它們值域的交。
現(xiàn)在我們得到了 \(m\) 個數(shù),以及他們排名 \(rk\) 數(shù)組。
把他們按照 \(rk\) 排序后，就得到了一個長度為 \(m\) 的上升序列，其中每個數(shù)有一個值域 \(b_i\)。
現(xiàn)在問題變成：有多少個長度為 \(m\) 的嚴(yán)格單調(diào)上升的序列 \(c\)，并且 \(c_i \in [1,b_i]\)。
雖然 \(b_i\) 很大，但是它們在數(shù)軸上分出來的值域段卻很少，比如 \(b\) 如果是: \(6,4,2,8\)，那么就把值域分成了 \([1,2],[3,4],[5,6],[7,8]\) 四段。
考慮 DP，設(shè) \(f_{i,j}\) 表示前 \(i\) 個數(shù)，其中第 \(i\) 個數(shù)的值在第 \(j\) 段的方案數(shù)，轉(zhuǎn)移時枚舉 \(k\) 和 \(x\), 表示 \(c[k+1,i]\) 這些數(shù)全都放在第 \(j\) 段，\(c_k\) 放在第 \(x\) 段：
\(f_{i,j}=\sum f_{k,x} \times C_{len_j}^{i-k}\)。
轉(zhuǎn)移系數(shù) \(C_{len_j}^{i-k}\) 即從第 \(j\) 段選出 \(i-k\) 個位置。
注意還要判斷 \([k+1,i]\) 這些數(shù)是否都可以取到第 \(j\) 段，通過值域段的形成過程容易證明這些數(shù)的值域要么與第 \(j\) 段包含，要么相離，絕不可能相交的，所以只用看是否包含即可。
所有過程全都暴力即可，\(O(n^5)\) 的 DP。
時間復(fù)雜度 \(O(n^{n+5})\) 實(shí)際根本跑不滿。
code
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=10+5,mod=1e9+7;
inline int read(){
int w = 1, s = 0;
char c = getchar();
for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
return s * w;
}
int n,a[N],sum,INV=1;
int quick_power(int a,int b){
int ans=1;
while(b){
if(b&1) (ans*=a)%=mod;
b>>=1,(a*=a)%=mod;
}
return ans;
}
int rk[N],dp[N],t[N],b[100],len[N],f[N][N];
int C(int n,int m){ //這個要暴力算
if(m>n) return 0;
int ans=1;
for(int i=n-m+1;i<=n;i++) (ans*=i)%=mod;
for(int i=1;i<=m;i++) (ans*=quick_power(i,mod-2))%=mod;
return ans;
}
bool check(int l,int r,int id){
for(int i=l;i<=r;i++) if(t[i]<b[id]) return false;
return true;
}
int solve(int m){
for(int i=1;i<=m;i++) b[i]=LLONG_MAX;
for(int i=1;i<=n;i++) b[rk[i]]=min(b[rk[i]],a[i]);
for(int i=1;i<=m;i++) t[i]=b[i];
sort(b+1,b+m+1);
int cnt=unique(b+1,b+m+1)-b-1;
for(int i=1;i<=cnt;i++) len[i]=b[i]-b[i-1];
memset(f,0,sizeof f);
f[0][0]=1;
for(int i=1;i<=m;i++){
for(int j=1;j<=cnt;j++){
for(int k=0;k<i;k++){
if(!check(k+1,i,j)) continue;
for(int x=0;x<j;x++){
(f[i][j] += f[k][x] * C(len[j],i-k) % mod) %= mod;
}
}
}
}
int res=0;
for(int j=0;j<=cnt;j++) (res+=f[m][j])%=mod;
return res;
}
void dfs(int u){
if(u==n+1){
int maxrk=0;
bool flag[8];
memset(flag,0,sizeof flag);
for(int i=1;i<=n;i++) flag[rk[i]]=true,maxrk=max(maxrk,rk[i]);
for(int i=1;i<=n;i++) if(!flag[i] && flag[i+1]) return; //排名數(shù)組不合法
int LIS=0;
for(int i=1;i<=n;i++){
dp[i]=1;
for(int j=1;j<=i-1;j++){
if(rk[j]<rk[i]) dp[i]=max(dp[i],dp[j]+1);
}
LIS=max(LIS,dp[i]);
}
(sum+=LIS*solve(maxrk)%mod)%=mod;
return;
}
for(int i=1;i<=n;i++){
rk[u]=i;
dfs(u+1);
}
}
signed main(){
n=read();
for(int i=1;i<=n;i++) a[i]=read(),(INV*=quick_power(a[i],mod-2))%=mod;
dfs(1);
printf("%lld\n",sum*INV%mod);
return 0;
}
100.無題
第 100 個題就簡單點(diǎn)吧。
題面
給你一棵 \(n\) 個點(diǎn)的樹和一個數(shù) \(x\)，點(diǎn)有點(diǎn)權(quán) \(a_i\)，問有多少種把樹分成若干連通塊的方法，使得每一個連通塊內(nèi)的點(diǎn)的異或和都是 \(x\)。
答案對 \(998244353\) 取模。
數(shù)據(jù)范圍： \(n\le 10^6，1\le x,a_i \le 10^9\)。
題解
一個子樹如果能恰好分成若干合法的連通塊，那么子樹的異或和一定等于 \(0 / x\)。
而一個子樹假設(shè)劃分完之后還剩一些東西，那這些東西一定在上面，且他們的異或和只能是 \(sum / sum\oplus x\)。
其中 \(sum\) 是子樹的異或和。
那么設(shè) \(f_{u,0/1}\) 表示剩余的點(diǎn)的異或和是 \(sum / sum \oplus x\) 的方案數(shù)。
轉(zhuǎn)移時就是個普通的樹形背包。
\(O(n)\)。
code
#include<bits/stdc++.h>
#define int long long
#define PII pair<int,int>
#define fi first
#define se second
using namespace std;
const int N=1e6+5,mod=998244353;
inline int read() {
int w = 1, s = 0;
char c = getchar();
for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
return s * w;
}
int n,x,a[N];
int tot,head[N],to[N<<1],Next[N<<1];
void add(int u,int v) {
to[++tot]=v,Next[tot]=head[u],head[u]=tot;
}
int f[N][2];
int dfs(int u,int fa){
int sum=a[u];
f[u][0]=1,f[u][1]=0;
for(int i=head[u];i;i=Next[i]){
int v=to[i];
if(v==fa) continue;
sum^=dfs(v,u);
int tmp[2];
tmp[0]=(f[u][0]*f[v][0]%mod + f[u][1]*f[v][1]%mod)%mod;
tmp[1]=(f[u][1]*f[v][0]%mod + f[u][0]*f[v][1]%mod)%mod;
f[u][0]=tmp[0],f[u][1]=tmp[1];
}
int tmp[2];
tmp[0]=f[u][0],tmp[1]=f[u][1];
if(sum==x) (f[u][1]+=tmp[0])%=mod; //可以沒有剩余,即不往上上傳
if(sum==0) (f[u][0]+=tmp[1])%=mod;
return sum;
}
int quick_power(int a,int b){
int ans=1;
while(b){
if(b&1) (ans*=a)%=mod;
b>>=1,(a*=a)%=mod;
}
return ans;
}
signed main() {
freopen("town.in","r",stdin);
freopen("town.out","w",stdout);
n=read(),x=read();
for(int i=1; i<=n; i++) a[i]=read();
for(int i=1; i<n; i++) {
int u=read(),v=read();
add(u,v),add(v,u);
}
int sum=dfs(1,0),ans;
if(sum==x) ans=f[1][0];
else if(sum==0) ans=f[1][1];
else ans=0;
printf("%lld\n",ans);
return 0;
}
從這題開始組合數(shù)就不用 \(C_n^m\) 改用 \(\binom{n}{m}\) 了。
101. Counting swaps
容易知道把他變成有序的最小操作數(shù)是 \(\sum_{i=1}^{cnt} siz_i-1=n-cnt\)，\(siz_i\) 表示第 \(i\) 個置換環(huán)的長度，\(cnt\) 是置換環(huán)個數(shù)。
設(shè) \(f_n\) 表示把長度為 \(n\) 的環(huán)分解成 \(n\) 個自環(huán)的方案數(shù)。
那么枚舉第一次操作后他分成的兩個小環(huán)的大小 \(x,y\)。
如果 \(x=y\) 那么有 \(\frac{n}{2}\) 種操作方法把他分成 \(x,y\) 兩個環(huán) ； 否則這一步的方案數(shù)為 \(n\)，我們記作 \(T(x,y)\)。
然后可以得到 \(f_n=\sum_{x+y=n} T(x,y) \times f_x \times f_y \times \binom{n-2}{x-1}\)。
則答案 \(ans=\frac{(n-cnt)!}{\prod (siz_i-1)!} \times \prod f_{siz_i}\)。
注意到此時的瓶頸在求 \(f\) 是 \(O(n^2)\) 的。
打表可以發(fā)現(xiàn) \(f_n=n^{n-2}\)，所以可以優(yōu)化成 \(O(n \log n)\)。
當(dāng)然我們需要證明。
會發(fā)現(xiàn) \(n^{n-2}\) 是經(jīng)典的有標(biāo)號無根樹的個數(shù)，于是考慮在操作序列和有標(biāo)號無根樹之間建立雙射。
如果交換了 \(x,y\) 就在 \(x,y\) 之間連一條邊，那么 \(n-1\) 次操作后就可以得到一棵 \(n\) 個點(diǎn)的樹。
但注意到你正著推并沒有雙射關(guān)系，因?yàn)閷τ谝粋€置換環(huán)，相同的操作集合，只要操作順序不同，這兩種操作方案就是不同的，但是他們得到的無根樹是一樣的。
那么我們就倒著考慮，假設(shè)我們得到了最后那棵無根樹，并且欽定了每條邊之間的順序（一共有 \(n^{n-2}\times (n-1)!\) 種情況），那么我們倒著執(zhí)行所有操作，每次操作變成合并兩個環(huán)，我們會得到一個唯一確定的環(huán)。而這個操作序列同樣是那個環(huán)的一個合法操作方案。
所以所有長度為 \(n\) 的置換環(huán)的方案個數(shù)是 \(n^{n-2}\times (n-1)!\)，顯然每個置換環(huán)的方案數(shù)都是一樣的，而長度為 \(n\) 的置換環(huán)一共有 \((n-1)!\) 個（就是一個圓排列數(shù)）。
所以每個長度為 \(n\) 的置換環(huán)的方案數(shù)都是 \(\frac{n^{n-2}\times (n-1)!}{(n-1)!}=n^{n-2}\)。
該證明參考自：這篇題解。
這題雖然最終做法不是 DP，但是前半部分是個計(jì)數(shù) DP 題的經(jīng)典思路，并且結(jié)論也應(yīng)該牢記。
code
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5,mod=1e9+9;
inline int read(){
int w = 1, s = 0;
char c = getchar();
for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
return s * w;
}
int n,a[N],dis[N],fact[N],q[N],inv[N],f[N],ans;
int Dis(int x){
return lower_bound(dis+1,dis+n+1,x)-dis;
}
int quick_power(int a,int b){
int ans=1;
while(b){
if(b&1) (ans*=a)%=mod;
b>>=1,(a*=a)%=mod;
}
return ans;
}
//int Swap(int x,int y){
// return (x==y)?((x+y)/2):(x+y);
//}
int fa[N],Size[N];
int get(int x){
return x==fa[x]?x:(fa[x]=get(fa[x]));
}
void merge(int x,int y){
x=get(x),y=get(y);
if(x==y) return;
Size[y]+=Size[x];
fa[x]=y;
}
signed main(){
// freopen("perm.in","r",stdin);
// freopen("perm.out","w",stdout);
int T=read();
fact[0]=1;
for(int i=1;i<N;i++) fact[i]=fact[i-1]*i%mod;
inv[1]=1;
for(int i=2;i<N;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod;
q[0]=1;
for(int i=1;i<N;i++) q[i]=q[i-1]*inv[i]%mod;
while(T--){
n=read();
for(int i=1;i<=n;i++) fa[i]=i,Size[i]=1;
for(int i=1;i<=n;i++) dis[i]=a[i]=read();
sort(dis+1,dis+n+1);
for(int i=1;i<=n;i++) merge(i,Dis(a[i]));
f[1]=1;
for(int i=2;i<=n;i++){
// for(int x=1;x<=i/2;x++){
// int y=i-x;
// (f[i]+=Swap(x,y) * f[x] % mod * f[y] % mod * fact[i-2] % mod * q[x-1] % mod * q[y-1] % mod)%=mod;
// }
// cout<<i<<':'<<f[i]<<'\n';
f[i]=quick_power(i,i-2);
}
ans=1;
int sum=0;
for(int i=1;i<=n;i++){
if(get(i) == i){
sum+=Size[i]-1;
(ans *= f[Size[i]]) %= mod;
(ans *= q[Size[i]-1]) %= mod;
}
}
(ans *= fact[sum]) %= mod;
printf("%lld\n",ans);
}
return 0;
}
102.Jellyfish and EVA
翻譯可能有點(diǎn)不清楚：
就是一個點(diǎn) \(u\) 在選擇了 \(v\) 但是 \((u,v)(u,w)\) 不同時，在銷毀這兩條邊之后會繼續(xù)選下一個 \(v'\)，直到 \(v'=w'\)。
首先對于一個點(diǎn)的所有出邊我們肯定是欽定一個順序去選，那我們首先我們需要預(yù)處理一個 \(f_{i,j}\) 表示假如我們有 \(i\) 條出邊，成功選到第 \(j\) 條的概率是多少。
初值：\(f_{i,1}=\frac{1}{i}\)。
對于其他 \(f_{i,j}\) 考慮當(dāng)我選第一條邊時隨機(jī)到了哪一條邊。
首先它一定不能隨機(jī)到第一條邊（不然在第一條邊我就直接走掉了），假設(shè)隨機(jī)到了邊 \(x\)：
- \(1<x<j\)：那么現(xiàn)在第 \(j\) 條邊變成了第 \(j-2\) 條邊，\(f_{i-2,j-2} \times \frac{j-2}{i} \to f_{i,j}\)。
- \(j<x\le i\)：那么現(xiàn)在第 \(j\) 條邊變成了第 \(j-1\) 條邊，\(f_{i-2,j-1} \times \frac{i-j}{i} \to f_{i,j}\)。
設(shè) \(g_u\) 表示從點(diǎn) \(u\) 走到 \(n\) 的概率，那么因?yàn)轭}目中說每一條邊都滿足 \(u<v\)，所以我們倒著轉(zhuǎn)移。
現(xiàn)在相當(dāng)于是把 \(u\) 的所有出點(diǎn) \(v\) 的 \(g_v\) 和 \(f_{deg_u,j}\) 去配對，問乘積之和最大是多少。
根據(jù)經(jīng)典結(jié)論，把他們分別升序排序然后依次匹配就是最優(yōu)的。
（事實(shí)上 \(j\) 越大 \(f_{i,j}\) 越小，但你排序了復(fù)雜度也不會錯）。
\(O(n^2 + m \log m)\)。
code
#include<bits/stdc++.h>
using namespace std;
const int N=5e3+5,M=2e5+5;
inline int read(){
int w = 1, s = 0;
char c = getchar();
for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
return s * w;
}
int n,m,deg[N];
vector<int> G[N];
double f[N][N],g[N];
void add(int u,int v){
deg[u]++;
G[u].push_back(v);
}
void Init(){
for(int i=1;i<=n;i++) G[i].clear(),deg[i]=0;
}
signed main(){
int T=read();
while(T--){
n=read(),m=read();
Init();
for(int i=1;i<=m;i++){
int u=read(),v=read();
add(u,v);
}
for(int i=0;i<=n;i++) f[i][0]=0,g[i]=0;
for(int i=1;i<=n;i++){
f[i][1]=1.0/i;
for(int j=2;j<=i;j++) f[i][j]=1.0*f[i-2][j-2]*(j-2)/i + 1.0*f[i-2][j-1]*(i-j)/i;
}
g[n]=1.0;
for(int i=n;i>=1;i--){
sort(G[i].begin(),G[i].end(),[&](int x,int y){return g[x]>g[y];});
for(int j=1;j<=deg[i];j++) g[i]+=g[G[i][j-1]]*f[deg[i]][j];
}
printf("%.12lf\n",g[1]);
}
return 0;
}
103.Jellyfish and Miku
用的是第一篇題解的思路。
設(shè) \(f_i\) 表示 \(i\) 走到 \(n\) 的期望步數(shù)。
那么根據(jù)題意，可以得到：
化簡第二個式子得到：
\(a_{i+1} \times (f_i - f_{i+1}) = a_{i} \times (f_{i-1} - f_i) + a_i + a_{i+1}\)。
設(shè) \(g_i=f_{i-1}-f_i\)，那么就等價(jià)于：
\(a_{i+1} \times g_{i+1} = a_i \times g_i + a_i + a_{i+1}\)。
于是得到 \(g\) 的遞推式：
手推可以得到通項(xiàng)公式：
答案是 \(f_0\)，用 \(g\) 表示他：
于是問題變成最小化 \(\sum_{i=1}^n \frac{1}{a_i} \sum_{j=1}^{i-1} a_j\)。
這個問題可以 DP，設(shè) \(dp_{i,s}\) 表示 \(\sum_{j=1}^i a_j =s\) 時，前 \(i\) 個數(shù)的上面那個式子的值。
轉(zhuǎn)移：\(dp_{i,s} + \frac{s}{j} \to dp_{i+1,s+j}\)。
復(fù)雜度是 \(O(m^2n)\)，過不了。
此時我們需要一個結(jié)論：\(a_i\) 一定是單調(diào)不降的。
證明：鄰項(xiàng)交換可證。
所以 \(s+k(n-i) \le m\)，于是復(fù)雜度變成調(diào)和級數(shù)，\(O(m^2 \log n)\)。
code
#include<bits/stdc++.h>
using namespace std;
const int N=3e3+5;
inline int read(){
int w = 1, s = 0;
char c = getchar();
for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
return s * w;
}
int n,m;
double f[N][N];
signed main(){
n=read(),m=read();
for(int i=0;i<=n;i++)
for(int s=0;s<=m;s++)
f[i][s]=1e9;
f[0][0]=0;
for(int i=0;i<n;i++){
for(int s=0;s<=m;s++){
for(int k=1;k*(n-i)+s<=m;k++){
f[i+1][s+k]=min(f[i+1][s+k],f[i][s]+1.0*s/k);
}
}
}
double ans=1e9;
for(int s=0;s<=m;s++) ans=min(ans,f[n][s]);
printf("%.12lf",2.0*ans+1.0*n);
return 0;
}
104.Good Contest
這個題就是 "99.[ARC104E] Random LIS" 在爆搜完之后數(shù)方案數(shù)的子問題。
只不過值域從 \([1,r]\) 變成了 \([l,r]\)，然后從嚴(yán)格單增變成不嚴(yán)格單降。
前面是一樣的，設(shè) \(f_{i,j}\) 表示考慮前 \(i\) 個數(shù)，其中第 \(i\) 個數(shù)在第 \(j\) 段（這里把段從大到小排序）的方案數(shù)。
考慮從 \(f_{k,x}\) 轉(zhuǎn)移過來，即 \(a[k+1,i]\) 都在第 \(j\) 段，同樣的需要判斷他們的值域是否和第 \(j\) 段有交。
現(xiàn)在相當(dāng)于是要求在第 \(j\) 段放這 \(i-k\) 個數(shù)的方案數(shù)，注意到它們的大小關(guān)系已經(jīng)定了，我們選位置就可以了。
但是因?yàn)轭}目描述是單調(diào)不增而不是單調(diào)下降，所以一個位置可以放多個數(shù)，算這個也很簡單：
假設(shè)這段有 \(len\) 個位置，我們要放進(jìn) \(m=i-k\) 個位置。
那么相當(dāng)于是要解一個形如：\(x_1+x_2+...+x_{len}=m\) 的方程。
求他的非負(fù)整數(shù)解的個數(shù)，根據(jù)插板法答案是 \(\binom{len+m-1}{len-1}=\binom{len+m-1}{m}\)。
因?yàn)檫@個組合數(shù)很大不能預(yù)處理，所以求組合數(shù)有個 \(O(n)\)，然后枚舉 \(x\) 用前綴和優(yōu)化掉即可。
時間復(fù)雜度 \(O(n^4)\)。
code
#include<bits/stdc++.h>
#define int long long
#define PII pair<int,int>
#define fi first
#define se second
using namespace std;
const int N=50+5,mod=998244353;
inline int read(){
int w = 1, s = 0;
char c = getchar();
for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
return s * w;
}
int n,l[N],r[N],f[N][N<<2],pre[N][N<<2],inv[N],sum;
struct P{
int pos,op;
}a[N<<1];
int cnt;
PII range[N<<1]; //左閉右開
bool check(int L,int R,int id){
for(int i=L;i<=R;i++){
if(max(l[i],range[id].fi)>min(r[i],range[id].se-1)) return false;
}
return true;
}
int C(int n,int m){ //m 比較小
if(m>n) return 0;
int res=1;
for(int i=n-m+1;i<=n;i++) res=res*i%mod;
for(int i=1;i<=m;i++) res=res*inv[i]%mod;
return res;
}
int quick_power(int a,int b){
int ans=1;
while(b){
if(b&1) (ans*=a)%=mod;
b>>=1,(a*=a)%=mod;
}
return ans;
}
signed main(){
n=read();
inv[1]=1;
for(int i=2;i<N;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod;
sum=1;
for(int i=1;i<=n;i++){
l[i]=read(),r[i]=read(),(sum*=(r[i]-l[i]+1))%=mod;
a[i]={l[i],1},a[i+n]={r[i]+1,-1};
}
sort(a+1,a+2*n+1,[&](P x,P y){return x.pos<y.pos;});
for(int i=1,tmp=0;i<=2*n;i++){ //我想不到更好的搞出區(qū)間的方法了
if(tmp>0) range[++cnt]={a[i-1].pos,a[i].pos};
tmp+=a[i].op;
}
reverse(range+1,range+cnt+1);
f[0][0]=1;
for(int i=0;i<=cnt;i++) pre[0][i]=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=cnt;j++){
for(int k=0;k<i;k++){
if(!check(k+1,i,j)) continue;
int len=range[j].se-range[j].fi,num=i-k;
(f[i][j]+=pre[k][j-1]*C(len+num-1,num)%mod)%=mod;
}
}
for(int j=1;j<=cnt;j++) pre[i][j]=(pre[i][j-1]+f[i][j])%mod;
}
printf("%lld\n",pre[n][cnt]*quick_power(sum,mod-2)%mod);
return 0;
}
105. Tenzing and Random Operations
這個題有兩種做法，一種是組合意義，一種是代數(shù)法，這里講前者。
考慮 \(\prod a_i\) 的組合意義，相當(dāng)于是從 \(i\) 走到 \(i+1\) 有 \(a_i\) 種方案，求 \(1\) 走到 \(n+1\) 的方案數(shù)。
修改意味著什么，相當(dāng)于是在一個位置 \(i\) 放了一個工具，走到 \(i\) 之后就擁有了這個工具，在之后的每一步 \((u,u+1)\) 你都可以使用這個工具使你走到 \(u+1\) 多了 \(v\) 個方案。
注意：這個工具不是一次性的，可以用多次。
那么雖然 \(m\) 很大，但是所有用過的工具肯定只有 \(n\) 種，于是考慮 \(O(n^2)\) 的 DP。
設(shè) \(f_{i,j}\) 表示走到 \(i\) ，我用了 \(j\) 種工具（注意不是 \(j\) 次工具）的方案數(shù)，轉(zhuǎn)移有：
- 用 \(a_i\)：\(f_{i,j} \times a_i \to f_{i+1,j}\)。
- 用先前用過的工具：\(f_{i,j}\times j\times v \to f_{i+1,j}\)。
- 用一個我先前沒用過的工具，先看他是剩下 \(m-j\) 個中的哪一個，再看他放在了前 \(i\) 個位置的哪一個： \(f_{i,j}\times (m-j)\times i\times v \to f_{i+1,j+1}\)。
答案就是 \(\frac{\sum_{i=0}^n f_{n+1,i} \times n^{m-i}}{n^m} = \sum_{i=0}^n \frac{f_{n+1,i}}{n^i}\)。
code
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e3+5,mod=1e9+7;
inline int read(){
int w = 1, s = 0;
char c = getchar();
for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
return s * w;
}
int n,m,v,a[N],f[N][N];
int qp(int a,int b){
int ans=1;
while(b){
if(b&1) (ans*=a)%=mod;
(a*=a)%=mod,b>>=1;
}
return ans;
}
signed main(){
n=read(),m=read(),v=read();
for(int i=1;i<=n;i++) a[i]=read();
f[1][0]=1;
for(int i=1;i<=n;i++){
for(int j=0;j<=i;j++){
(f[i+1][j] += f[i][j] * a[i] % mod)%=mod;
(f[i+1][j] += f[i][j] * v % mod * j % mod)%=mod;
(f[i+1][j+1] += f[i][j] * (m-j) % mod * i % mod * v % mod)%=mod;
}
}
int ans=0;
for(int i=0;i<=n;i++) (ans+=f[n+1][i]*qp(qp(n,i),mod-2)%mod)%=mod;
printf("%lld\n",ans);
return 0;
}
106.Tenzing and Random Real Numbers
一個trick：右邊的 \(1\) 很難受，考慮令 \(y_i=x_i-0.5\)，那么限制變?yōu)椋?/p>
- \(y_i+y_j\le 0\)
- \(y_i+y_j\ge 0\)。
其中 \(y_i\) 在 \([-0.5,0.5]\) 等概率隨機(jī)。
首先這個 = 直接去掉對答案是沒有影響的，因?yàn)樵谝粋€無限大的集合里隨機(jī)一個數(shù)隨機(jī)到一個確定的數(shù)的概率是 \(0\)。
考慮 \(y_i+y_j\) 的符號跟什么有關(guān)，容易證明他的符號就是絕對值大的那個數(shù)的符號。
所以一個條件相當(dāng)于限制了絕對值大的那個數(shù)的符號。
而一個 \(y\) 取到正負(fù)的概率均為 \(1/2\)，所以直接合法方案數(shù)/總方案數(shù)即為概率。
現(xiàn)在我們只需要給 \(y\) 確定一個順序（按絕對值從大到小排），并確定每個數(shù)的符號。
考慮根據(jù)值域從大到小狀壓 DP，每次新加進(jìn)來的一數(shù)定放在末尾，枚舉它的符號是什么并判斷是否滿足所有條件即可。
總方案數(shù)就是 \(n! 2^n\)。
暴力 check 復(fù)雜度就是 \(O(2^n m)\)。
code
#include<bits/stdc++.h>
#define PII pair<int,int>
#define fi first
#define se second
//#define int long long
using namespace std;
const int N=1e5+5,mod=998244353;
inline int read(){
int w = 1, s = 0;
char c = getchar();
for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
return s * w;
}
int n,m,f[(1<<20)+5];
vector<PII> G[N];
int inv[N];
signed main(){
n=read(),m=read();
for(int i=1;i<=m;i++){
int op=read(),u=read(),v=read();
G[u].push_back({v,op}),G[v].push_back({u,op});
}
f[0]=1;
for(int s=0;s<(1<<n);s++){
for(int i=1;i<=n;i++){ //枚舉下一個放啥
if(s>>(i-1)&1) continue;
//我們只需要判斷以他作為絕對值最大的數(shù)的限制是否滿足即可
for(int opt=0;opt<=1;opt++){
bool flag=true;
for(PII limit:G[i]){
int j=limit.fi,op=limit.se;
if(s>>(j-1)&1) continue;
if(op!=opt){
flag=false;
break;
}
}
if(flag) (f[s|(1<<(i-1))]+=f[s])%=mod;
}
}
}
inv[1]=1;
for(int i=2;i<N;i++) inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
int ans=f[(1<<n)-1];
//總方案數(shù)為 n!*(2^n) 先確定順序再確定正負(fù)號
for(int i=1;i<=n;i++) ans=1ll*ans*inv[i]%mod;
for(int i=1;i<=n;i++) ans=1ll*ans*inv[2]%mod;
printf("%d\n",ans);
return 0;
}
107.Sports Betting
幾個題面注意點(diǎn)：\(i\) 打敗了 \(j\)，不一定代表 \(j\) 沒打敗 \(i\)。
根據(jù)期望線性性，我們只要算出每個人成為 Winner 的概率加起來即可。
起手狀壓 DP：\(f_{i,S}\) 表示 \(i\) 打敗集合 \(S\) 所有人的概率，特殊地 \(S\) 一定包含 \(i\)。
考慮容斥，用 \(1-\) 不合法的概率。
\(P（\text{不合法概率}）=\sum f_{i,T}\times g_{S/T,T}\)。（\(S/T\) 是補(bǔ)集的意思。）
其中 \(T\) 是 \(S\) 的一個包含 \(i\) 的子集，\(g_{S,T}\) 表示集合 \(S\) 的所有人都打敗了集合 \(T\) 的人，且集合 \(T\) 的人沒一個打敗 \(S\) 的人的概率。
\(O(n^2)\) 直接算 \(g\) 的話求解一個人的概率的復(fù)雜度是 \(O(3^nn^2)\)。
總復(fù)雜度是 \(O(3^nn^3)\) 過不去。
優(yōu)化求 \(g\) 的方法，先 \(O(n^22^n)\) 預(yù)處理出 \(h_{i,S}\) 表示 \(i\) 打敗 \(S\) 中所有人，且 \(S\) 中全都沒打敗 \(i\) 的概率。
這樣就可以 \(O(n)\) 求 \(g\) 了。
總時間復(fù)雜度 \(O(3^nn^2)\)。
因?yàn)?\(S,T\) 還有要包含 \(i\) 的限制，所以跑不滿，\(4s\) 隨便過的。
code
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e6+5,mod=1e9+7;
inline int read(){
int w = 1, s = 0;
char c = getchar();
for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
return s * w;
}
int n,a[N],inv[N],ans;
int h[16][(1<<14)+5],f[16][(1<<14)+5];
int solve(int x){
for(int s=0;s<(1<<n);s++){
if(!(s>>(x-1)&1)) continue;
for(int t=s;t;t=(t-1)&s){
if(!(t>>(x-1)&1)) continue;
int tmp=s^t,g=1;
for(int i=1;i<=n;i++){
if(tmp>>(i-1)&1) g=g*h[i][t]%mod;
}
f[x][s]=(f[x][s]+g*f[x][t]%mod)%mod;
}
f[x][s]=(1-f[x][s]+mod)%mod;
}
return f[x][(1<<n)-1];
}
signed main(){
n=read();
for(int i=1;i<=n;i++) a[i]=read();
inv[1]=1;
for(int i=2;i<N;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod;
for(int i=1;i<=n;i++){
for(int s=0;s<(1<<n);s++){
if(s>>(i-1)&1) continue; //不能包含 i
h[i][s]=1;
for(int j=1;j<=n;j++){
if(s>>(j-1)&1) h[i][s]=h[i][s] * a[i] % mod * inv[a[i]+a[j]] % mod;
}
}
}
for(int i=1;i<=n;i++) ans=(ans+solve(i))%mod;
printf("%lld\n",ans);
return 0;
}
108.找行李
題面
數(shù)據(jù)范圍: \(n,m\le 200，1\le a_i,b_i \le 500\)，\(a_i,b_i\) 互不相同。
題解
首先一個經(jīng)典技巧是：\(f_d\) 表示答案 \(\ge d\) 的方案數(shù)，那么差分一下可以得到 \(ans=\sum_{i=1}^{+\infty} f_i\)（實(shí)際上 \(d\) 只需要枚舉到值域最大值）。
對于一個 \(d\)，每個人能選擇的箱子是一段前綴，并且前面的人的可選箱子是后面的人的可選箱子的子集。
于是考慮 DP，\(f_{i,j}\) 表示前 \(i\) 個人，選了 \(j\) 個箱子的方案數(shù)（\(d\) 確定），那么假設(shè)第 \(i\) 個人可選的箱子有 \(k\) 個：\(f_{i,j} = f_{i-1,j} + f_{i-1,j-1}\times (k-(j-1))\)。
意義為，要么第 \(i\) 個人不匹配，要么匹配一個箱子，可匹配的箱子有 \(k-(j-1)\) 個（因?yàn)榍懊?\(i-1\) 個人匹配掉了 \(j-1\) 個）。
\(O(n^2V)\)。
code
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=500+5,mod=998244353;
inline int read(){
int w = 1, s = 0;
char c = getchar();
for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
return s * w;
}
int n,m,a[N],b[N],f[N][N],ans;
signed main(){
n=read(),m=read();
for(int i=1;i<=n;i++) a[i]=read();
for(int i=1;i<=m;i++) b[i]=read();
sort(a+1,a+n+1),sort(b+1,b+m+1);
for(int d=1;d<=500;d++){
memset(f,0,sizeof f);
f[0][0]=1;
for(int i=1,k=0;i<=m;i++){
for(int j=0;j<=min(i,n);j++){
while(k+1<=n && b[i]-a[k+1]>=d) k++;
f[i][j]=f[i-1][j];
if(k>=j-1 && j>=0) (f[i][j]+=f[i-1][j-1]*(k-(j-1))%mod)%=mod;
}
}
for(int j=1;j<=n;j++) (ans+=f[m][j])%=mod;
}
printf("%lld\n",ans);
return 0;
}
109.[POI2015] MYJ
一個店的價(jià)格肯定只會取某個 \(c_i\)，所以可以離散化。
因?yàn)轭櫩褪且欢螀^(qū)間，所以考慮區(qū)間 DP。
\(f_{l,r,k}\) 表示當(dāng)區(qū)間 \([l,r]\) 的最小值 \(\ge k\) 時，所有被 \([l,r]\) 包含的顧客的最大花費(fèi)。
轉(zhuǎn)移有：\(f_{l,r,k} = \max( f_{l,r,k+1} , \max_{x=l}^r (f_{l,x-1,k}+f_{x+1,r,k}+cnt(l,r,x,k)\times k) )\)。
\(cnt(l,r,x,k)\) 表示當(dāng)區(qū)間 \([l,r]\) 的最小值位置為 \(x\) 且值為 \(k\) 時，所有被 \([l,r]\) 包含的且在 \(x\) 處消費(fèi)的顧客數(shù)。
直接轉(zhuǎn)移是 \(O(n^3m^2)\)，狀態(tài)數(shù)是 \(O(n^2m)\)，枚舉 \(x\) \(O(n)\)，求 \(cnt\) \(O(m)\)。
只需要在枚舉完 \(l,r\) 后去 \(O(nm)\) 預(yù)處理 \(cnt(l,r,x,k)\) 就可以在轉(zhuǎn)移時去掉 \(O(m)\)。
具體的預(yù)處理方法就是先 \(O(m)\) 的去枚舉所有被 \([l,r]\) 包含的顧客 \(i\)，然后 \(O(n)\) 遍歷 \(x\in [a_i,b_i]\)，將 \(cnt(l,r,x,c_i)\) 加上 \(1\)。
最后對 \(cnt(l,r,x)\) 做一遍后綴和即可。
復(fù)雜度變成 \(O(n^3m)\)。
記錄方案是樸素的。
code
#include<bits/stdc++.h>
#define PII pair<int,int>
#define fi first
#define se second
using namespace std;
const int N=4000+5;
inline int read(){
int w = 1, s = 0;
char c = getchar();
for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
return s * w;
}
int n,m,a[N],b[N],c[N],f[55][55][N],dis[N],tot;
int cnt[55][N];
PII from[55][55][N]; //記錄最小值的位置以及最小值
int Dis(int x){
return lower_bound(dis+1,dis+tot+1,x)-dis;
}
int p[N];
void dfs(int l,int r,int k){
if(l>r) return;
int x=from[l][r][k].fi,ming=from[l][r][k].se;
if(ming==0) ming=k;
p[x]=dis[ming];
if(l==r) return;
dfs(l,x-1,ming),dfs(x+1,r,ming);
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
n=read(),m=read();
for(int i=1;i<=m;i++) a[i]=read(),b[i]=read(),dis[i]=c[i]=read();
sort(dis+1,dis+m+1);
tot=unique(dis+1,dis+m+1)-dis-1;
for(int i=1;i<=m;i++) c[i]=Dis(c[i]);
for(int len=1;len<=n;len++){
for(int l=1;l+len-1<=n;l++){
int r=l+len-1;
//預(yù)處理 cnt
for(int x=l;x<=r;x++) for(int k=1;k<=tot;k++) cnt[x][k]=0;
for(int i=1;i<=m;i++)
if(l<=a[i]&&b[i]<=r)
for(int x=a[i];x<=b[i];x++) cnt[x][c[i]]++;
for(int x=l;x<=r;x++) for(int k=tot-1;k>=1;k--) cnt[x][k]+=cnt[x][k+1];
for(int k=tot;k>=1;k--){
from[l][r][k]=from[l][r][k+1],f[l][r][k]=f[l][r][k+1];
for(int x=l;x<=r;x++){
if(f[l][x-1][k]+f[x+1][r][k]+cnt[x][k]*dis[k] >= f[l][r][k]){
f[l][r][k]=f[l][x-1][k]+f[x+1][r][k]+cnt[x][k]*dis[k];
from[l][r][k]={x,k};
}
}
}
}
}
printf("%d\n",f[1][n][1]);
dfs(1,n,1);
for(int i=1;i<=n;i++) printf("%d ",p[i]);
puts("");
return 0;
}
110.[清華集訓(xùn) 2016] 組合數(shù)問題
這個一眼 Lucas 定理，\(C(n,m) \equiv 0 \pmod k\) 當(dāng)且僅當(dāng) \(n，m\) 的 \(k\) 進(jìn)制表示下，\(n\) 有一位比 \(m\) 小。
因?yàn)?\(n，m\) 巨大，所以只能數(shù)位 DP:
\(f_{pos,0/1,0/1,0/1,0/1}\) 表示考慮了前 \(pos\) 位，目前 \(i\) 有沒有一位比 \(j\) 小，\(i\) 和 \(j\) 是否緊貼，\(i\) 和 \(n\) 是否緊貼，\(j\) 和 \(m\) 是否緊貼的方案數(shù)。
轉(zhuǎn)移比較顯然。
code
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5,mod=1e9+7;
inline int read(){
int w = 1, s = 0;
char c = getchar();
for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
return s * w;
}
int T,k,n,m,len1,len2,a[65],b[65],f[65][2][2][2][2];
int dfs(int pos,bool flag,bool lim1,bool lim2,bool lim3){
if(!pos) return flag;
if(~f[pos][flag][lim1][lim2][lim3]) return f[pos][flag][lim1][lim2][lim3];
int p1=lim2?a[pos]:(k-1),res=0;
for(int i=0;i<=p1;i++){
int p2=lim3?b[pos]:(k-1);
if(lim1) p2=min(p2,i);
for(int j=0;j<=p2;j++){
( res += dfs(pos-1 , flag|(i<j) , lim1&(j==i) , lim2&(i==a[pos]) , lim3&(j==b[pos])) ) %= mod;
}
}
return f[pos][flag][lim1][lim2][lim3]=res;
}
int solve(){
len1=len2=0;
memset(a,0,sizeof a);
memset(b,0,sizeof b);
while(n) a[++len1]=n%k,n/=k;
while(m) b[++len2]=m%k,m/=k;
memset(f,-1,sizeof f);
return dfs(max(len1,len2) , false , true , true , true);
}
int quick_power(int a,int b){
int ans=1;
while(b){
if(b&1) (ans*=a)%=mod;
(a*=a)%=mod,b>>=1;
}
return ans;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
T=read(),k=read();
while(T--){
n=read(),m=read();
if(k==1){
if(n>=m) printf("%lld\n",((m+1)*m%mod*quick_power(2,mod-2)%mod + (m+1)*(n-m+1)%mod)%mod);
else printf("%lld\n",(n+2)*(n+1)%mod*quick_power(2,mod-2)%mod);
}
else printf("%lld\n",solve());
}
return 0;
}
111.Rikka with Subsequences
題意:
給一個 01 矩陣 \(A\)，和一個數(shù)組 \(a\)，定義 \(a\) 的長度為 \(m\) 的子序列 \(p\) 是好的，當(dāng)且僅當(dāng)：\(A_{p_1,p_2}=A_{p_2,p_3}=...=A_{p_{m-1},p_m}=1\)。
特殊的，長度為 1 的子序列也是好的。
對于每一個本質(zhì)不同的好的子序列 \(p\)，若他在 \(a\) 中出現(xiàn)了 \(cnt\) 次，則答案加上 \(cnt^3\)。
求最終答案。
當(dāng)要求 \(cnt^3\) 時一個經(jīng)典的套路是：\(cnt^3 = (1+1+...+1)(1+1+...+1)(1+1+...+1)\)。
根據(jù)乘法分配律，這個等價(jià)于在每個括號里選一個 \(1\) 的方案數(shù)。
相當(dāng)于是把原序列 \(a\) 復(fù)制成三個一模一樣的序列 \(a\)，\(b\)，\(c\)，求從 \(a\)，\(b\)，\(c\) 中選出本質(zhì)相同好的子序列的方案數(shù)。
那么設(shè) \(f_{i,j,k}\) 表示匹配到 \(a_i,b_j,c_k\) 的方案數(shù) （要求 \(a_i=b_j=c_k\)），轉(zhuǎn)移就是：
\(f_{i,j,k}=1+\sum_{i'<i,j'<j,k'<k，A_{a_i,a_{i'}}=1，a_{i'}=b_{j'}=c_{k'}} f_{i',j',k'}\)。
直接做 \(O(n^6)\)，可以前綴和優(yōu)化+容斥變成 \(O(n^3)\)。
這個前綴和優(yōu)化比較高級，具體可以看代碼。
code
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e2+5,mod=1e9+7;
inline int read(){
int w = 1, s = 0;
char c = getchar();
for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
return s * w;
}
int T,n,A[N][N],a[N],f[N][N][N],pre[N][N][N];
/*
pre[i][j][k]:表示 Σf[i'][j'][k'] 且 i'<i，j'<j，k'<k 并且 A[ a[i'] ][ a[j] ] = 1。
千萬注意最后不是 A[ a[i'] ][ a[i] ] = 1
*/
signed main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>T;
while(T--){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
char c; cin>>c;
A[i][j]=c-'0';
}
}
memset(f,0,sizeof f);
memset(pre,0,sizeof pre);
int ans=0;
for(int i=1;i<=n;i++){
//1.上一層的 f 沒有用了，直接在原數(shù)組上對后兩維做一遍前綴和（不帶限制），注意容斥
for(int j=1;j<=n;j++)
for(int k=1;k<=n;k++)
(f[i-1][j][k]+=((f[i-1][j-1][k]+f[i-1][j][k-1])%mod-f[i-1][j-1][k-1]+mod)%mod)%=mod;
//2.計(jì)算當(dāng)前的 pre[i][j][k]:pre[i][j][k] 和 pre[i-1][j][k] 相比由于我們的定義,其實(shí)只多了 Σf[i-1][j'][k'] (如果 A[a[i-1]][a[j]]=1 的話)
for(int j=1;j<=n;j++)
for(int k=1;k<=n;k++)
if(A[a[i-1]][a[j]]) pre[i][j][k]=(pre[i-1][j][k]+f[i-1][j-1][k-1])%mod; //這個時候的 f 數(shù)組已經(jīng)做過前綴和了
else pre[i][j][k]=pre[i-1][j][k];
//3.計(jì)算當(dāng)前層的 f
for(int j=1;j<=n;j++)
for(int k=1;k<=n;k++){
if(a[i]==a[j]&&a[j]==a[k]) f[i][j][k]=(pre[i][j][k]+1)%mod; //雖然 pre 的定義是 A[ai'][aj]=1，但是這里 ai=aj 所以沒事
else f[i][j][k]=0;
(ans+=f[i][j][k])%=mod;
}
}
cout<<ans<<'\n';
}
return 0;
}
112.Bus Analysis
考慮給你了一個序列 \(t\) 怎么算答案，然后 dp of dp 即可。
首先把貢獻(xiàn)都除以二，最后再把答案 \(\times 2\) 沒有任何影響。
樸素的 dp 是設(shè) \(f_i\) 表示覆蓋前 \(i\) 個點(diǎn)的最小代價(jià)。
轉(zhuǎn)移時，如果區(qū)間 \([t_{j+1},t_i]\) 的長度 \(\le 20\) 則有轉(zhuǎn)移 \(f_j+1 \to f_i\)；如果長度 \(\le 75\) 則有轉(zhuǎn)移 \(f_j+3 \to f_i\)。
這么看的話，如果想要轉(zhuǎn)移 \(f_i\) 我們需要至多 \(i\) 前面 \(75\) 個 \(j\) 的 DP 值。
繼續(xù)壓縮，會發(fā)現(xiàn)這 \(75\) 個 \(j\) 中的任意兩個 \(x,y\) 都滿足 \(f_x\) 和 \(f_y\) 相差不超過 \(3\)。
所以其實(shí)有用的 DP 值只有三種。
于是我們內(nèi)層 dp 其實(shí)只需要維護(hù)四個值：
- \(w\)：表示 \(f_i\)。
- \(x\): 表示最大的 \(j\) 滿足 \(f_j=f_i-1\)。
- \(y\): 表示最大的 \(j\) 滿足 \(f_j=f_i-2\)。
- \(z\): 表示最大的 \(j\) 滿足 \(f_j=f_i-3\)。
注：理論上講我們還需要維護(hù) \(u\) 表示最大的 \(j\) 滿足 \(f_j=f_i\)，但顯然 \(u=i\)。
轉(zhuǎn)移是簡單的，先算出 \(f_{i+1}\)，然后用 \({i,x,y,z}\) 去得到新的 \((x',y',z')\)。
那么我們的外層 dp 就是 \(f_{i,w,x,y,z}\) 表示內(nèi)層 dp 的結(jié)果是 \((w,x,y,z)\) 的方案數(shù)，顯然會炸。
不過發(fā)現(xiàn)我們記錄 \(w\) 的唯一用處就是計(jì)算最后的答案。
但是我們只需要計(jì)算所有 \(w\) 的和即可，這啟發(fā)我們在 \(w\) 改變的時候直接把變化值加到最后的答案里就可以了。
這樣狀態(tài)就變成 \(f_{i,x,y,z}\) 了，\(O(n\times 75^3)\) 因?yàn)槌?shù)小可以通過。
code
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+5,mod=1e9+7;
inline int read(){
int w=1,s=0;
char c=getchar();
for(;c<'0'||c>'9';w*=(c=='-')?-1:1,c=getchar());
for(;c>='0'&&c<='9';s=s*10+c-'0',c=getchar());
return w*s;
}
int n,t[N],f[2][76][76][76],pos[10],ans,p[N];
void DP1(int i,int x,int y,int z,int res){
if(x) (x+=1)%=76;
if(y) (y+=1)%=76;
if(z) (z+=1)%=76;
(f[i&1^1][x][y][z]+=res)%=mod;
}
int solve(int now,int lst,int res){
int len=t[now]-t[lst+1]+1;
if(len<=20) return res+1;
else if(len<=75) return res+3;
else return n+5;
}
void DP2(int i,int x,int y,int z,int res){
int g=solve(i+1,i,4);
if(x) g=min(g,solve(i+1,i-x,3));
if(y) g=min(g,solve(i+1,i-y,2));
if(z) g=min(g,solve(i+1,i-z,1));
(ans+=1ll*res*p[n-i-1]%mod*(g-4)%mod)%=mod;
pos[1]=pos[2]=pos[3]=0;
if(z>=1&&z<=74) pos[g-1]=z+1;
if(y>=1&&y<=74) pos[g-2]=y+1;
if(x>=1&&x<=74) pos[g-3]=x+1;
pos[g-4]=1;
(f[i&1^1][pos[1]][pos[2]][pos[3]]+=res)%=mod;
}
signed main(){
n=read();
p[0]=1;
for(int i=1;i<=n;i++) t[i]=read(),p[i]=p[i-1]*2%mod;
f[0][0][0][0]=1;
for(int i=0;i<n;i++){
memset(f[i&1^1],0,sizeof f[i&1^1]);
for(int x=0;x<=min(i,75);x++){
for(int y=0;y<=min(i,75);y++){
for(int z=0;z<=min(i,75);z++){
if(!f[i&1][x][y][z]) continue;
DP1(i,x,y,z,f[i&1][x][y][z]);
DP2(i,x,y,z,f[i&1][x][y][z]);
}
}
}
}
printf("%d\n",ans*2%mod);
return 0;
}
113.[NOIP2021] 方差
先模一下第一篇題解的數(shù)學(xué)大師。
首先雖然很難發(fā)現(xiàn)但是不難證明操作相當(dāng)于是交換差分?jǐn)?shù)組。
而題目要求的式子可以寫成 \(n\times \sum a_i^2 - (\sum a_i)^2\)。
考慮運(yùn)用我們初二的數(shù)學(xué)知識，方差越小意味著數(shù)據(jù)波動越小。
也就是我們在把序列排序后，他的圖像應(yīng)該是：增長速度先變緩，然后保持在平均數(shù)，再快速增長。
在差分?jǐn)?shù)組上的表示就是差分?jǐn)?shù)組先減小后增大，呈單谷。
所以我們先把差分?jǐn)?shù)組升序排序。
那么不難想到按差分的值從小到大 dp，每一次往差分?jǐn)?shù)組里面放數(shù)，要么放開頭要么放結(jié)尾。
但是這樣不太方便維護(hù)上面那個式子，于是考慮把一個值放進(jìn) dp。
設(shè) \(f_{i,j}\) 表示放了 \(i\) 個差分值，且目前還原出的原序列的 \(\sum a_i\) 為 \(j\) 時 \(\sum a_i^2\) 的最小值。
轉(zhuǎn)移時：
- 下一個放開頭：\(f_{i,j} + 2\times j\times c_{i+1} + (i+1)\times (c_{i+1}^2) \to f_{i+1,j+(i+1)\times c_{i+1}}\)。
- 下一個放結(jié)尾：\(f_{i,j} + pre_{i+1}^2 \to f_{i+1,j+pre_{i+1}}\)，\(pre_{i+1}=\sum_{j=1}^{i+1} c_j\)。
目前時間復(fù)雜度是 \(O(n^2V)\) 的。
因?yàn)樵瓟?shù)組有序，而我們會發(fā)現(xiàn) \(n\) 遠(yuǎn)大于 \(V\) 所以有很多差分為 \(0\)，這一部分沒有必要轉(zhuǎn)移。
當(dāng)然不轉(zhuǎn)移不代表不給他狀態(tài)，你不能直接去掉那些為 \(0\) 的差分值（可能只有我一開始是這么寫的）。
差分不為 \(0\) 的只有 \(V\) 個，所以復(fù)雜度變?yōu)?\(O(nV^2)\)。
然后因?yàn)檫@個數(shù)據(jù) \(n\) 和 \(a\) 成反比，所以不想把代碼復(fù)制一份的話建議滾動數(shù)組。
code
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+5,inf=0x3f3f3f3f3f3f3f3f;
inline int read(){
int w = 1, s = 0;
char c = getchar();
for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
return s * w;
}
int n,m,a[10005],t[10005],c[10005],pre[10005],sum,f[2][N];
signed main(){
n=read();
int maxn=0;
for(int i=1;i<=n;i++) a[i]=read(),maxn=max(maxn,a[i]);
sum=n*maxn;
for(int i=1;i<n;i++) c[i]=a[i+1]-a[i];
sort(c+1,c+n);
m=n-1;
for(int i=1;i<=m;i++) pre[i]=pre[i-1]+c[i];
memset(f,0x3f,sizeof f);
f[0][0]=0;
for(int i=0;i<m;i++){
if(c[i+1]==0) f[i&1^1][0]=0;
else{
for(int j=0;j<=sum;j++) f[i&1^1][j]=inf;
for(int j=0;j<=sum;j++){
if(j+(i+1)*c[i+1]<=sum) f[(i+1)&1][j+(i+1)*c[i+1]] = min(f[(i+1)&1][j+(i+1)*c[i+1]] , f[i&1][j] + 2*j*c[i+1] + (i+1)*(c[i+1]*c[i+1]));
if(j+pre[i+1]<=sum) f[(i+1)&1][j+pre[i+1]] = min(f[(i+1)&1][j+pre[i+1]] , f[i&1][j] + pre[i+1]*pre[i+1]);
}
}
}
int ans=inf;
for(int i=0;i<=sum;i++){
if(f[m&1][i]==inf) continue;
ans=min(ans,n*(f[m&1][i] + 2*i*a[1] + n*a[1]*a[1]) - (i+n*a[1]) * (i+n*a[1]));
}
printf("%lld\n",ans);
return 0;
}
114.Match
題目翻譯：
有兩個序列 \(a，b\)，以及一張二分圖，二分圖中左部節(jié)點(diǎn) \(i\) 和右部節(jié)點(diǎn) \(j\) 有邊的條件是：\(a_i\oplus b_j \ge k\)。
對每個 \(1\le k\le n\) 求二分圖大小為 \(k\) 的匹配的數(shù)量。
這種異或起來大于或小于某個數(shù)的題以前有做過：CF1616H。
兩個思路：一個在 Trie 上考慮，一個直接在序列上考慮，兩者殊途同歸，為了方便理解我們在 Trie 上考慮。
因?yàn)轭}目要求的是匹配數(shù)量，數(shù)據(jù)范圍又很小，考慮直接 dp。
注意因?yàn)橛袃蓚€序列所以我們維護(hù)兩棵 Trie。
設(shè) \(f(u,v,i)\) 表示在 \(a\) 序列的 Trie 的 \(u\) 子樹和 \(b\) 序列的 Trie 的 \(v\) 子樹內(nèi)選出大小為 \(i\) 的匹配的方案數(shù)。
- 如果 \(k\) 當(dāng)前這一位為 \(1\)：
那么一對匹配不能同時在 \(ch1_{u,0},ch2_{v,0}\) 或同時在 \(ch1_{u,1},ch2_{v,1}\) 子樹內(nèi)。
\(f(ch1_{u,0},ch2_{v,1},x)\times f(ch1_{u,1},ch2_{v,0},y) \to f(u,v,x+y)\)。 - 如果 \(k\) 當(dāng)前這一位為 \(0\)，此時的匹配可以是來自：
- \(f(ch1_{u,0},ch2_{v,0},x)\)
- \(f(ch1_{u,1},ch2_{v,1},y)\)
- \(ch1_{u,0}\) 和 \(ch2_{v,1}\) 隨便組合。
- \(ch1_{u,1}\) 和 \(ch2_{v,0}\) 隨便組合。
可先算出后兩個組合的方案數(shù)，再算出四個合在一起的方案數(shù)。
代碼實(shí)現(xiàn)時注意到你開不下 \(O(60^2n^3)\) 的數(shù)組，但是兒子的 dp 數(shù)組只在父親有用到，所以在 dfs 時直接返回 dp 數(shù)組，也不需要真的去把 Trie 樹建出來。
復(fù)雜度的話，因?yàn)檫@個轉(zhuǎn)移本質(zhì)是樹形背包，所以其實(shí)是 \(O(n^4)\)。
代碼參考了一篇題解。
因?yàn)?vector 都是動態(tài)開空間，所以一定要注意每個 vector 到底要開多少。
這應(yīng)該是我寫過的最高級的代碼（指語法）。
code
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e2+5,mod=998244353;
inline int read(){
int w = 1, s = 0;
char c = getchar();
for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
return s * w;
}
int n,k,inv[N],fact[N],q[N];
int C(int n,int m){
if(n<m) return 0;
return fact[n]*q[m]%mod*q[n-m]%mod;
}
void Init(){
fact[0]=1;
for(int i=1;i<N;i++) fact[i]=fact[i-1]*i%mod;
inv[1]=1;
for(int i=2;i<N;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod;
q[0]=1;
for(int i=1;i<N;i++) q[i]=q[i-1]*inv[i]%mod;
}
vector<int> merge1(vector<int> f1,vector<int> f2){ //合并兩個 dp 數(shù)組
vector<int> dp(f1.size()+f2.size()-1,0);
for(int i=0;i<f1.size();i++)
for(int j=0;j<f2.size();j++)
(dp[i+j]+=f1[i]*f2[j]%mod)%=mod;
return dp;
}
vector<int> merge2(int n,int m){ //表示 n 個左部節(jié)點(diǎn)和 m 個右部節(jié)點(diǎn)隨意匹配的方案數(shù)
vector<int> res(min(n,m)+1);
for(int i=0;i<res.size();i++) res[i]=C(n,i)*C(m,i)%mod*fact[i]%mod;
return res;
}
vector<int> dfs(int pos,vector<int> &a,vector<int> &b){
if(a.empty() || b.empty()) return {1};
if(pos==-1) return merge2(a.size(),b.size());
vector<int> A0,A1,B0,B1;
for(int x:a) if(x>>pos&1) A1.emplace_back(x); else A0.emplace_back(x);
for(int x:b) if(x>>pos&1) B1.emplace_back(x); else B0.emplace_back(x);
if(k>>pos&1) return merge1(dfs(pos-1,A0,B1),dfs(pos-1,A1,B0));
vector<int> f1=dfs(pos-1,A0,B0),f2=dfs(pos-1,A1,B1);
vector<int> dp(min(a.size(),b.size())+1,0);
for(int i=0;i<f1.size();i++){
for(int j=0;j<f2.size();j++){
int lstA0=A0.size()-i,lstA1=A1.size()-j; //計(jì)算剩余可供合并的點(diǎn)
int lstB0=B0.size()-i,lstB1=B1.size()-j;
vector<int> f3=merge1(merge2(lstA0,lstB1) , merge2(lstA1,lstB0)); //先計(jì)算隨便匹配的方案數(shù)。
for(int k=0;k<f3.size();k++) (dp[i+j+k]+=f1[i]*f2[j]%mod*f3[k]%mod)%=mod;
f3.clear(); f3.shrink_to_fit(); //釋放空間
}
}
f1.clear(); f1.shrink_to_fit(); //釋放空間
f2.clear(); f2.shrink_to_fit(); //釋放空間
return dp;
}
signed main(){
n=read(),k=read();
vector<int> a(n),b(n);
for(int i=0;i<n;i++) a[i]=read();
for(int i=0;i<n;i++) b[i]=read();
Init();
vector<int> ans=dfs(60,a,b);
while(ans.size()<n+1) ans.emplace_back(0);
for(int i=1;i<=n;i++) printf("%lld\n",ans[i]);
return 0;
}
115.[AGC009E] Eternal Average
考慮把最終的樹畫出來：
這棵 \(k\) 叉樹有 \(n+m\) 個葉子，\(n\) 個葉子權(quán)值為 \(0\)，\(m\) 個葉子的權(quán)值為 \(1\)，父親的權(quán)值為兒子權(quán)值的平均數(shù)，最終剩的數(shù)就是根的權(quán)值。
因?yàn)橄喈?dāng)于是每一次少 \(k-1\) 個點(diǎn)，所以題目保證了 \((k-1)|(n+m-1)\)。
設(shè) \(m\) 個點(diǎn)的深度分別為 \(x_i\)（根的深度為 \(0\)），\(n\) 個點(diǎn)的深度分別為 \(y_i\)，那么容易知道根的權(quán)值為 \(\sum_{i=1}^m (\frac{1}{k})^{x_i}\)。
而如果所有葉節(jié)點(diǎn)的權(quán)值均為 \(1\)，那么根的權(quán)值為 \(1\)，所以 \(\sum_{i=1}^m (\frac{1}{k})^{x_i}+\sum_{i=1}^n (\frac{1}{k})^{y_i} = 1\)。
而如果給定了 \(x_i\) 和 \(y_i\) 且滿足 \(\sum_{i=1}^m (\frac{1}{k})^{x_i}+\sum_{i=1}^n (\frac{1}{k})^{y_i} = 1\)，那肯定也可以構(gòu)造出一棵合法的 \(k\) 叉樹。
證明：
考慮最后的 \(1\) 怎么得到的，首先深度為 \(1\) 的層必然有 \(k\) 個點(diǎn)。
然后我們把滿足 \(x_i=1,y_j=1\) 的點(diǎn)分配到第 \(1\) 層，那么第 \(1\) 層還會剩下一些點(diǎn)，這些點(diǎn)是由第 \(2\) 層合并上來的。
由此不斷往下一層考慮，每一層的點(diǎn)必然都是 \(k\) 的倍數(shù)，而且 \(n+m\) 個點(diǎn)都能得到分配。
當(dāng)然你也可以把這個過程看成在 \(k\) 進(jìn)制下的小數(shù)的加法的逆過程（即不斷退位）。
現(xiàn)在問題變成：求滿足 \(\sum_{i=1}^m (\frac{1}{k})^{x_i}+\sum_{i=1}^n (\frac{1}{k})^{y_i} = 1\) 的不同 \(\sum_{i=1}^m (\frac{1}{k})^{x_i}\) 的個數(shù)。
可以發(fā)現(xiàn)，在 \(k\) 進(jìn)制下，如果不考慮進(jìn)位，\(\sum_{i=1}^m (\frac{1}{k})^{x_i}\) 的數(shù)位和 \(= m\)（我們下面記它為 \(0.c_1c_2c_3....c_l\)），即 \(\sum_{j=1}^l c_j= m\)。
因?yàn)榇藭r數(shù)位和的實(shí)際意義就是有多少個值為 \(1\) 的葉子。
那么對于一個進(jìn)位過的 \(\sum_{i=1}^m (\frac{1}{k})^{x_i}\)，由于進(jìn)位的過程是把 \(j+1\) 位 \(-k\)，第 \(j\) 位 \(+1\)，所以此時的 \(\sum_{j=1}^l c_j \equiv m \pmod{k-1}\)。
而如果一個小數(shù) \(0.c_1c_2c_3....c_l\) 他的數(shù)位和 \(sum\le m\) 且 \(sum \equiv m \pmod{k-1}\)，那么我們通過不斷退位總可以使 \(sum=m\)，此時就可以構(gòu)造出合法的 \(x\) 序列。
而因?yàn)?\(\sum_{i=1}^m (\frac{1}{k})^{x_i}+\sum_{i=1}^n (\frac{1}{k})^{y_i} = 1\)，所以 \(\sum_{i=1}^n (\frac{1}{k})^{y_i} = 1-\sum_{i=1}^m (\frac{1}{k})^{x_i}\)，所以 \(\sum_{i=1}^n (\frac{1}{k})^{y_i}\) 的數(shù)位和為 \(1+l\times (k-1)-sum\)。
類似的可以證明它同樣需要與 \(n\) 模 \(k-1\) 同余。
于是我們得出了一個結(jié)果 \(\sum_{i=1}^m (\frac{1}{k})^{x_i}\) 合法的充要條件（\(sum\) 是數(shù)位和，\(l\) 是位數(shù)）：
- \(sum \equiv m \pmod{k-1}\)。
- \(1+l\times (k-1)-sum \equiv n \pmod{k-1}\)。
然后就可以 DP 了。
設(shè) \(f_{i,j,0/1}\) 表示考慮了前 \(i\) 個小數(shù)位，位數(shù)和為 \(j\)，最后一位是否是 \(0\) 能構(gòu)成的不同 \(\sum_{i=1}^m (\frac{1}{k})^{x_i}\) 的方案數(shù)。
轉(zhuǎn)移就是個樸素的背包。
當(dāng)且僅當(dāng) \(j \equiv m \pmod{k-1}\) 且 \(1+i\times (k-1)-j \equiv n \pmod{k-1}\) 且末尾沒有后導(dǎo) \(0\) 時，可以統(tǒng)計(jì)入答案。
code
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e3+5,mod=1e9+7;
inline int read(){
int w = 1, s = 0;
char c = getchar();
for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
return s * w;
}
int n,m,k,f[N<<1][N][2],pre[N<<1][N],ans=0;
signed main(){
n=read(),m=read(),k=read();
f[0][0][0]=1;
for(int j=0;j<=m;j++) pre[0][j]=1;
for(int i=1;i<=n+m-1;i++){
for(int j=0;j<=m;j++){
f[i][j][0]=(f[i-1][j][0]+f[i-1][j][1])%mod;
int tmp=min(j,k-1);
if(tmp>=1) f[i][j][1] = ( pre[i-1][j-1] - ((j-tmp-1>=0)?pre[i-1][j-tmp-1]:0) + mod ) % mod;
pre[i][j] = (((j==0) ? 0 : pre[i][j-1]) + f[i][j][0] + f[i][j][1] ) % mod;
if((m-j)%(k-1)==0 && (1+i*(k-1)-j<=n) && (n-1-i*(k-1)+j)%(k-1)==0) (ans+=f[i][j][1])%=mod;
}
}
printf("%lld\n",ans);
return 0;
}
116.[NOI2008] 奧運(yùn)物流
因?yàn)轭}目說每個點(diǎn)都可以到 \(1\) 號點(diǎn)，所以 \(1\) 一定在那個環(huán)中。
首先先考慮如果不是基環(huán)樹，而是一棵以 \(1\) 為根的內(nèi)向樹時該怎么做。
此時容易得到 \(R(1) = \sum_{i=1}^n C_i\times k^{dep_i}\)，其中 \(dep_1=0\)。
那么我們每一次操作一定是把一個點(diǎn)的后繼點(diǎn)直接改成 \(1\)，即把它樹上的父親變?yōu)?\(1\) 號點(diǎn)。
因?yàn)樽詈蟮拇鸢钢桓?\(dep\) 有關(guān)，所以我們只需要知道每個點(diǎn)在最終樹上的深度即可，考慮樹形 DP。
設(shè) \(f_{i,j,k}\) 表示：當(dāng)前在考慮 \(i\) 子樹，且 \(i\) 子樹內(nèi)（不包含 \(i\)）有 \(j\) 個點(diǎn)的父親被修改了，\(i\) 在最終得到的樹的深度為 \(k\) 時，\(i\) 子樹內(nèi)（包含 \(i\)）的點(diǎn)的 \(\sum C_i\times k^{dep_i}\) 的最大值。
轉(zhuǎn)移時考慮樹形背包，每次加進(jìn)來 \(u\) 的一個子樹 \(v\)：
- 若 \(v\) 自己不修改，那 \(v\) 的深度就是 \(u\) 的深度 \(+1\)：\(f_{u,i,k}+f_{v,j,k+1} \to f_{u,i+j,k}\)。
- 若 \(v\) 自己修改了，那 \(v\) 的深度為 \(1\)：\(f_{u,i,k}+f_{v,j,1} \to f_{u,i+j+1,k}\)
因?yàn)槭菢湫伪嘲詥未螛湫?DP 是 \(O(n^3)\)。
考慮基環(huán)樹，對于環(huán)上的點(diǎn)列 \(len\) 元一次方程組（\(len\) 為環(huán)長），解一下可以得到 \(R(1)=\dfrac{\sum_{i=1}^n C_i\times k^{dist_i}}{1-k^{len}}\)，其中 \(dist(i)\) 表示 \(i\) 需要走幾步可以到 \(1\)（其實(shí)上面的 \(dep\) 也可以寫成 \(dist\)）。
假設(shè)環(huán)是 \(1\to x_1\to x_2\to ... \to x_{len-1}\)。
如果環(huán)上有點(diǎn)需要修改，那也一定是連向 \(1\)，因?yàn)檫@樣分母變小，分子變大，整體變大。
我們枚舉第一個修改的點(diǎn) \(x_i\)，讓他指向 \(1\)，現(xiàn)在環(huán)變成了 \(1\to x_1\to x_2\to ... \to x_i\)，環(huán)長變?yōu)?\(i+1\)。
然后會發(fā)現(xiàn)最后的式子只跟 \(dist\) 和環(huán)長有關(guān)，現(xiàn)在環(huán)長已經(jīng)確定為 \(i\) 了，而在算 \(dist\) 時一定不會用到 \(1 \to x_1\) 這條邊。
所以我們可以現(xiàn)在直接把這條邊斷掉，這樣的話圖就變成了一棵樹，可以直接跑樹形 DP。
總時間復(fù)雜度 \(O(n^4)\)。
code
#include<bits/stdc++.h>
#define PII pair<int,int>
#define fi first
#define se second
using namespace std;
const int N=60+5;
inline int read(){
int w = 1, s = 0;
char c = getchar();
for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
return s * w;
}
int n,m,nxt[N];
double k,p[N],C[N];
int st[N],top;
vector<int> G[N];
PII novis;
double f[N][N][N],ans;
int Size[N];
void dfs(int u,int dep){
Size[u]=1;
for(int i=0;i<=dep;i++) f[u][0][i]=p[i]*C[u];
for(int v:G[u]){
if(u==novis.fi && v==novis.se) continue;
dfs(v,dep+1);
for(int x=Size[u];x>=0;x--){
for(int y=Size[v];y>=0;y--){
if(x+y>m) continue;
for(int i=0;i<=n;i++){
if(x+y+1<=m) f[u][x+y+1][i]=max(f[u][x+y+1][i],f[u][x][i]+f[v][y][1]);
f[u][x+y][i]=max(f[u][x+y][i],f[u][x][i]+f[v][y][i+1]);
}
}
}
Size[u]+=Size[v];
}
}
signed main(){
scanf("%d%d%lf",&n,&m,&k);
for(int i=1;i<=n;i++) scanf("%d",&nxt[i]);
for(int i=1;i<=n;i++) scanf("%lf",&C[i]);
p[0]=1.0;
for(int i=1;i<=n;i++) p[i]=p[i-1]*k;
int u=1;
st[++top]=1;
while(nxt[u]!=1) st[++top]=nxt[u],u=nxt[u];
for(int i=2;i<=n;i++) G[nxt[i]].push_back(i); //自動忽略 (nxt[1],1) 這條邊
for(int i=2;i<=top;i++){
if(i!=top && m==0) continue;
if(i!=top){
novis={st[i+1],st[i]};
m--; //已經(jīng)用掉了一次
G[1].push_back(st[i]);
}
for(int i=1;i<=n;i++) for(int j=0;j<=m;j++) for(int d=0;d<=n;d++) f[i][j][d]=-1e9;
dfs(1,0);
ans=max(ans,f[1][m][0]/(1.0-p[i])); //因?yàn)檫@里的 i 算上了 1 號點(diǎn)，所以不用寫 i+1
if(i!=top){
novis={0,0};
m++;
G[1].pop_back();
}
}
printf("%.2lf\n",ans);
return 0;
}
117.[THUWC 2017] 隨機(jī)二分圖
首先根據(jù)期望的定義，最后的期望等于每個完美匹配出現(xiàn)的概率之和。
而我們在算每個完美匹配出現(xiàn)的概率時，只需要算上完美匹配中的邊出現(xiàn)的概率即可，其他的邊出不出現(xiàn)都無所謂，不用算進(jìn)概率。
也就是說如果一組里的邊并沒有出現(xiàn)在匹配里，這組邊的概率其實(shí)不用管。
考慮只有第一類組怎么做。
設(shè) \(f_{i,S}\) 表示左部節(jié)點(diǎn)的前 \(i\) 個點(diǎn)匹配了右部 \(S\) 中的點(diǎn)的匹配的期望個數(shù)。
轉(zhuǎn)移時考慮所有以 \(i+1\) 為左部節(jié)點(diǎn)的邊即可。
現(xiàn)在我們加上第二，三兩類組，因?yàn)榇藭r我們加點(diǎn)的順序會是無序的（即左部節(jié)點(diǎn)可能不是從 1 順序加到 n 的），所以樸素的思想是設(shè) \(f_{S,T}\) 表示左部 \(S\) 的點(diǎn)匹配了右部 \(T\) 的點(diǎn)的匹配的個數(shù)。
但這會有一個問題，就是第二組里的兩條邊雖然會同時出現(xiàn)在圖中，但不一定同時出現(xiàn)在匹配中，換句話說我們需要?dú)J定第二組里的邊到底是一下哪種狀態(tài)：
- 只有第一條邊在匹配中。
- 只有第二條邊在匹配中。
- 兩條邊全在匹配中。
- 兩條邊全不在匹配中（當(dāng)然這個情況并不會對概率做出貢獻(xiàn)，其實(shí)不用考慮）。
但是注意到在轉(zhuǎn)移 \(f_{S,T}\) 時我們記錄不了哪些組被轉(zhuǎn)移過了，我們其實(shí)只能通過這組里的邊的點(diǎn)是否在 \(S\) 和 \(T\) 里出現(xiàn)了來判斷。
如果只有第一類組，這種轉(zhuǎn)移沒有任何的問題，但是當(dāng)有了第二類組就會有問題，因?yàn)橄旅鎯煞N情況本質(zhì)是一樣的，但都會被算一次，就重復(fù)了：
- 第一次就欽定兩條邊全出現(xiàn)在匹配里。
- 第一次只欽定出現(xiàn)了第一條邊，第二次再考慮到這條邊時又欽定了只出現(xiàn)第二條邊。
而我們并不能去記錄每個第二類組的狀態(tài)，所以不能這么轉(zhuǎn)移。
然后就有一個非常神奇的思路：既然我們只能處理第一類組，那不妨把第二三類組都拆成兩個第一類組，然后看一下這么轉(zhuǎn)移會多轉(zhuǎn)移或少轉(zhuǎn)移什么東西。
對于第二類組，假設(shè)它里面的兩條邊是 \((u,v)\) 和 \((x,y)\)，現(xiàn)在它已經(jīng)變成兩個分別包含了 \((u,v)\) 和 \((x,y)\) 的第一類組。
- 當(dāng)最后只有 \((u,v)\) 在完美匹配中，即對應(yīng)了狀態(tài) 2.，對概率的貢獻(xiàn)是 \(\frac{1}{2}\)。
- 當(dāng)最后只有 \((x,y)\) 在完美匹配中，即對應(yīng)了狀態(tài) 3，對概率的貢獻(xiàn)是 \(\frac{1}{2}\)。
- 當(dāng)最后 \((x,y)\) 和 \((u,v)\) 全在完美匹配中，即對應(yīng)了狀態(tài) 4.，那此時的貢獻(xiàn)是 \(\frac{1}{4}\)，可其實(shí)概率是 \(\frac{1}{2}\)。
那我們只需要多加一個表示 \((x,y)\) 和 \((u,v)\) 全在完美匹配中的，且系數(shù)為 \(\frac{1}{4}\) 的轉(zhuǎn)移就可以把上面漏掉的那 \(\frac{1}{4}\) 的概率加上。
對于第三類組，同樣假設(shè)它里面的兩條邊是 \((u,v)\) 和 \((x,y)\)，現(xiàn)在它已經(jīng)變成兩個分別包含了 \((u,v)\) 和 \((x,y)\) 的第一類組。
- 前面兩個情況的分析是一樣的，沒有問題。
- 當(dāng)最后 \((x,y)\) 和 \((u,v)\) 全在完美匹配中，那此時的貢獻(xiàn)是 \(\frac{1}{4}\)，可其實(shí)概率是 \(0\)，因?yàn)樗麄儔焊荒芡瑫r出現(xiàn)。
那我們只需要多加一個表示 \((x,y)\) 和 \((u,v)\) 全在完美匹配中的，且系數(shù)為 \(-\frac{1}{4}\) 的轉(zhuǎn)移就可以把上面多的的那 \(\frac{1}{4}\) 的概率減掉。
然后為了防止把不同的加入順序算成不同方案，每一次可以欽定只轉(zhuǎn)移編號最小的左部節(jié)點(diǎn)。
code
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5,mod=1e9+7;
inline int read(){
int w = 1, s = 0;
char c = getchar();
for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
return s * w;
}
int n,m,inv2,inv4;
int a[N],b[N],cnt; //分別表示轉(zhuǎn)移和這個轉(zhuǎn)移的系數(shù)
int quick_power(int a,int b){
int ans=1;
while(b){
if(b&1) (ans*=a)%=mod;
b>>=1,(a*=a)%=mod;
}
return ans;
}
map<int,int> f;
int dfs(int S){
if(f.count(S)) return f[S]; // 別寫 f[S]!=0 因?yàn)?f[S] 可以 =0
for(int i=0;i<n;i++){
if(!(S>>i&1)){ //不用考慮是否有組包含編號最小的沒被算進(jìn)匹配的點(diǎn)，因?yàn)闆]有的話這個圖一定沒有完美匹配，答案為0
int res=0;
for(int j=1;j<=cnt;j++){
if( (a[j]>>i&1)==1 && (a[j]&S)==0 ){ //當(dāng)前轉(zhuǎn)移得包含 i，并且沒有在 S 中出現(xiàn)過
(res+=b[j]*dfs(S|a[j])%mod)%=mod;
}
}
return f[S]=res;
}
}
}
signed main(){
inv2=quick_power(2,mod-2),inv4=quick_power(4,mod-2);
n=read(),m=read();
for(int i=1;i<=m;i++){
int op=read(),x=read()-1,y=read()-1;
a[++cnt]=(1<<x)|(1<<(y+n));
b[cnt]=inv2;
if(op>0){
int u=read()-1,v=read()-1;
a[++cnt]=(1<<u)|(1<<(v+n)); //直接壓成一個二進(jìn)制數(shù)，很高級
b[cnt]=inv2;
if(x==u || y==v) continue; //這種情況絕對不可能出現(xiàn) (x,y) 和 (u,v) 一起出現(xiàn)在匹配中的情況
int tmp=(1<<x)|(1<<(y+n)) | (1<<u)|(1<<(v+n));
if(op==1) a[++cnt]=tmp,b[cnt]=inv4;
else a[++cnt]=tmp,b[cnt]=-inv4+mod;
}
}
f[(1<<(n<<1))-1]=1;
printf("%lld\n",quick_power(2,n)*dfs(0)%mod);
return 0;
}
118.[ARC098F] Donation
考慮正難則反：
即假設(shè)我們現(xiàn)在在終點(diǎn)，往回退著走，那么假設(shè)在第一次到達(dá)點(diǎn) \(u\) 時我有 \(x\) 元錢，那需要滿足 \(x\ge \max(0,A_u-B_u)\)，然后在這個點(diǎn)時會得到 \(B_u\) 的錢。
就算我們后面可能會再回到這個點(diǎn)，但是注意到倒著做的話我們的錢只增不減，而現(xiàn)在 \(\ge A_u-B_u\)，那加完 \(B_u\) 后錢數(shù)就 \(\ge A_u\) 了，所以后面就算回到 \(u\) 也不用擔(dān)心錢數(shù)會 \(<A_u\)。
這樣總答案就是在終點(diǎn)的錢數(shù) \(+\sum_{i=1}^n B_i\)。
但是你如果按照 \(C_u=\max(0,A_u-B_u)\) 從小到大貪心的遍歷會出問題，因?yàn)槟銖?\(u\) 走到 \(v\) 的過程中可能會經(jīng)過其他 \(C\) 更大的點(diǎn)。
考慮以 \(C\) 建出 Kruskal 重構(gòu)樹（邊權(quán)設(shè)為兩個端點(diǎn)的 \(C\) 的最大值），然后樹形 DP，設(shè) \(f_u\) 表示遍歷完 \(u\) 子樹所需要的最小錢數(shù)，\(sum_u\) 表示 \(u\) 子樹內(nèi)所有葉子的 \(B\) 的和。
那么枚舉起點(diǎn)在哪棵子樹內(nèi)，假設(shè)在 \(v\) 子樹內(nèi)，那么遍歷完 \(v\) 后你會有 \(x+sum_v\) 個錢（\(x\) 是初始的錢數(shù)），此時你需要滿足 \(x+sum_v\ge C_u\)。
然后因?yàn)?\(C_u\) 是其子樹內(nèi)所有 \(C\) 最大的，那么在到達(dá) \(u\) 之后再往下去其他子樹就一定滿足了。
所以轉(zhuǎn)移為： \(f_u=\min_v(\max(C_u-sum_v,f_v))\)，\(C_u-sum_v\) 的意思是至少要這么多可以走到 \(u\)。
code
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
inline int read(){
int w = 1, s = 0;
char c = getchar();
for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
return s * w;
}
int n,m,tot,head[N],to[N],Next[N],A[N],B[N],C[N];
void add(int u,int v){
to[++tot]=v,Next[tot]=head[u],head[u]=tot;
}
struct Edge{
int u,v,w;
}e[N];
int fa[N],cnt;
int get(int x){
return (x==fa[x])?x:(fa[x]=get(fa[x]));
}
int sum[N],f[N];
void dfs(int u){
if(!head[u]){
sum[u]=B[u];
f[u]=C[u];
return;
}
f[u]=LLONG_MAX;
for(int i=head[u];i;i=Next[i]){
int v=to[i];
dfs(v);
sum[u]+=sum[v];
f[u]=min(f[u],max(f[v],C[u]-sum[v]));
}
}
signed main(){
n=read(),m=read();
for(int i=1;i<=n;i++){
A[i]=read(),B[i]=read();
C[i]=max(A[i]-B[i],0ll);
}
for(int i=1;i<=m;i++){
int u=read(),v=read(),w=max(C[u],C[v]);
e[i]={u,v,w};
}
for(int i=1;i<=2*n-1;i++) fa[i]=i;
sort(e+1,e+m+1,[&](Edge x,Edge y){return x.w<y.w;});
cnt=n;
for(int i=1;i<=m;i++){
int u=e[i].u,v=e[i].v,w=e[i].w;
if(get(u)==get(v)) continue;
u=get(u),v=get(v);
++cnt;
C[cnt]=w;
add(cnt,u),add(cnt,v);
fa[u]=cnt,fa[v]=cnt;
}
dfs(cnt);
printf("%lld\n",f[cnt]+sum[cnt]);
return 0;
}
浙公網(wǎng)安備 33010602011771號