AT_abc309_g 题解

tsqtsqtsq0309 · 2023-08-29 09:00:12 · 题解

AT_abc309_g [ABC309G] Ban Permutation

题目大意

求长为 N(N\leq 100) 且满足以下条件的排列 P=(P_1,P_2,\cdots,P_N) 的个数：

思路

第一眼看到这一题就知道不能够直接求（废话）。

看到大于等于一眼想到容斥和状压。可以考虑将问题转化一下，钦定 j 个位置满足条件 |P_i-i|\le X。

具体地说，令 f_{i,j,s} 表示前 i 个位置中有 j 个位置满足条件 |P_i-i|\le X，目前不合法区域选择状态为 s，转移的时候讨论是否满足条件即可，还有一车细节需要注意。除了这 i 个位置以外其余的位置都可以随便排，所以还需要乘上 fac_{n-i} 才行。

综上所述，易知答案为：

\sum^{n}_{i=0}\sum_s\times(-1)^i\times(n-i)!

总的时间复杂度为 O(n^24^XX)，应该是可以过的吧……

记得开 long long

在这里祭了不知道多久……

代码

#include <iostream>
#define int long long
#define MAXN 105
#define MAXX 15
#define mod 998244353
using namespace std;
int n, x, t, ans;
int f[MAXN][MAXN][MAXX * MAXN], fac[MAXN];
signed main(){
    cin >> n >> x;fac[0] = 1;
    for(int i = 1 ; i <= n ; i ++)
        fac[i] = fac[i - 1] * i % mod;
    x--;
    f[0][0][0] = 1;
    for(int i = 1 ; i <= n ; i ++){
        for(int j = 0 ; j < i ; j ++){
            for(int s = 0 ; s < (1 << ((x << 1) + 1)) ; s ++){
                if (!f[i - 1][j][s])continue;t = (s >> 1);
                f[i][j][t] += f[i - 1][j][s];f[i][j][t] %= mod;
                for(int k = 0 ; k <= (x << 1) ; k ++){
                    if ((~t) & (1 << k)){
                        if (i + k - x < 1 || i + k - x > n)continue;
                        f[i][j + 1][t | (1 << k)] += f[i - 1][j][s];
                        f[i][j + 1][t | (1 << k)] %= mod;
                    }
                }
            }
        }
    }
    for(int i = 0 ; i <= n ; i ++){
        for(int s = 0 ; s < (1 << (x * 2 + 1)); s ++){
            t = (i & 1) ? (mod - f[n][i][s]) : f[n][i][s];
            ans = (ans + t * fac[n - i] % mod) % mod;
        }
    }
    cout << ans << endl;
    return 0;
}