problem

luogu-P4099

solution

兩篇前提題解：排列計數，老C的鍵盤

想必已經看了 CQOI2017 老C的鍵盤 一題題解了。

這里直接考慮優化狀態轉移方程。

我們發現 $f(u,i),f(v,j)$，當枚舉 $j$ 后，對應的 $k$ 是一段連續區間。

$f(u,i)?f(v,j)?\left(\genfrac{}{}{0ex}{}{k?1}{i?1}\right)?\left(\genfrac{}{}{0ex}{}{si{z}_u+si{z}_v?k}{si{z}_u?i}\right)$ 轉移貢獻變化的只有 $k$，且有兩項都與之掛鉤。

我們不妨反過來固定 $k$，能轉移到這個 $k$ 的肯定也是一段連續的 $j$。

所以我們求出來 $f(v,j)$ 后，直接做個前綴和，$f(v,j)={\sum }_{j^{\prime }\le j}f(v,j^{\prime })$。

以要求 $h_u<h_v$ 為例。

其原來是 $i+j\le k\le i+si{z}_v$，固定 $i,k$ 后，能轉移過來的 $j$ 范圍則為 $1～k?i$。

另一種則是 $k?i<j\le si{z}_v$。

兩種的 $k$ 范圍也稍稍不同。

具體可以看代碼實現。

code

#include <bits/stdc++.h> using namespace std; #define int long long #define mod 1000000007 #define maxn 1005 char s[5]; int n; int c[maxn][maxn], f[maxn][maxn], g[maxn], siz[maxn]; vector < pair < int, int > > G[maxn];void dfs( int u, int fa ) {f[u][1] = siz[u] = 1;for( int i = 0;i < G[u].size();i ++ ) {int v = G[u][i].first, w = G[u][i].second;if( v == fa ) continue;dfs( v, u );memcpy( g, f[u], sizeof( f[u] ) );memset( f[u], 0, sizeof( f[u] ) );for( int i = 1;i <= siz[u];i ++ )if( w ) {for( int k = i + 1;k <= i + siz[v];k ++ )(f[u][k] += f[v][k - i] % mod * g[i] % mod * c[k - 1][i - 1] % mod * c[siz[u] + siz[v] - k][siz[u] - i]) %= mod;}else {for( int k = i;k < i + siz[v];k ++ )(f[u][k] += (f[v][siz[v]] - f[v][k - i]) % mod * g[i] % mod * c[k - 1][i - 1] % mod * c[siz[u] + siz[v] - k][siz[u] - i]) %= mod;}siz[u] += siz[v];}for( int i = 1;i <= siz[u];i ++ ) (f[u][i] += f[u][i - 1]) %= mod; }signed main() {for( int i = 0;i <= 1000;i ++ ) {c[i][0] = c[i][i] = 1;for( int j = 1;j < i;j ++ )c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;}int T;scanf( "%lld", &T );while( T -- ) {scanf( "%lld", &n );memset( f, 0, sizeof( f ) );for( int i = 0;i < n;i ++ ) G[i].clear();for( int i = 1, u, v;i < n;i ++ ) {scanf( "%lld %s %lld", &u, s, &v );G[u].push_back( make_pair( v, s[0] == '<' ) );G[v].push_back( make_pair( u, s[0] == '>' ) );}dfs( 0, 0 );printf( "%lld\n", ( f[0][n] + mod ) % mod );}return 0; }

總結

以上是生活随笔為你收集整理的[HEOI2013] SAO（dp + 组合数 + 前缀和）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。