2019.03.27【GDOI2019】模擬 T3

題目大意

給出$n$, $p$, 求有多少長度為$n$的排列可以被分成三個上升子序列, 數量對$p$取模,

數據范圍 $3 \leq n \leq 500$.

思路

首先讓我們考慮如果有一個排列,如何判斷這個排列合法,我可以考慮貪心,維護三個上升序列的末尾(最大值),從左到右依次將數插入序列,把這個數貪心的加到它可以加入的末尾的數最大的序列里.

因此考慮dp,定義$f[i][j][k]$表示現在有$i$個數,形成了三個上升子序列,其中最大的子序列末尾顯然是第$i$大的數,第二大的子序列末尾是第$j$大的數,第三大的子序列末尾是第$k$大的數,這樣的序列的數量,顯然,這樣枚舉是不會重復的,轉移的時候,考慮在這個序列末尾加數,考慮加的這個數在這$i$個數中的相對位置,設這個位置為$l$,有
$$
f[i][j][k] \rightarrow f[i+1][j][k],l=i+1 \\
f[i][j][k] \rightarrow f[i+1][l][k],j < l \leq i \\
f[i][j][k] \rightarrow f[i+1][j+1][l], k < l \leq j
$$
一個簡單的$O(n^4)$dp

#define add(x, y) x = (x + y >= md) ? x + y - md : x + y
f[1][0][0] = 1;
for (int i = 1; i < n; ++i)for (int j = 0; j < i; ++j)for (int k = 0; k <= j; ++k)if (f[i][j][k] > 0) {int x = f[i][j][k];for (int l = k + 1; l <= j; ++l)add(f[i + 1][j + 1][l], x);for (int l = j + 1; l <= i; ++l)add(f[i + 1][l][k], x);add(f[i + 1][j][k], x);}

考慮優化,發現轉移的都是一段,隨便前綴和搞一搞就可以了

#define add(x, y) x = (x + y >= md) ? x + y - md : x + y
#define sub(x, y) x = (x - y < 0) ? x - y + md : x - y
f[1][0][0] = 1;
for (int i = 1; i < n; ++i) {int cur = i & 1, nxt = cur ^ 1;memset(f[nxt], 0, sizeof(f[nxt]));memset(tag1, 0, sizeof(tag1));memset(tag2, 0, sizeof(tag2));for (int j = 0; j < i; ++j)for (int k = 0; k <= j; ++k) if (f[cur][j][k] > 0) {int x = f[cur][j][k];add(tag1[j + 1][k + 1], x);sub(tag1[j + 1][j + 1], x);add(tag2[j + 1][k], x);sub(tag2[i + 1][k], x);add(f[nxt][j][k], x);}for (int j = 0; j <= i; ++j)for (int k = 1; k <= i; ++k)add(tag1[j][k], tag1[j][k - 1]), add(tag2[k][j], tag2[k - 1][j]);for (int j = 0; j <= i; ++j)for (int k = 0; k <= j; ++k) {add(f[nxt][j][k], tag1[j][k]);add(f[nxt][j][k], tag2[j][k]);} 
}

復雜度$O(n^3)$.