[APIO2014]连珠线

考虑一组以 \(x\) 为中点的蓝边，有两种可能：

\[son[x]->x->fa[x]
\]

\[son[x]->x->son[x]
\]

其中若有两个儿子间连边的点不存在祖先关系，那么它们就无法被连接到一起

因此所有的儿子间连边的点一定在一条链上

因此，若以链的最低点为根，那么所有儿子间连边的点的情况可以归纳为 \(son[x]->x->fa[x]\) 的情况

换根 \(dp\) 即可

点击查看代码

#include<bits/stdc++.h>
using namespace std;
int n;
int ver[400005],ne[400005],head[200005],cnt,val[400005];
inline void link(int x,int y,int v){
    ver[++cnt]=y;
    ne[cnt]=head[x];
    head[x]=cnt;val[cnt]=v;
}
long long dp[2][200005],f[200005];
void dfs1(int x,int fi){
    dp[1][x]=f[x]=-1e18;
    for(int i=head[x];i;i=ne[i]){
        int u=ver[i];
        if(u==fi)continue;
        dfs1(u,x);
        long long tmp=max(dp[0][u],dp[0][u]+dp[1][u]+val[i]),tmp2=dp[0][u]+val[i]-tmp;
        if(tmp2>dp[1][x])f[x]=max(f[x],dp[1][x]);
        else f[x]=max(f[x],tmp2);
        dp[0][x]+=tmp;dp[1][x]=max(dp[1][x],tmp2);
    }
}
long long ans;
void dfs2(int x,int fi){
    ans=max(ans,dp[0][x]);
    for(int i=head[x];i;i=ne[i]){
        int u=ver[i];
        if(u==fi)continue;
        long long tmp=max(dp[0][u],dp[0][u]+dp[1][u]+val[i]),tmp2=dp[0][u]+val[i]-tmp;
        if(dp[1][x]==tmp2)dp[1][x]=f[x];
        dp[0][x]-=tmp;
        {
            long long tmp3=max(dp[0][x],dp[0][x]+dp[1][x]+val[i]),tmp4=dp[0][x]+val[i]-tmp3;
            dp[0][u]+=tmp3;
            if(tmp4>dp[1][u])f[u]=max(f[u],dp[1][u]);
            else f[u]=max(f[u],tmp4);
            dp[1][u]=max(dp[1][u],tmp4);
            dfs2(u,x);
        }
        dp[0][x]+=tmp;dp[1][x]=max(dp[1][x],tmp2);
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<n;i++){
        int x,y,z;scanf("%d%d%d",&x,&y,&z);
        link(x,y,z);link(y,x,z);
    }
    dfs1(1,1);dfs2(1,1);
    printf("%lld",ans);

    return 0;
} 

[ZJOI2017]仙人掌

对树加边，使每条边最多一个环上，等价于将若干条不相交的链覆盖到树上

对于每个点，枚举与它相连的边的所有匹配情况即可

点击查看代码

#include<bits/stdc++.h>
using namespace std;
int t;
int n,m;
int ver[5000005],ne[5000005],head[5000005],ct;
bool is;
inline void link(int x,int y){
    ver[++ct]=y;
    ne[ct]=head[x];
    head[x]=ct;
}
int dfn[5000005],low[5000005],cnt;
int stk[5000005],top,col[5000005],tot;
void tarjan(int x,int fi){
    dfn[x]=low[x]=++cnt;
    bool flag=0;stk[++top]=x;
    for(int i=head[x];i;i=ne[i]){
        int u=ver[i];
        if(u==fi)continue;
        if(!dfn[u]){
            tarjan(u,x);
            low[x]=min(low[x],low[u]);
            if(low[u]<dfn[x]){
                if(flag){is=0;return ;}
                flag=1;
            }
        }
        else {
            low[x]=min(low[x],dfn[u]);
            if(dfn[u]<dfn[x]){
                if(flag){is=0;return ;}
                flag=1;
            }
        }
    }
    if(dfn[x]==low[x]){
        col[x]=++tot;
        while(stk[top]!=x)col[stk[top--]]=tot;
        top--;
    }
}
long long dp[5000005],g[5000005];
const long long md=998244353;
bool vis[5000005];
void dfs(int x,int fi){
    dp[x]=1;vis[x]=1;
    int siz=0;
    for(int i=head[x];i;i=ne[i]){
        int u=ver[i];
        if(u==fi||col[u]==col[x])continue;
        dfs(u,x);siz++;
        dp[x]=dp[x]*dp[u]%md;
    }
    dp[x]=dp[x]*g[siz+(fi!=x)]%md;
//    cout<<x<<" "<<dp[x]<<" "<<siz+(fi!=x)<<endl;
}
int main(){
    g[0]=g[1]=1;
    for(int i=2;i<=5e6;i++)g[i]=(g[i-1]+g[i-2]*(i-1)%md)%md;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)head[i]=0;ct=0;is=1;
        for(int i=1;i<=n;i++)vis[i]=0;cnt=0;tot=0;
        for(int i=1;i<=n;i++)dfn[i]=0;
        for(int i=1;i<=m;i++){
            int x,y;
            scanf("%d%d",&x,&y);
            link(x,y);link(y,x);
        }
        tarjan(1,1);
