wave

题意：求有多少个1~n的排列满足：

其中n<=50

解：

贼神的一道题。

如何处理绝对值？

从小到大按顺序放数，可以拆掉绝对值。

如果你放的旁边有个空隙，那么贡献-i，如果旁边有个数，贡献+i

然后你设的是f[i][j][k][s]表示前i个数，有j+1段数(j个间隔)，两端点状态为k(0~2分别表示都没有放数，放了一个，放了两个)，目前贡献为s的方案数。

所以要求的就是f[n][0][2][m]

考虑转移：我们可以把i放在某个间隔里，三种情况。还可以放在两端，4种情况。

 #include <cstdio>

 #include <algorithm>

 typedef long long LL;

 const int N = , MO = 1e9 + , D = ;

 int n;

 LL f[][N][][];

 inline void add(LL &a, const LL &b) {

     a += b;

     while(a >= MO) {

         a -= MO;

     }

     while(a < ) {

         a += MO;

     }

     return;

 }

 int main() {

     freopen("wave.in", "r", stdin);

     freopen("wave.out", "w", stdout);

     int m;

     scanf("%d%d", &n, &m);

     LL ans = ;

     f[][][][D - ] = ; // 1 in mid

     f[][][][D - ] = ; // 1 in edge

     for(int i = ; i < n; i++) {

         for(int j = ; j <= (n + ) >> ; j++) {

             for(int k = ; k < ; k++) {

                 for(int s = ; s < ; s++) {

                     if(!f[i & ][j][k][s]) {

                         continue;

                     }

                     LL t = f[i & ][j][k][s];

                     //printf("%d %d %d %d = %lld\n", i, j, k, s - D, t);

                     // f[i][j][k][s] -> ?

                     if(k < ) { // i+1 in edge

                         add(f[(i + ) & ][j][k + ][s + i + ], t * ( - k)); // merge

                         add(f[(i + ) & ][j][k][s], t * ( - k));             // edge

                         add(f[(i + ) & ][j + ][k + ][s - i - ], t * ( - k)); // end

                         if(j + ( - k) + i < n - ) {

                             add(f[(i + ) & ][j + ][k][s - ((i + ) << )], t * ( - k)); // split

                             //printf("%d %d %d %d %d \n", i + 1, j + 1, k, s - ((i + 1) << 1) - D, f[i + 1][j + 1][k][s - ((i + 1) << 1)]);

                         }

                     }

                     // i+1 in mid

                     if(j) {

                         add(f[(i + ) & ][j][k][s], t * j * ); // edge

                         add(f[(i + ) & ][j - ][k][s + ((i + ) << )], t * j); // merge

                         if(j + ( - k) + i < n - ) { // split

                             add(f[(i + ) & ][j + ][k][s - ((i + ) << )], t * j);

                         }

                     }

                     f[i & ][j][k][s] = ;

                 }

             }

         }

     }

     printf("%lld", f[n & ][][][m + D]);

     return ;

 }

AC代码

空间不够，要滚动。然后每次要清零。当前价值可能为负所以要加一个偏移量。

相同的套路还有相邻的两个数贡献为max/min，几乎一模一样。

巴特西

wave

最新文章

热门文章