AGC 005 D - ~K Perm Counting

时间：2022-02-19 16:55:20

D - ~K Perm Counting

链接

题意：

　　求有多少排列对于每个位置i都满足$|ai−i|!=k$。n<=2000

分析：

　　容斥+dp。

　　$answer = \sum\limits_{i = 0}^{n}(-1)^ig[i] \times (n - i)!$

　　$g[i]$表示至少存在I个位置满足$a[i] - i = k$个数。

　　考虑如何求出$g[]$。 如果建立两列点，一个表示数字，一个表示下标，左边第i个点与右边第i-k和i+k个点连边，那么这是一张二分图，g[i]就是求满足有刚好i个匹配的方案数。

　　发现这样图可以按照模k的余数分成2k条链，每条链互不影响，链内满足不能有相邻的一起选。于是可以$f[i][j][0]$表示到链上的第i个位置，当前有j个匹配，第i个选不选的方案数。

　　考虑如何将2k条链合并：因为链与链之间是互不影响的，所以可以建立一个点，连接两条链，然后让这个点一定不选即可。

代码：

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<iostream>

#include<cmath>

#include<cctype>

#include<set>

#include<queue>

#include<vector>

#include<map>

using namespace std;

typedef long long LL;

inline int read() {

    int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;

    for(;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;

}

const int N = , mod = ;

int f[N][N][], g[N], A[N], fac[N];

inline void add(int &x,int y) { x += y; if (x >= mod) x -= y; }

int main() {

    int n = read(), k = read(), Ans = ;

    int cnt = ;

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

        for (int j = i; j <= n; j += k) A[++cnt] = (i == j);

        for (int j = i; j <= n; j += k) A[++cnt] = (i == j);

    }

    f[][][] = ;

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

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

            add(f[i][j][], (f[i - ][j][] + f[i - ][j][]) % mod);

            if (!A[i] && j) add(f[i][j][], f[i - ][j - ][]);

        }

    fac[] = ;

    for (int i = ; i <= n; ++i) fac[i] = 1ll * fac[i - ] * i % mod;

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

        int res = (f[n << ][i][] + f[n << ][i][]) % mod;

        Ans += 1ll * (i &  ? - : ) * res * fac[n - i] % mod;

        Ans = (Ans % mod + mod) % mod;

    }

    cout << Ans;

    return ;

}

相关文章