题目
首先我要吐槽，这题目就是坑，给那么多无用的信息，我还以为要根据提示才能做出来呢！
算法1
暴力，傻傻地跟着提示，纯暴力(40)分，高斯消元(60)分。
算法2
DP！一个显然的东西是，这个矩阵有很多地方都是(0)，所以我们枚举的许多排列都是无用的。
设(f(i,set))，其中(i)表示计算到排列的第(i)个元素，或者说是到矩阵的第(i)行，(set)是一个集合，表示前一行哪些数字还没选，可知(set)的大小为(2k)（这样我们才能DP嘛）。(f)的值表示当前计算到的行列式的值。
然后转移的时候我们要统计新产生的逆序对，进而判断是否要乘(-1)。
时间复杂度(O(2^{2k}nk))。
算法3
直接DP，不要想什么矩阵。
假设我们DP到了第(i)位，显然有用的信息只有(i-k sim i-1)这(k)个点的连通性。
然后暴力出所有的状态（要最小表示法，只有(52)种状态），搞出它们之间的转移，然后直接矩阵乘法即可。时间复杂度(O(52^3 log n))。
代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <assert.h>
using namespace std;
#ifdef debug
#define ep(...) fprintf(stderr, __VA_ARGS__)
#else
#define ep(...) assert(true)
#endif
typedef long long i64;
const int MAXK = 5;
const int MAXS = 60;
const int MOD = 65521;
const int LOGN = 60;
const int HASHSIZE = 1 << MAXK * 3;
int cntS;
int k;
i64 n;
struct MatrixB {
i64 A[MAXS][MAXS];
i64* operator [] (const int &x) {
return A[x];
}
};
struct MatrixA {
i64 A[MAXS];
i64 &operator [] (const int &x) {
return A[x];
}
};
void multi(MatrixB &A, MatrixB &B, MatrixB &C) {
for (int i = 0; i < cntS; i ++)
for (int j = 0; j < cntS; j ++) {
C[i][j] = 0;
for (int k = 0; k < cntS; k ++)
C[i][j] += A[i][k] * B[k][j];
C[i][j] %= MOD;
}
}
void multi(MatrixA &A, MatrixB &B, MatrixA &C) {
for (int i = 0; i < cntS; i ++) {
C[i] = 0;
for (int j = 0; j < cntS; j ++)
C[i] += B[j][i] * A[j];
C[i] %= MOD;
}
}
MatrixB B[LOGN];
struct Status {
int A[MAXK];
int &operator [] (const int &x) {
return A[x];
}
int transform() {
int ret = 0;
for (int i = k - 1; i >= 0; i --) {
ret <<= 3;
ret |= A[i];
}
return ret;
}
void show() {
#ifdef debug
for (int i = 0; i < k; i ++)
ep("%d ", A[i]);
ep("
");
#endif
}
};
int hash[HASHSIZE];
#define test(s, i) (((s) >> (i)) & 1)
Status transform(int x) {
Status ret;
for (int i = 0; i < k; i ++) {
ret[i] = x & 7;
x >>= 3;
}
return ret;
}
int dfs(int f) {
Status cur = transform(f);
if (hash[f] == -1) {
hash[f] = cntS ++;
int cnt[MAXK];
fill(cnt, cnt + k, 0);
for (int i = 0; i < k; i ++)
cnt[cur[i]] ++;
for (int s = 0; s < 1 << k; s ++) {
int con = 1;
Status nxt = cur;
int in = -1;
if (cnt[0] == 1 && test(s, 0) == 0) continue;
for (int i = 0; i < k; i ++)
if (test(s, i)) {
con *= cnt[i];
if (in == -1) in = i;
else {
for (int j = 0; j < k; j ++)
if (nxt[j] == i) nxt[j] = in;
}
}
if (! con) continue;
static int mapTo[MAXK];
fill(mapTo, mapTo + MAXK, -1);
int z = 0;
for (int i = 1; i < k; i ++)
if (mapTo[nxt[i]] == -1) {
mapTo[nxt[i]] = z ++;
}
for (int i = 0; i + 1 < k; i ++)
nxt[i] = mapTo[nxt[i + 1]];
nxt[k - 1] = in == -1 || mapTo[in] == -1 ? z : mapTo[in];
cur.show();
ep("%d %d
", s, con);
nxt.show();
ep("--------------
");
int h = nxt.transform();
int idx = dfs(h);
B[0][hash[f]][idx] += con;
B[0][hash[f]][idx] %= MOD;
}
}
return hash[f];
}
MatrixA A, tA;
void dfs2(int cur, Status s, int combination) {
if (cur == k) {
s.show();
ep("%d
-----------
", combination);
int idx = hash[s.transform()];
A[idx] += combination;
A[idx] %= MOD;
}
else {
int cnt[MAXK];
fill(cnt, cnt + cur + 1, 0);
for (int i = 0; i < cur; i ++)
cnt[s[i]] ++;
for (int S = 0; S < 1 << cur; S ++) {
int con = 1;
Status nxt = s;
nxt[cur] = -1;
for (int i = 0; i < cur; i ++)
if (test(S, i)) {
con *= cnt[i];
if (nxt[cur] == -1) nxt[cur] = i;
else {
for (int j = 0; j < cur; j ++)
if (nxt[j] == i) nxt[j] = nxt[cur];
}
}
if (! con) continue;
static int mapTo[MAXK];
int z = 0;
fill(mapTo, mapTo + cur, -1);
for (int i = 0; i < cur; i ++) {
if (mapTo[nxt[i]] == -1) {
mapTo[nxt[i]] = z ++;
}
nxt[i] = mapTo[nxt[i]];
}
if (nxt[cur] == -1) {
int x = 0;
while (true) {
bool ok = true;
for (int i = 0; i < cur; i ++)
if (nxt[i] == x) {
ok = false;
break;
}
if (! ok) x ++;
else break;
}
nxt[cur] = x;
}
dfs2(cur + 1, nxt, combination * con);
}
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("count.in", "r", stdin);
freopen("count.out", "w", stdout);
#endif
scanf("%d%lld", &k, &n);
memset(hash, -1, sizeof hash);
dfs(0);
ep("find %d
", cntS);
ep("-----------
");
for (int i = 0; i < cntS; i ++) {
for (int j = 0; j < cntS; j ++)
ep("%d ", B[0][i][j]);
ep("
");
}
ep("===================
");
for (int i = 1; i < LOGN; i ++)
multi(B[i - 1], B[i - 1], B[i]);
Status s;
dfs2(0, s, 1);
ep("-----------
");
for (int i = 0; i < cntS; i ++)
ep("%d ", A[i]);
ep("
");
ep("===================
");
n -= k;
for (int i = 0; i < LOGN; i ++)
if (n >> i & 1) {
tA = A;
multi(tA, B[i], A);
}
i64 ans = 0;
for (int i = 0; i < HASHSIZE; i ++)
if (hash[i] != -1) {
Status x = transform(i);
bool ok = true;
for (int j = 1; j < k; j ++)
if (x[j] != x[j - 1]) {
ok = false;
break;
}
if (ok) ans += A[hash[i]];
}
ans %= MOD;
printf("%d
", (int) ans);
ep("%lld
", ans);
return 0;
}