//        for(int i=1;i<=n;i++)cout<<col[i]<<" ";cout<<endl;
        if(!is){
            puts("0");
            continue;
        }
        long long ans=1;
        for(int i=1;i<=n;i++)if(!vis[i]){
            dfs(i,i);//cout<<i<<":\n";
            ans=ans*dp[i]%md;
        }
//        for(int i=1;i<=n;i++)cout<<dp[i]<<" ";
        printf("%lld\n",ans);
    }

    return 0;
} 

[ZJOI2016]线段树 加强版（小小猫咪）

期望乘以总方案数就是对所有方案求和

考虑暴力 \(dp\) ：令 \(f[v][i][l][r]\) 表示区间 \([l,r]\) 内的值小于 \(val[v]\) ，且 \(a[l-1],a[r+1]>val[v]\) 的方案数，再令：

\[pre(v,i,j)=\sum_{t=1}^{j}f[v][i][t][r]*(t-1)
\\
suf(v,i,j)=\sum_{t=j}^{n}f[v][i][l][t]*(n-t)
\]

有：

\[f[v][i][l][r]=f[v][i-1][l][r]*g(l,r)+pre(v,i-1,l-1)+suf(v,i-1,r+1)
\]

其中 \(g(l,r)=\frac{l*(l-1)}{2}+\frac{(n-r)*(n-r+1)}{2}+\frac{(r-l+1)*(r-l+2)}{2}\) 表示无用操作数

则有：

\[ans[i]=\sum_{i\in[l,r]}\sum_{v}(f[v][p][l][r]-f[v-1][p][l][r])*val[v]
\]

拆开，有：

\[ans[i]=\sum_{i\in[l,r]}\sum_{v}f[v][p][l][r]*val[v]-\sum_{i\in[l,r]}\sum_{v}f[v-1][p][l][r]*val[v]
\\

=\sum_{i\in[l,r]}\sum_{v}f[v][p][l][r]*(val[v]-val[v+1])
\]

因此，可以直接设 \(dp[i][l][r]=\sum_{v}f[v][i][l][r]\)

转移方程：

\[pre(i,j)=\sum_{t=1}^{j}dp[i][t][r]*(t-1)
\\
suf(i,j)=\sum_{t=j}^{n}dp[i][l][t]*(n-t)
\\
dp[i][l][r]=dp[i-1][l][r]*g(l,r)+pre(i-1,l-1)+suf(i-1,r+1)

\]

进而时间复杂度 \(O(n^4)->O(n^3)\)

点击查看代码

