标签：DP
题目
n,k<=12,L<=1e9
分析
设dis[i]表示1->i最短路
对于一条边的两个端点i,j，如果dis[i]==dis[j]，那么这条边边权任意，同理，如果dis[i] < dis[j]，那么边权不能小于dis[j]-dis[i]
同时对于点i，一定存在一个点j，使得dis[j] < dis[i]且j到i的边长度为dis[i]-dis[j]
我们可以将它们按照dis值从小到大排序，就可以直接进行dp
我们注意到一定会存在dis[1]=0,dis[n]=k
对于dis[i] > k的值，对答案无影响，可以直接用k+1表示
对于2~n-1的点，我们也不需要它们具体的最短路是多少，我们只需要知道对于最短路是j的点的个数就可以了
这样我们就可以从小到大枚举所有点的最短路x，再枚举满足最短路是x的点的个数，并计算方案总数
code
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(register int i=a;i<=b;i++)
#define dep(i,a,b) for(register int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline ll read()
{
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int mod=1e9+7;
int a[16],b[16],n,k,L,tmp=1,cnt,bit[16];
ll ans;
void dfs(int x,int y){
if(x==k+1){
if(y+2!=n&&k==L)return;
cnt=0;
rep(i,1,n)
rep(j,1,a[i])b[++cnt]=i;
b[++cnt]=k;
rep(i,1,n-y-2)b[++cnt]=k+1;
ll re=1;
rep(i,1,cnt){
ll s1=1,s2=1;
rep(j,0,i-1)
if(b[j]<b[i])s1=s1*(L-(b[i]-b[j])+1)%mod,s2=s2*(L-(b[i]-b[j]))%mod;
if(b[i]<=k)re=re*(s1-s2+mod)%mod;else re=re*s1%mod;
rep(j,0,i-1)
if(b[i]==b[j])re=re*L%mod;
}
int tt=tmp;rep(i,1,x-1)tt/=bit[a[i]];tt/=bit[n-y-2];
ans=(ans+re*tt)%mod;return;
}
rep(i,0,n-y-2)a[x]=i,dfs(x+1,y+i);
}
int main()
{
n=read(),k=read(),L=read();
bit[0]=1;rep(i,1,12)bit[i]=bit[i-1]*i;
rep(i,2,n-2)tmp*=i;
if(L<k){puts("0");return 0;}
if(n==2){puts("1");return 0;}
dfs(1,0);
cout<<ans<<endl;
return 0;
}
