【WC模拟】Arrangement

Description

由于題面太過鬼畜就直接貼圖了~

n,m,k<=100

Solution

橋豆麻袋，讓我先笑一會先。

原來還可以這樣出題，漲姿勢了。

話說第一張圖真的不是紅衣男孩

活着還是很吼的

回歸正題，我們考慮要怎麼計算b序列的a排列的數量。

那麼它重排過後的上升次數和下降次數都是一樣的。

為了友善我們強制把b排列的末尾加上一個b1.

比如 b1,b2,b1是一個合法的排列。

那麼我們可以看出來b1,b2,b2,b1是不合法的，但是我們隻需要在兩個b2之間插入一個b3它就會變成合法的。

那麼我們設狀态Fi,j,k,l表示目前已經把前i個數放完了，放了j個數，有k個空位，排列方案為l的方案數。

那麼我們枚舉下一個數填多少個，轉移隻需要把l乘上一個組合數就可以得到新序列的a排列的數量。

而且因為k很小，是以這樣的轉移不是特别多，常數很小，是能過去的。

Code

#include <cstdio>
#include <cstring>
#include <algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
typedef long long ll;
const int N=,mo=+;
int n,m,K,ans,p,q,f[][N][N][N],c[N][N];
int main() {
    freopen("arrangement.in","r",stdin);
    freopen("arrangement.out","w",stdout);
    scanf("%d%d%d",&n,&m,&K);
    c[][]=;
    fo(i,,n) {
        c[i][]=;
        fo(j,,i) c[i][j]=min(K+,c[i-][j]+c[i-][j-]);
    }
    fo(i,,n+) f[][i][i-][]=;
    int p=,q=;
    fo(i,,m) {
        memset(f[q],,sizeof(f[q]));
        fo(j,,n+)
            fo(k,,j)
                fo(l,,K) 
                    if (f[p][j][k][l]) {
                        fo(x,k,n+-j) {
                            int y=l*c[x-][k-];
                            if (y<||y>K) continue;
                            (f[q][j+x][x-k][y]+=f[p][j][k][l])%=mo;
                        }
                    }
        fo(j,,n+) fo(l,,K) (ans+=(ll)f[p][j][][l]*(m-i+)%mo)%=mo;
        p=-p;q=-q;
    }
    printf("%d\n",ans);
    return ;
}