题解 SP3734 【PERIODNI - Periodni】

· · 题解

SPOJ PERIODNI

不知道公式会不会出问题，建议到 这里 或者 Luogu 博客查看。

仍然考虑类笛卡尔树的 dp，我们把整个直方图画成了很多个矩形。首先考虑一个矩形内部的答案，如果这个矩形 n 行 m 列，并且我们要从中选择 k 个点，方案数量就是，从行选择 k 个，从列选择 k 个，然后再任意组合。考虑任意组合的过程，就是从行的 k 个点分别对应到一个列，也就是排列的数量，所以就是 k! ，于是 n\times m 的矩形选择 k 个点的方案就是：

S(n,m,k) = {n\choose k} {m\choose k} k!

然后考虑设 dp[i][j] 表示 i 这个（笛卡尔树的）节点中选择了 j 个点的方案数量。

怎么转移？我们先抛开这个矩形本身，只考虑 u 所有儿子，设初始状态为 dp[u][0] = 1，然后我们对于每一个儿子 v ，考虑转移 （式子可能边界有点小问题建议以代码为准），注意树形 dp 要逆序枚举。。

dp[u][i] = \sum_{j=1}^i dp[v][j]\times dp[u][i - j]

对于所有儿子分别跑一次之后，当前的 dp[u][i] 就是从 u 的儿子中选择 i 个点的方案数量，然后考虑怎么把这个位置的矩形也选择上，注意要减去已经通过儿子选择过的列，于是再做一次：

dp[u][i] = \sum_{j=1}^i dp[u][j] S(x - (i - j),y,i-j)

其中 x,y 表示这个矩形的长宽。（这几个柿子看起来都好卷积啊。。但是 n \leq 500 就随便做喽）

复杂度，如果笛卡尔树暴力枚举下一层暴力跑树形 dp 都才 O(n^3) 。。那就暴力一点吧。。

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "set"
#include "vector"
#include "map"
#include "cmath"
#define MAXN 506
//#define int long long
using namespace std;
typedef long long ll;
#define P 1000000007

int n , m;

int Pow( int x , int a ) {
    int ans = 1 , cur = x % P;
    while( a ) {
        if( a & 1 ) ans = 1ll * ans * cur % P;
        cur = 1ll * cur * cur % P , a >>= 1;
    }
    return ans;
}
int h[MAXN];
int J[1000006] , invJ[1000006];
int C( int a , int b ) {
    if( a < b ) return 0;
    return 1ll * J[a] * invJ[b] % P * invJ[a - b] % P;
}
int S( int n , int m , int k ) {
    return 1ll * C( n , k ) * C( m , k ) % P * J[k] % P;
}
int dp[506 * 506][506] , cur , k;
int solve( int l , int r , int base ) {
    if( l > r ) return 0;
    int re = 0 , c = ++ cur , L = r - l + 1;
    for( int i = l ; i <= r ; ++ i ) if( !re || h[i] < h[re] ) re = i;
    vector<int> mn;
    mn.push_back( l - 1 );
    for( int i = l ; i <= r ; ++ i ) if( h[i] == h[re] ) mn.push_back( i );
    mn.push_back( r + 1 );
    dp[c][0] = 1;
    for( int i = 1 ; i < mn.size() ; ++ i ) {
        int t = mn[i] , p = mn[i - 1] , l = t - p - 1 , id = solve( p + 1 , t - 1 , h[re] );
        if( id == 0 ) continue;
        for( int j = min( L , k ) ; j >= 0 ; -- j )
            for( int k = 1 ; k <= min( j , l ) ; ++ k )
                ( dp[c][j] += 1ll * dp[id][k] * dp[c][j - k] % P ) %= P;
    }
    int dh = h[re] - base;
    for( int i = min( L , k ) ; i >= 0 ; -- i )
        for( int j = 1 ; j <= min( dh , i ) ; ++ j )
            ( dp[c][i] += 1ll * dp[c][i - j] * S( dh , L - ( i - j ) , j ) % P ) %= P;
    return c;
}

int main() {
    J[0] = 1; invJ[0] = 1;
    for( int i = 1 ; i < 1000006 ; ++ i ) J[i] = 1ll * J[i - 1] * i % P , invJ[i] = Pow( J[i] , P - 2 );
    cin >> n >> k;
    for( int i = 1 ; i <= n ; ++ i ) scanf("%d",h + i);
    int c = solve( 1 , n , 0 );
    cout << dp[c][k] << endl;
}