P11223 题解

· · 题解

不算太难但很有意思的一道题，这里提供一下我的构造方法。

考虑限制给到了 m\le n+1，我们直接取满。

我们确定两个状态使其一部分情况最终到这个值，另一部分状态最终到另一个值，这两个值封闭；为了最小化影响，我们直接使这两个值分别为 n 和 m（即第 n 行都是 n，第 m 行都是 m）。

我们手模一下小数据找找灵感，k=0 的时候我们显然直接让 n 这个值无法到达就行了；但 k=1 就不那么好办了，我们要构造出来一条路径经过所有值一次，相当于确定出一个排列，大概就是这样（拿 n=8 举个例子）：

2 9 9 9 9 9 9 8 9
9 3 9 9 9 9 9 8 9
9 9 4 9 9 9 9 8 9
9 9 9 5 9 9 9 8 9
9 9 9 9 6 9 9 8 9
9 9 9 9 9 7 9 8 9
9 9 9 9 9 9 8 8 9
9 9 9 9 9 9 9 8 9

显然只能沿着不是 m 的数一路走到 n。

我们沿着 k=1 继续想，如果第 i 列的某个值给到了 n，那么相当于走到该值后的 n-i 个操作随意排列，即给答案增加了 (n-i)!，同时注意到第 i 列还剩下 n-i+1 个值都可以自由改动（其他的值在此之前都被调用过了），也就是在第 i 行 k\in[0,(n-i+1)!] 都可以被处理（如果用 (n-i)! 处理完还有剩余就像 k=1 一样引导其走到下一列再处理）。

易证 \forall k \in [0,n!] 可以处理。

代码实现不难，注意特判 n=1,k=0 的情况。


#include<bits/stdc++.h>
//#include<Windows.h>
#define int long long
//#define ll long long
#define double long double
#define fi first
#define se second
//#define ls t[p].l
//#define rs t[p].r
#define y1 yyyyyyyyyyyyyyyy1
using namespace std;
const int N = 3e5 + 10, inf = 1e12, M = 101;
const double eps = 1e-14, pi = 3.1415926, kou = 0.577215669902;
const int mod = 1e9 + 7;
//const int AQX = 9;
mt19937 rnd(time(0) ^ clock());
int random(int l, int r){
    return rnd() % (r - l + 1) + l;
}
/*
                           _      _        _          
                   ____  _| |_   | |_  ___| |___ _ _  
                  |_ / || | ' \  | ' \/ -_) / -_) ' \ 
                  /__|\_, |_||_|_|_||_\___|_\___|_||_|
                      |__/    |___|                              

*/
//struct Graph{
//  int head[N], tot = 1;
//  struct edge{
//      int t;
//      int d, fa, f;
//      int next;
//  }e[N << 1];
//  void edge_add(int u, int v, int w = 0){
//      e[++tot].next = head[u];
//      e[tot].t = v;
//      e[tot].d = w;
//      e[tot].f = u;
//      head[u] = tot;
//  }
//  void clear(int n){
//      for(int i = 1;i <= tot;i++)e[i].t = e[i].f = e[i].d = e[i].next = 0;
//      for(int i = 1;i <= n;i++)head[i] = 0;
//      tot = 0;
//  }
//}g;
//int qmr(int x, int a){
//  int ret = 1, p = x;
//  while(a){
//      if(a & 1)ret = ret * p % mod;
//      p = p * p % mod;
//      a >>= 1;
//  }
//  return ret;
//}

int n, k, jc[N], ans[20][20];
signed main(){
    int T, lsj;
    cin >> lsj >> T;
    jc[0] = 1;
    for(int i = 1;i <= 12;i++)jc[i] = jc[i - 1] * i % mod;
    while(T--){
        cin >> n >> k;
        if(n == 1 && k == 0){
            cout << 2 << " " << 2 << endl;
            printf("1 1\n");
            continue;
        }
        cout << n + 1 << " " << n << endl;
        for(int i = 1;i < n;i++){
            int p = jc[n - i], j = n;
            for(;k >= p;k -= p, j--)ans[i][j] = n;
            for(;j;j--)ans[i][j] = n + 1;
            if(k)ans[i][i] = i + 1;
        }
        for(int i = 1;i <= n;i++){
            for(int j = 1;j < n;j++)printf("%lld ", ans[j][i]);
            printf("%lld %lld\n", n, n + 1);
        }
    }
    return 0;
}