首先我要吐槽，这题目就是坑，给那么多无用的信息，我还以为要根据提示才能做出来呢！
算法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#include #include #include #include using namespace std;#ifdef debug#define ep(...) fprintf(stderr, __VA_ARGS__)#else#define ep(...) assert(true)#endiftypedef 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("\n");#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\n", s, con); nxt.show(); ep("--------------\n"); 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\n-----------\n", 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\n", cntS); ep("-----------\n"); for (int i = 0; i < cntS; i ++) { for (int j = 0; j < cntS; j ++) ep("%d ", B[0][i][j]); ep("\n"); } ep("===================\n"); for (int i = 1; i < LOGN; i ++) multi(B[i - 1], B[i - 1], B[i]); Status s; dfs2(0, s, 1); ep("-----------\n"); for (int i = 0; i < cntS; i ++) ep("%d ", A[i]); ep("\n"); ep("===================\n"); 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\n", (int) ans); ep("%lld\n", ans); return 0;}