题目地址：HDUOJ：Problem – 4903

题目描述

There is an old country and the king fell in love with a devil. The devil always ask the king to do some crazy things. Although the king used to be wise and beloved by his people. Now he is just like a boy in love and can’t refuse any request from the devil. Also, this devil is looking like a very cute Loli.
Something bad actually happen. The devil makes this kingdom’s people infected by a disease called lolicon. Lolicon will take away people’s life in silence.
Although z*p is died, his friend, y*wan is not a lolicon. Y*wan is the only one in the country who is immune of lolicon, because he like the adult one so much.
As this country is going to hell, y*wan want to save this country from lolicon, so he starts his journey.
You heard about it and want to help y*wan, but y*wan questioned your IQ, and give you a question, so you should solve it to prove your IQ is high enough.
The problem is about counting. How many undirected graphs satisfied the following constraints?

1. This graph is a complete graph of size n.
2. Every edge has integer cost from 1 to L.
3. The cost of the shortest path from 1 to n is k.

Can you solve it?
output the answer modulo 10^9+7
有一张n个点的无向完全图，第i个点的编号是i，每条边的边权在1到L之间的正整数，问存在多少个图使得1到n的最短路是k。

输入输出格式

输入格式：
The first line contains an integer T, denoting the number of the test cases.
For each test case, the first line contains 3 integers n,k,L.
T<=5 n,k<=12,L<=10^9.

输出格式：
For each test case, output the answer in one line.

输入输出样例

输入样例#1：

2
3 3 3
4 4 4

输出样例#1：

8
668

题解

首先是方案数，我们就要找方案。考虑如果暴力地解决应该如何，我们可以首先把点1到每个点的最短路长度给枚举出来，然后构造这个图。但是仔细地分析一下，我们似乎不关心点的编号，只关心点的数量。那么这就好办了，我们只需要枚举1到该点最短路长度为定值的点有多少个就好了。
下面的叙述中，用dis代替某点最短路长度。
但是怎么统计方案数呢？考虑当前枚举到dis为x的点有i个的状况，枚举最短路长度1~x-1的方案数早已算出为res，且前面已经枚举过的点数和为tot，cnt数组表示dis为某值的点有多少个。
首先从剩下的点里面把i个点选出来，乘C_{n-tot-1}^i；
这些点之间的边是无所谓的，所以每条边随便给个长度就行，乘L^{C_i^2}；
dis更小的点向这些点连边，设当前枚举到了之前的dis为x'的情况，这些边要满足x' + w \geq x（j是dis更小的点，i是当前dis的点，w是这条边的边权），每条边的边权有L - (x - x') + 1种可以选择，但是如果全都选择了比x - x'大的边权，最短路长度就无法满足，因此有一部分方案不能满足，要减去，所以最后的方案数是 (L - (x - x') + 1)^{cnt_{x'}} - (L - (x - x'))^{cnt_{x'}} ；
把上面这一大堆乘进答案里就好啦。
到达枚举终点时tot还有可能比n小，即有点没有算过。这些点内部的边肯定是任意怎么样都行，但是要保证它们的dis比k大，这样的话，上面的“一部分方案不能满足”部分就不存在了。
注意这里计算的数据都挺大的，及时取模，小心溢出。

代码

// Code by KSkun, 2018/3
#include <cstdio>
#include <cstring>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    char c = fgc();
    while(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MO = 1e9 + 7;

LL C[20][20];

inline void calc() {
    for(int i = 0; i <= 12; i++) {
        C[i][0] = 1;
        for(int j = 1; j <= i; j++) {
            C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MO;
        }
    }
}

inline LL fpow(LL x, LL k) {
    LL t = 1;
    while(k) {
        if(k & 1) t = (t * x) % MO;
        x = (x * x) % MO;
        k >>= 1;
    }
    return t;
}

int T, n, k, l, cnt[20];
LL ans;

inline LL cal(int x) {
    if(!cnt[x]) return 1;
    LL t1 = 1, t2 = 1;
    for(int i = 0; i < x; i++) {
        if(!cnt[i]) continue;
        if(x - i > l) return 0;
        t1 = t1 * fpow(l - (x - i) + 1, cnt[i]) % MO;
        t2 = t2 * fpow(l - (x - i), cnt[i]) % MO;
    }
    if(x == k + 1) return fpow(t1, cnt[x]);
    t1 -= t2; if(t1 < 0) t1 += MO;
    t1 = fpow(t1, cnt[x]);
    return t1;
}

inline void dfs(int x, LL res, int tot) {
    if(x == k) {
        for(int i = 1; i + tot <= n; i++) {
            LL nres = res * C[n - tot - 1][i - 1] % MO * fpow(l, C[i][2]) % MO * fpow(l, C[n - tot - i][2]) % MO;
            cnt[k] = i; cnt[k + 1] = n - tot - i;
            nres = nres * cal(k) % MO * cal(k + 1) % MO;
            ans = (ans + nres) % MO;
        }
        return;
    }
    for(int i = 0; i + tot < n; i++) {
        cnt[x] = i;
        LL nres = res * fpow(l, C[i][2]) % MO * C[n - tot - 1][i] % MO * cal(x) % MO;
        dfs(x + 1, nres, tot + i);
    }
}

int main() {
    calc();
    T = readint();
    while(T--) {
        n = readint(); k = readint(); l = readint();
        memset(cnt, 0, sizeof(cnt));
        cnt[0] = 1;
        ans = 0;
        dfs(1, 1, 1);
        printf("%lld\n", ans);
    }
    return 0;
}