P11173 题解

没看懂出题人想表达什么，但是按照我的做法这没黑吧/jk

显然，问题等价于求所有 n 个点的 DAG 最长链乘上 x^c 的和，其中 c 为边数。

先弱化，算方案数。

考虑分层，设 dp_{i,j} 表示目前考虑了 i 个点，最前面一层有 j 个点的方案数。

转移考虑枚举新的一层的点数 k，dp_{i,j}\times(x^i-x^{i-j})^k\to dp_{i+k,k}。也就是说，新的一层的每个点必须被一个前一层的点连向，其余随意。

考虑上最长链长度。

设 dp_{i,j,0/1} 表示目前考虑了 i 个点，最前面一层有 j 个点的方案数和所有方案数目前链长之和。有转移：

最后答案就是 \sum_{j=1}^ndp_{n,j,1}。总复杂度 O(n^3)。

为什么 n^3 开 600？因为 1000 太大了。

#include <bits/stdc++.h>
#define int unsigned long long
#define double long double
#define mid ((l+r)>>1)
#define lowbit(i) (i&(-i))
using namespace std;
const int mod=202407031;
int dp[605][605][2],C[605][605],pw[605];
int f[605][2],g[605][2];
signed main(){
    for(int i=0;i<=600;i++) C[i][0]=1;
    for(int i=1;i<=600;i++) for(int j=1;j<=i;j++) C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
    int n,a; cin>>n>>a; a%=mod;
    pw[0]=1; for(int i=1;i<=600;i++) pw[i]=pw[i-1]*a%mod;
    for(int i=1;i<=n;i++) dp[i][i][0]=dp[i][i][1]=1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++){
            int mul=(pw[i]+mod-pw[i-j])%mod,tr=1;
            for(int k=1;i+k<=n;k++){
                (tr*=mul)%=mod;
                int tmptr=tr*C[i+k][k]%mod;
                (dp[i+k][k][0]+=dp[i][j][0]*tmptr)%=mod;
                (dp[i+k][k][1]+=(dp[i][j][0]+dp[i][j][1])*tmptr)%=mod;
            }
        }
    }
    for(int i=1;i<=n;i++) for(int j=1;j<=i;j++) (g[i][0]+=dp[i][j][0])%=mod,(g[i][1]+=dp[i][j][1])%=mod;
    cout<<g[n][1];
    return 0;
}