AGC039（D未做）

C

一次操作相当于将末位取反放到首位，即(2n)次一定可以
考虑(X)，相当于环形(XX')的循环节，由于这个是环形的，相当于无限长度，若经过(d)次回来，则((d,2n))也可以。故(d|2n)
显然(n)次不合法，故(d mid n)

由于(d|2n,d mid n)：(d=2k)，(k|n)，(frac{n}{k}~is~odd)
将(X)分成(frac{n}{k})段，奇段与偶段相等

考虑计算(k|n)，(d=2k)为循环节的个数，但要求的是最小的，所以容斥一下

E

F

做法1
对于A的权值，考虑组合意义：矩阵B，(b_{i,j})小于等于A矩阵第(i)行最小值与第(j)列最小值
令({x})为A每行的最小值，令({y})为B每列的最大值

我们考虑连着({x},{y})一同算进去，按从小到大的顺序加入
考虑我们之前加入了(i)行(x_k< t)，(j)列(x_k< t)
若我们加入(a)行(x_i=t)的，A中已经确定的列可以填(ge t)，且至少有一个(t)。B中未确定的列填(le t)
加入(a)列(y_i=t)的类似

做法2
令({x},{y})为行/列最小值。权值为(prod_{i,j}min(x_i,y_i))
考虑算方案数，我们不算恰好为最小值，算大于等于最小值，方案数为(prod_{i,j}(K+1-min(x_i,y_i)))

我们考虑连着({x},{y})一同算进去，按从小到大的顺序加入
考虑我们之前加入了(i)行(x_k< t)，(j)列(x_k< t)，若我们加入(a)行(x_i=t)的，权值乘上(t^{aj})，方案数乘上((K+1-t)^{a(M-j)})，还要乘上({n-ichoose a})
列同理

当然还要容斥，乘上系数即可