#include<bits/stdc++.h>
using namespace std;
int n,q;
int a[405];
long long dp[2][405][405],pre[405][405],suf[405][405];
long long g[405][405],ans[405];
const long long md=1e9+7;
int main(){
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    a[0]=a[n+1]=1e9;
    for(int l=1;l<=n;l++){
        int mx=a[l];
        for(int r=l;r<=n;r++){
            mx=max(mx,a[r]);
            if(mx<=a[l-1]&&mx<=a[r+1])dp[0][l][r]=(mx-(l==1&&r==n?0:min(a[l-1],a[r+1])))%md;
            g[l][r]=(l*(l-1)/2+(n-r)*(n-r+1)/2+(r-l+1)*(r-l+2)/2)%md;
        }
    }
    for(int t=1;t<=q;t++){
        int lst=((t-1)&1),nxt=(t&1);
        for(int r=1;r<=n;r++){
            for(int i=1;i<=r;i++)pre[i][r]=(pre[i-1][r]+dp[lst][i][r]*(i-1))%md;
        }
        for(int l=1;l<=n;l++){
            for(int i=n;i>=l;i--)suf[l][i]=(suf[l][i+1]+dp[lst][l][i]*(n-i))%md;
        }
        for(int l=1;l<=n;l++){
            for(int r=l;r<=n;r++){
                dp[nxt][l][r]=(dp[lst][l][r]*g[l][r]+pre[l-1][r]+suf[l][r+1])%md;
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int l=1;l<=i;l++){
            for(int r=i;r<=n;r++)ans[i]=(ans[i]+dp[q&1][l][r])%md;
        }
    }
    for(int i=1;i<=n;i++)printf("%lld ",(ans[i]+md)%md);

    return 0;
} 

星际旅行

点击查看代码

创造题目

点击查看代码

后宫

点击查看代码

分组

点击查看代码

攻城机变

点击查看代码

基因改造问题

拼接 \(SAM\) 即可

点击查看代码

#include<bits/stdc++.h>
using namespace std;
int T;
int rt,cnt,lst,son[26][2000005],l[2000005],fa[2000005];
inline void insert(int c){
    int i=lst,x=++cnt;l[x]=l[lst]+1;lst=x;
    while(i&&!son[c][i])son[c][i]=x,i=fa[i];
    if(!i)fa[x]=rt;
    else{
        int j=son[c][i];
        if(l[i]+1==l[j])fa[x]=j;
        else {
            int e=++cnt;l[e]=l[i]+1;
            for(int t=0;t<26;t++)son[t][e]=son[t][j];
            fa[e]=fa[j];fa[x]=fa[j]=e;
            while(i&&son[c][i]==j)son[c][i]=e,i=fa[i];
        }
    }
}
char s[2000005];
int pre,ed,ans,op;
bool vis[2000005];
void dfs1(int x){
    if(op)printf("%s\n",s+1);ans++;
    bool is=0;
    for(int i=0;i<26;i++){
        if(!son[i][x])continue;
        s[++ed]=i+'A';
        dfs1(son[i][x]);
        s[ed--]=0;
    }
}
long long dp[2000005];
const long long md=1e9+7;
void dfs2(int x){
    if(dp[x])return ;dp[x]=1;
    for(int i=0;i<26;i++){
        if(!son[i][x])continue;
        dfs2(son[i][x]);
        dp[x]=(dp[x]+dp[son[i][x]])%md;
    }ans=dp[x];
}
int main(){
    scanf("%d",&T);
    for(int t=1;t<=T;t++){
        scanf("%s",s+1);
        int n=strlen(s+1);rt=++cnt;lst=cnt;vis[cnt]=1;
        for(int i=1;i<=n;i++)insert(s[i]-'A');
    }
    for(int i=cnt;i;i--){
        for(int j=0;j<26;j++)if(!son[j][i])son[j][i]=son[j][pre];
        if(vis[i])pre=i;
    }
    memset(s,0,sizeof(s));
    scanf("%d",&op);
    if(op)dfs1(1);else dfs2(1);
    printf("%d",ans);

    return 0;
} 

UR #1 外星人

点击查看代码

庆典

点击查看代码

小猫咪

直接从 \(1\sim n\) 顺次填写 { \(a\) } 的第 \(i\) 位

设 \(dp[i][j][k]\) 表示，已经填完了 \(1\sim i\) 这些位置，并且目前已经确定在 \(1\sim i\) 中位置上的，值在 \(1\sim i\) 的数字有 \(j\) 个，这 \(j\) 个已经被确定的位置上的 \(\max\) 和为 \(k\) 的方案数

转移时枚举 \(i+1\) 这个数值被填到了哪里，以及在最终的排列里 \(i+1\) 这个位置上的值是什么即可

点击查看代码

#include<bits/stdc++.h>
using namespace std;
int n,m;
long long dp[2][55][2505],ans;
const long long md=998244353;
int main(){
    scanf("%d%d",&n,&m);
    dp[0][0][0]=1;
    for(int i=0,u=1;i<n;i++,u^=1){
        for(int j=0;j<=i;j++){
            for(int k=0;k<=i*i;k++){
                long long &t=dp[u^1][j][k];
                if(!t)continue;
                dp[u][j+2][k+2*(i+1)]=(dp[u][j+2][k+2*(i+1)]+1ll*t*(i-j)%md*(i-j)%md)%md;
                dp[u][j+1][k+i+1]=(dp[u][j+1][k+i+1]+1ll*t*(i-j)%md*2%md+t)%md;
                dp[u][j][k]=(dp[u][j][k]+t)%md;t=0;
            }
        }
    }
    for(int i=m;i<=n*n;i++)ans=(ans+dp[n&1][n][i])%md;
    for(int i=1;i<=n;i++)ans=1ll*ans*i%md;
    printf("%lld",ans);

    return 0;
} 

基因改造计划

点击查看代码

```cpp

</details>

### [求余数]()

<details>
<summary>点击查看代码</summary>

```cpp 

摩天大楼

点击查看代码