好牛的计数题。
题目链接。
题意
给定一个 的矩阵，第
行第 列的元素是 ，不同位置可能有相同的元素。
现在可以进行任意次操作，若选择对第 行操作，会先把所有第
行所有偶数列的元素按顺序拿出来，然后再按顺序放在第 行最后面。
对第
列操作类似。问最后能换出多少种不同的矩阵。
。
题解
这题的具体操作其实不影响做法，不妨将对行操作看为，将整行乘上一个输入的置换；对列操作相同。
容易发现，我们重新排布一下各个行的位置（与输入的置换），是不影响答案的。
那我们不妨，把同一个置换环中的行，连续排布在一起；对列进行相同的操作。
这样就可以认为，我们把行与列都连续的分为了若干组，一次对行的操作，相当于是行内处于同一组的元素，做一个循环位移。
首先考虑，若所有行分成的组中，有一组大小为 的情况。
这个时候无论对哪一列进行操作，都不会影响到这一行的元素，所以这部分相对于外面是独立的，贡献可以单独计算。
由于我们能做的只有同时对所有列组进行循环位移，所以这部分其实就是，所有列组的最小循环节的最小公倍数。
而最小循环节跑一遍 kmp 就能算出来。这里的贡献容易在
复杂度内进行计算。存在某一个列组大小为 的情况类似。
现在我们就只需要考虑所有行和列形成的组大小都 的情况。
称某一个行组与某一个列组对应的所有格子为一个“盘面”，若盘面所有元素都互不相同，则称这个盘面是“互异盘面”，否则为“非互异盘面”。
首先可以发现，一个盘面内的元素永远都不会交换到盘面外头去。
然后可以发现，一个盘面可以在不改变其他盘面的情况下，完成某三个元素的三轮换。
这就说明，对于非互异盘面，可以在不改变其他盘面的情况下，得到所有状态，对于互异盘面，可以在不改变其他盘面的情况下，得到所有奇偶性相同的状态。
那么非互异盘面的问题直接就解决了，只需要考虑互异盘面的情况。
又可以发现，如果有一个盘面，他的长和宽都是奇数，那么无论怎么位移，奇偶性都没有办法改变。
对于某一个大小为奇数的行组，显然对行做操作，只会影响到那些大小为偶数的列组，而影响到的对应盘面，只会被行操作影响，所以这部分贡献，每一个行组是
。
大小为奇数的列组贡献类似。
那么现在就只需要考虑长和宽均为偶数的互异盘面了。
将行组与列组都看作点，一个互异盘面当作边。
可以发现总方案数其实就是
的生成树边数次方，因为对于每一个环来说，状态的异或和总是 。
这样就解决了最后一部分的贡献。
时间复杂度可以做到单组 。
代码
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
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
| #include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define debug(x) cerr<<#x<<"="<<x<<endl
using namespace std;
using ll=long long;
using ld=long double;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
inline int read()
{
int s=0,w=1;char ch;
while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
inline ll lread()
{
ll s=0,w=1;char ch;
while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
const int mod=998244353;
bool vis1[1000005];
bool vis2[1000005];
ll jc[3000005];
ll inv[3000005];
int pri[3000005];
int is[3000005];
int wtf[3000005];
int fa[2000005];
vc<int>a[1000005];
vc<int>w1[1000005];
vc<int>w2[1000005];
bool v[1000005];
int p[1000005];
int s[1000005];
int nx[1000005];
int n,m,c1,c2;
vc<int>now;
inline ll qow(ll a,ll b)
{
ll ans=1;
while(b)
{
if(b&1) ans=ans*a%mod;
a=a*a%mod;
b>>=1;
}
return ans;
}
inline void init(int L)
{
for(int i=2;i<=L;i++)
{
if(!is[i]) pri[++pri[0]]=i;
for(int j=1;j<=pri[0]&&i*pri[j]<=L;j++)
{
is[i*pri[j]]=1;
if(i%pri[j]==0) break;
}
}
for(int i=1;i<=pri[0];i++)
{
ll now=pri[i];
while(now<=L) wtf[now]=pri[i],now*=pri[i];
}
memset(is,0,sizeof(is));
jc[0]=1;
for(int i=1;i<=L;i++) jc[i]=jc[i-1]*i%mod;
inv[L]=qow(jc[L],mod-2);
for(int i=L;i;i--) inv[i-1]=inv[i]*i%mod;
for(int i=1;i<=L;i++) inv[i]=jc[i-1]*inv[i]%mod;
}
inline int run(int len)
{
for(int i=2,j=0;i<=len;i++)
{
while(j&&s[j+1]!=s[i]) j=nx[j];
if(s[j+1]==s[i]) j++;
nx[i]=j;
}
int ans=len;
while(nx[len])
{
if(len%(len-nx[len])==0) ans=min(ans,len-nx[len]);
nx[len]=nx[nx[len]];
}
return ans;
}
inline ll push(int v)
{
ll ans=1;
for(int i=1;i<=v;i++) if(v%i==0&&wtf[i]&&!is[i])
{
ans=ans*wtf[i]%mod,is[i]=1;
now.push_back(i);
}
return ans;
}
inline void clear()
{
for(int i:now) is[i]=0;
now.clear();
}
inline int find(int num)
{
if(fa[num]==num) return num;
return fa[num]=find(fa[num]);
}
inline ll get(int x,int y,bool &f)
{
f=0;ll ans=1;int cnt=0;
for(int i:w1[x]) for(int j:w2[y])
{
cnt++,ans=ans*cnt%mod;
if(is[a[i][j]]) f=1;
is[a[i][j]]++,ans=ans*inv[is[a[i][j]]]%mod;
}
for(int i:w1[x]) for(int j:w2[y]) is[a[i][j]]=0;
return ans;
}
int main()
{
int T=read();init(3000000);
while(T--)
{
n=read(),m=read(),c1=c2=0;
for(int i=1;i<=n;i++)
{
a[i].resize(m+1);
for(int j=1;j<=m;j++) a[i][j]=read();
}
for(int i=1;i<=n;i++) p[i]=(i&1)?(i/2+1):((n+i+1)/2),v[i]=0;
for(int i=1;i<=n;i++) if(!v[i])
{
c1++;w1[c1].clear();vis1[c1]=0;
for(int j=i;!v[j];j=p[j]) w1[c1].push_back(j),v[j]=1;
}
for(int i=1;i<=m;i++) p[i]=(i&1)?(i/2+1):((m+i+1)/2),v[i]=0;
for(int i=1;i<=m;i++) if(!v[i])
{
c2++;w2[c2].clear();vis2[c2]=0;
for(int j=i;!v[j];j=p[j]) w2[c2].push_back(j),v[j]=1;
}
for(int i=1;i<=c1+c2;i++) fa[i]=i;
ll ans=1;
for(int i=1;i<=c1;i++) if(w1[i].size()==1)
{
for(int j=1;j<=c2;j++)
{
int len=0;
for(int p:w2[j]) s[++len]=a[w1[i][0]][p];
ans=ans*push(run(len))%mod;
}
clear();
}
for(int i=1;i<=c2;i++) if(w2[i].size()==1)
{
for(int j=1;j<=c1;j++)
{
int len=0;
for(int p:w1[j]) s[++len]=a[p][w2[i][0]];
ans=ans*push(run(len))%mod;
}
clear();
}
for(int i=1;i<=c1;i++) for(int j=1;j<=c2;j++)
{
if(w1[i].size()==1||w2[j].size()==1) continue;
bool f;ll val=get(i,j,f);
if(f) ans=ans*val%mod;
else
{
ans=ans*val%mod*inv[2]%mod;
if(w1[i].size()%2==0&&w2[j].size()%2==0)
{
int u=find(i),v=find(c1+j);
if(u!=v) ans=ans*2%mod,fa[u]=v;
}
else if(w1[i].size()%2==0)
{
if(!vis2[j]) vis2[j]=1,ans=ans*2%mod;
}
else if(w2[j].size()%2==0)
{
if(!vis1[i]) vis1[i]=1,ans=ans*2%mod;
}
}
}
printf("%lld\n",ans);
}
return 0;
}
|