21年icpc上海区域赛B题Strange Permutations (容斥+生成函数)

题意： 求给定n的排列P，求满足对于任意i∈[1,n-1]满足$Q_{i+1}\ne P_{Q_i}$的Q排列方案数。（n<=1e5）
Solution: 排列的图意义

\quad 直接看这个式子有点晕，看到排列可以从图意义入手。
我们设P，Q的图意义为：$P_{Q_i}->Q_{i+1}$，当然反过来也一样的（这个意义想了几天，被$i->P_{i+1}$的固有套路给框柱了，意义是可以自定义的）。如果考虑i从1到n的话，连出来肯定是若干环，这个和$i->P_i$的建图意义是一样的。
\quad 乱证一下：因为$P_{Q_i}$是个排列，$Q_{i+1}$也是个排列（先假设Q{n+1}有意义），把两个排列按照$Q_{i+1}$大小排序，就转化成了$i->P_i$。
\quad 然后因为i只从1到n-1，那图是个哈密顿图（哈密顿路径）。因为只有n-1个点有出边，n-1个点有入边，且出入度至多为1，画画图得连出来是个哈密顿图。或者从上面连出来的环意义考虑，首先环是不合法的，因为有环就意味这每个点入出度都为1，显然不对，那还要联通，只能是哈密顿图了。
\quad 说了这么多就想证，图意义是哈密顿图。那问题转化成图上有n条禁边，求合法的哈密顿路径数量。禁边的可以设成(i,Pi)。
\quad 为什么这样设是对的呢，上面证了i->Pi的建图意义和$P_{Q_i}->Q_{i+1}(假设Q_{n+1}的意义是Q_1且Q_1不存在)$等价，那反过来也是等价的。
直观点，我们列出$P_{Q_i}$和$Qi+1$
P:3 4 1 2
Q:1 4 3 2
$P_{Q_i}$:3 2 1 4
$Q_{i+1}$: 4 3 2 ？
根据上面的建图意义，这是合法的。
来组不合法的。
P:3 4 1 2
Q:1 3 4 2
$P_{Q_i}$:3 2 1 4
$Q_{i+1}$:3 4 2 ？
3指向3不合法了，发现用$i->P_i$与这个建图意义的禁边意义是相同的！于是就可以转成n条禁边(i,Pi)。而n条禁边组成了若干环，我们要选的是哈密顿路径，所以不能有环。
\quad 考虑容斥，$f(i)$表示钦定选i条禁边的哈密顿路径数，因为不能有环，所以对于禁边组成的若干环，每个环上的边都不能全取，则$ans={\sum }_{i=0}^{n-1}(-1{)}^i\ast f(i)$(这是二项式反演，但不是没有组合数的容斥系数！容斥系数在后面的多项式计算里体现出来了！所以最外层不用带组合数！！！)。
设每个环多项式为$g(x)={\sum }_{i=0}^{siz-1}C(siz,i)x^i$，其中siz为环大小。
$设F=\prod g_j,f(i)=[x^i]F$,即第i项的系数,F的计算用启发式合并算一下就可以了。
时间复杂度$O(nlo{g}^{2}n)$。
这题难点还是在求解问题的转化上。搞清楚后，很容易。
（因为这题结合别的大佬们的题解理解了好久，把一些自己想错的问题都写了，所以比较长，还有一些证明和理解也是自己瞎想的，如有不对的话，还请读者留言区指正，感谢）

