当想了半个多小时三维坐标系的菜比看到了组合数学题解
题意
将 (1leq i, j, kleq N) 的 (N^3) 个三元组 ((i, j, k)) 进行排序，排序时以总和为第一关键字，第一维为第二关键字，第二维为第三关键字，从小到大排。
询问第 (K) 个三元组
分析
如果用三维坐标系描述，不难想到，三元组分布在长宽高均为 (N) 的正方体上；将其按 (x+y+z=C) 进行切片，就能得到第一关键字；同理分析得到第二第三。
如果具有极其恐怖的空间想象能力，可以试试这个方法。反正我是不行
考虑 (i+j+k=S) 的方案数：
等效于 (S) 个小球塞入 (3) 个盒子，每个盒子非空且容积为 (n) ，问方案数。
不考虑 (n) 的限制，则方案数用隔板法得 (dbinom{S-1}{2}) 。
现考虑有一个数超过 (n) 的限制，我们对它容斥：先分配给这个数 (n) ，再用隔板法分配得 (dbinom{S-n-1}{2})；超过 (n) 的那个数有 (dbinom{3}{1}) 种选法。
同理容斥两个数、三个数超过 (n) 限制的情况，得到最后方案数为：
(displaystyle sum_{i=0}^3(-1)^idbinom{3}{i}cdot dbinom{S-icdot n-1}{2}) 。
由于组合数下方的数字都较小，直接暴力展开可求，复杂度 (O(1)) 。
因为层数最高为 (3n) ，直接暴力枚举过去，找到在第几层即可，复杂度为 (O(n)) 。
求出第一关键字后，我们得到了 (i+j+k=S) 的答案，然后考虑求 (i) 。
我们直接从 (1) 到 (n) 枚举 (i) ，则此时 (j+k=S-i) 的方案数：
等效于 (S-i) 个小球塞入 (2) 个盒子，每个盒子非空且容积为 (n) ，问方案数。
同上得到为： (displaystyle sum_{j=0}^2(-1)^jdbinom{2}{j}cdot dbinom{S-i-jcdot n-1}{1}) 。
同理直接展开，然后暴力枚举，复杂度为 (O(n)) 即可确定 (i) 。
确定 (i) 与 (S) 后，我们直到 (j+k=S-i) ，则 (j_{min}=max(S-i-n, 1)) 。
当我们筛除上面的方案数，确定 ((i, j, k)) 为 (j+k=S-i) 的第 (K) 个后，则 (j_K=j_{min}+K-1) 。
然后用 (k=S-i-j_K) 求出 (k) 输出即可。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=3e6+10;
ll n, k, sum[MAXN];
inline ll calc3(ll k){
ll res=(k-1)*(k-2)/2;
k-=n;
if(k<=0) return res;
res-=(k-1)*(k-2)/2*3;
k-=n;
if(k<=0) return res;
res+=(k-1)*(k-2)/2*3;
k-=n;
if(k<=0) return res;
return res-(k-1)*(k-2)/2;
}
inline ll calc2(ll k){
ll res=k-1;
k-=n;
if(k<=0) return res;
res-=(k-1)*2;
k-=n;
if(k<=0) return res;
return res+(k-1);
}
inline void work(){
ll flr=3;
while(sum[flr]<k)
k-=sum[flr++];
for(int i=1;i<=n;++i){
ll res=calc2(flr-i);
if(res<k){
k-=res;
continue;
}
ll x=max(flr-i-n, 1ll)+(k-1);
cout<<i<<" "<<x<<" "<<flr-i-x;
break;
}
}
inline void pre(){
cin>>n>>k;
for(int i=1;i<=3*n;++i) sum[i]=calc3(i);
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
pre();
work();
cout.flush();
return 0;
}