Problem Statement
There are an integer $N$ and $M$ pairs of integers: $(a_1, b_1), (a_2, b_2), \dots, (a_M, b_M)$. Each pair $(a_i, b_i)$ satisfies $1 \leq a_i \lt b_i \leq N$.
Initally, you have all $N!$ permutations of $(1,2,\dots,N)$.
You will perform $M$ operations. The $i$-th operation is as follows.
- Do the following for each of your $N!$ permutations.
- Compare the $a_i$-th and $b_i$-th elements. If the former is greater, swap the two elements.
For each $1 \leq i \leq M$, let $S_i$ be the number of permutations of yours that are already sorted in ascending order at the end of the $i$-th operation.
Print $S_1, S_2, \dots, S_M$.
Here, the input gives you pairs of integers $(x_i, y_i)$ instead of $(a_i, b_i)$.
The values of $(a_i, b_i)$ can be obtained using $x_i$, $y_i$, and $S_{i-1}$ as follows. (Let $S_0 = 1$ for convenience.)
- Let $c_i = ((x_i + S_{i-1}) \bmod N) + 1$.
- Let $d_i = ((y_i + S_{i-1} \times 2) \bmod N) + 1$. (Here, it is guaranteed that $c_i \neq d_i$.)
- Let $a_i = \min(c_i, d_i)$.
- Let $b_i = \max(c_i, d_i)$.
Constraints
- $2 \leq N \leq 15$
- $1 \leq M \leq 5 \times 10^5$
- $1 \leq a_i \lt b_i \leq N$
- $0 \leq x_i, y_i \leq N - 1$
Input
The input is given from Standard Input in the following format:
$N$ $M$ $x_1$ $y_1$ $x_2$ $y_2$ $\vdots$ $x_M$ $y_M$
Output
Print $M$ lines. The $i$-th line should contain $S_i$.
Sample Input 1
2 1 1 1
Sample Output 1
2
You start with the permutations $(1, 2)$ and $(2, 1)$.
We have $(a_1, b_1) = (1, 2)$. At the end of the first operation, you have two copies of $(1, 2)$, so you should print $2$.
Sample Input 2
3 4 0 1 2 1 1 1 0 1
Sample Output 2
2 4 4 6
$(a_i, b_i)$ in order are $(1, 2), (2, 3), (1, 3), (1, 2)$.
Sample Input 3
5 5 4 4 0 4 1 1 2 4 1 2
Sample Output 3
2 4 4 8 16
$(a_i, b_i)$ in order are $(1, 2), (3, 4), (1, 5), (2, 3), (4, 5)$.
一道妙妙题。
（据说是一个套路）发现其实我们整个过程中只关心大小关系，但是又要去统计。我们把一个排列压成 \(n\) 个二进制数，第 \(i\) 个二进制数第 \(j\) 位表示 \(p_j\) 是否大于 \(i\)
这样子看起来很废话，但是仔细观察会发现，在进行题目中的交换操作后，有些二进制数会从不合法变成合法，而如果我们已经知道了那些二进制数是合法的，那么可以进行一个 \(O(2^n\times n)\) 的dp去统计答案。定义 \(dp_{S}\) 为目前到达二进制数 \(S\) 时的答案，枚举数字 \(popcount(S)+1\) 放在了哪里，转移易得。那么最终答案就是 \(dp_{2^n-1}\)
如果我们知道现在那个二进制数从不合法变成了合法，怎么更新 dp 值。由于每个二进制数最多只会进行这样一次过程，所以我们可以使用暴力重构的方式。如果 \(S\) 从不合法成为合法，那么只有 \(S\) 的超集会发生变化，对他们进行暴力重构即可。超集枚举加dp总复杂度 \(O(3^nn)\)
现在剩下的问题就是如何知道每次二进制数改完，有那些二进制数发生了变化。一个二进制数最多会被交换 \(O(n^2)\) 次，所以也是考虑维护所有的可以变换的二进制数，然后给他们暴力交换，暴力判断。维护 \(n^2\) 个队列 \(q[x][y]\)，表示把 \(x\) 和 \(y\) 交换了后会有更新的二进制数，而二进制数交换完之后，把所有新增加的 \((x,y)\) ，加入队列。这样子每个二进制数最多会被交换 \(O(n^2)\) 次，而每次交换最多会新增 \(O(n)\) 个数对，他最多会被加入队列 \(O(n^3)\) 次，所以这里复杂度 \(O(n^32^n)\)
#include<bits/stdc++.h>
using namespace std;
const int N=15,P=998244353;
int n,m,x,y,st[1<<N],S,v[1<<N],q[N][N][(1<<N)*N],ll[N][N],rr[N][N],to[1<<N],is[1<<N];
long long dp[1<<N],ls=1;
void getnew(int s)
{
dp[s]=0;
for(int i=0;i<n;i++)
if(s>>i&1)
dp[s]+=dp[s^(1<<i)];
}
void ins(int s)
{
if(v[s])
return;
// printf("%d\n",s);
v[s]=1;
int tp=0;
for(int i=S-s;i;i=(i-1)&(S-s))
if(v[S-i])
st[++tp]=S-i;
st[++tp]=S;
for(int i=1;i<=tp;i++)
getnew(st[i]);
}
void newdot(int s,int x)
{
if(is[to[s]])
ins(s);
for(int j=0;j<x;j++)
if(!(to[s]>>j&1))
q[j][x][++rr[j][x]]=s;
}
void newnode(int s,int x)
{
for(int j=x+1;j<n;j++)
if((to[s]>>j&1))
q[x][j][++rr[x][j]]=s;
}
int main()
{
scanf("%d%d",&n,&m);
S=(1<<n)-1;
v[0]=dp[0]=is[0]=1;
for(int i=1;i<=n;i++)
ins((1<<i)-1),is[(1<<i)-1]=1;
for(int i=0;i<=S;i++)
{
to[i]=i;
for(int j=0;j<n;j++)
if(i>>j&1)
newdot(i,j);
}
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
x=(x+ls)%n;
y=(y+ls*2)%n;
if(x>y)
swap(x,y);
for(int i=ll[x][y]+1;i<=rr[x][y];i++)
{
int s=to[q[x][y][i]];
if(!(s>>x&1)&&(s>>y&1))
{
to[q[x][y][i]]^=(1<<x)^(1<<y);
newdot(q[x][y][i],x);
newnode(q[x][y][i],y);
}
}
ll[x][y]=rr[x][y];
printf("%lld\n",ls=dp[(1<<n)-1]);
}
}