#defien int long long
const int N=1e5+5;
const int mod=998244353;
const double eps=1e-8;
const int MAXL = 60;
int n,k;
int a[N];
std::vector<int> G[N];
const int maxn = 6e6+10;
const int p = 998244353;
int Pow(int x,int d){
    int tans = 1;
    if(d == 0)return 1%p;
    int a = Pow(x,d/2);
    tans = 1ll*a*a%p;
    if(d%2)tans = 1ll*tans*x%p;
    return tans%p;
}
typedef vector<int> Poly;//多项式定义
int F1[maxn],F2[maxn];
int rev[maxn];
void NTT(int * A,int lim,int opt) {
    int i, j, k, m, gn, g, tmp;
    for(int i = 0; i < lim; ++i)rev[i] = (i & 1)*(lim >> 1) + (rev[i >> 1] >> 1);
    for(i = 0; i < lim; ++i)if (rev[i] < i) swap(A[i], A[rev[i]]);
    for(m = 2; m <= lim; m <<= 1) {
        k = m >> 1;
        gn = Pow(3,(p - 1) / m);
        for(i = 0; i < lim; i += m) {
            g = 1;
            for (j = 0; j < k; ++j, g = 1ll * g * gn % p) {
                tmp = 1ll * A[i + j + k] * g % p;
                A[i + j + k] = (A[i + j] - tmp + p) % p;
                A[i + j] = (A[i + j] + tmp) % p;
            }
        }
    }
    if(opt == -1){
        reverse(A+1,A+lim);
        int inv = Pow(lim,p-2);
        for(i = 0; i < lim; ++i) A[i] = 1ll * A[i] * inv % p;
    }
}
Poly operator + ( const Poly &A,const Poly &B){
    int n = A.size() , m = B.size();
    int siz = max(n,m);
    Poly C(siz,0);
    for(int i=0 ;i<siz ;i++){
        if( i <n && i < m) C[i] = (A[i] + B[i])%p;
        else if( i < n ) C[i] = A[i];
        else C[i] = B[i];
    }
    return C;
}
Poly mul(const Poly & A,const Poly & B){
    int n = A.size(),m = B.size();
    int siz = n + m - 1;
    Poly C(siz);
    if(siz < 64){//小于等于64项直接暴力算
        for(int i = 0;i < n;i++){
            for(int j = 0;j < m;j++)C[i+j] = (C[i+j] + 1LL*A[i]*B[j]%p)%p;
        }
        return C;
    }
    int fsiz = 1;
    while(fsiz <= siz)fsiz <<=1;
    for(int i = 0;i < fsiz;i++)F1[i] = F2[i] = 0;
    for(int i = 0;i < n;i++)F1[i] = A[i];
    for(int i = 0;i < m;i++)F2[i] = B[i];
    NTT(F1,fsiz,1);
    NTT(F2,fsiz,1);
    for(int i = 0;i < fsiz;i++)F1[i] = 1ll*F1[i]*F2[i]%p;
    NTT(F1,fsiz,-1);
    for(int i = 0;i < siz;i++){
        C[i] = F1[i];
    }
    return C;
}
int fac[N],ni_f[N];
ll qsm(int a,int b){
    ll ans=1,tmp=a;
    while( b ) {
        if( b&1 ) ans = ans * tmp%mod;
        tmp = tmp * tmp%mod;
        b>>=1;
    }
    return ans;
}
void ini(){
    int maxn = 1e5;
    fac[0]=1;
    _for(i,1,maxn) fac[i] =  (fac[i-1] * i)%mod;
    ni_f[maxn] = qsm(fac[maxn],mod-2);
    _rep(i,maxn-1,0) ni_f[i] = ni_f[i+1] * (i+1)%mod;
}
ll C(int n,int m){
    if( m==n || m==0 ) return 1;
    if( n < m ) return 0;
    return fac[n] * ni_f[n-m]%mod * ni_f[m]%mod;
}
int vis[N];
int dfs(int x ,int fa){
    vis[x]=1;
    int siz = 1;
    for(int y:G[x]){
        if( y==fa || vis[y]) continue;
        siz += dfs(y,x);
    }
    return siz;
}
vector<int> V;
Poly cal(int l,int r){
    if( l==r ){
        Poly ans(V[l]+1,0);
        _for(i,0,V[l]-1){
            ans[i] = C(V[l],i);
        }
        return ans;
    }
    int mid = (l+r)>>1;
    return mul(cal(l,mid) , cal(mid+1,r));
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif  
    IOS;
    ini();
    cin>>n;
    _for(i,1,n){
        cin>>a[i];
        G[i].push_back(a[i]);
        G[a[i]].push_back(i);
    }
    _for(i,1,n){
        if( !vis[i] ){
            int siz = dfs(i,0);
            V.push_back(siz);
        }
    }
    Poly F = cal(0,V.size()-1);
    int ans = 0;
    for(int i=0 ;i<F.size() ;i++){
        int flag = i&1?-1:1;
        ans = (ans + mod + flag * F[i] * fac[n-i]%mod)%mod;
    }
    cout<<ans<<endl;
    AC; 
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150