CF 459C

做过一点点构造题，花了一个小时想怎么构造，但并没有什么用，写起来感觉有点复杂。

标程分析：

对于输出结果，共d次分配情况。而对于每个学生而言，每个人有d次选择乘坐车辆的机会。

那么所有同学在k辆车，d轮下的选车情况共有k的d次方种选法。

仔细想一想，如果学生的数量超过了上述选法种数，根据鸽巢原理，必有重复的情况产生，此时则不符合题意。

其余情况，对于全排列中的n项，我们只需要选取k进制下的前n个数字输出结果即可。

竖着看输出样例。

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstdio>
#define ll long long
using namespace std;

int n, k, d;
//n为总人数，k为大巴数量，d为操作次数
int res[1010][1010];
void solve()
{
    for(int i = 1 ; i < n ; i++){
        for(int j = 0 ; j < d ; j++){
            res[j][i] = res[j][i - 1];
        }
        for(int j = d - 1 ; j >= 0 ; j--){
            res[j][i] = (res[j][i] + 1) % k;
            if(res[j][i])    break;
        }
    }
    
    for(int i = 0 ; i < d ; i++){
        for(int j = 0 ; j < n ; j++){
            printf("%d ",res[i][j] + 1);
        }
        printf("
");
    }
}

int main(){
    scanf("%d%d%d",&n,&k,&d);
    ll tmp = 1;
    for(int i = 1 ; i <= d ; i++){
        tmp *= k;
        if(tmp >= n)    break;
    }
    if(tmp < n){
        printf("-1
");
        return 0;
    }    
    if(n <= k){
        for(int i = 1 ; i <= d ; i++){
            for(int j = 1 ; j <= n ; j++){
                printf("%d ",j);
            }
            printf("
");
        }    
        return 0;
    }else{
        solve();
    }

    return 0;
}