The only survival
http://acm.hdu.edu.cn/showproblem.php?pid=4903
Time Limit: 40000/20000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
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
For each test case, the first line contains 3 integers n,k,L.
T<=5 n,k<=12,L<=10^9.
#include<cstdio>
#include<algorithm>
using namespace std;
int n,k,l,ans;
int d[],f[],C[][];
const int mod=1e9+;
void dfs(int now,int dis,bool ok,int sum)
//当前枚举哪个点，这个点到1的最短距离，是否满足第n个点到1的最远距离为k，当前方案数
{
if(now== && !dis) return;//dis初值为0，只有第一个点的距离为0
d[now]=dis; ok|=dis==k;
if(now>)//计算当前点和前面所有点之间连边的方案数
if(dis<=k)
{
f[]=; f[]=;
//f[i][0/1]：第now与1到i之间的边是否存在一条边使当前dis成立
for(int i=;i<now;i++)
if(d[i]==dis) //1到now的最短距离==1到i的最短距离 ，那么now和i之间的边可以为任意长度，第i个点对dis是否成立毫无影响
{
f[]=1ll*f[]*l%mod;
f[]=1ll*f[]*l%mod;
}
else
// 要保证1到now的最短距离为dis，如果之前在1——i-1中，已经有一条边使dis成立，那么i与now之间的边长只需>=dis-d[i]；如果1——i-1中不存在这么一条边，那么i与now之间的边=dis-d[i]
//如果1——i与now之间的边不能使dis成立，前i-1个已经考虑过了，最后一个i与now之间的边 要>dis-d[i]
{//设这条边边权为val
f[]=(1ll*f[]*(l-dis+d[i]+)%mod+f[])%mod; //d[i]+val>=dis ==> dis-d[i]<=val<=L ==> val有L-(dis-d[i])+1种选择
f[]=1ll*f[]*(l-dis+d[i])%mod; //d[i]+val>dis ==> dis-d[i]<val<=L ==> val有L-(dis-d[i])种选择
}
sum=1ll*sum*f[]%mod;
}
else for(int i=;i<now;i++) sum=1ll*sum*min(l,l-k+d[i])%mod;
//如果dis>k，那么1到n的最短路一定不经过now，now与其他点的边就无所谓了
if(now==n)
{
if(!ok) return;
int j;
//搜索的时候d按不上升搜索，所以搜索出的d还要分配给每个点，组合计算分配方案数
for(int tmp=n-,i=;i<=n;i=j)
// 除去1和n，还剩n-2个点待分配
{
for(j=i;d[i]==d[j] && j<=n;j++);
//相等的d的范围:i——j-1，所以相等的d的个数为j-i
//给tmp个点中的j-i个点分配d，方案数为C（tmp，j-i）
if(d[i]==k) i++;//如果当前d==k，那么包含了点n，需要减去，给i加1，相当于给j-i减1
sum=1ll*sum*C[tmp][j-i]%mod;
tmp-=j-i; //有j-i个点分配完了
}
ans=(ans+sum)%mod;
return;
}
for(;dis<=k+;dis++) dfs(now+,dis,ok,sum);
//边长>k且<l的边全部看为k+1
}
int main()
{
C[][]=;
for(int i=;i<=;i++)
{
C[i][]=;
for(int j=;j<=i;j++)
C[i][j]=(C[i-][j-]+C[i-][j])%mod;
}
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d%d",&n,&k,&l);
if(k>l) { puts(""); continue; }
ans=;
dfs(,,,);
printf("%d\n",ans);
}
}
#include<cstdio>
#include<iostream>
#include<algorithm> using namespace std; typedef long long LL; const int mod=1e9+; int N,K,L; int C[][]; int d[];
int f[]; int ans; void dfs(int now,int dis,bool ok,int sum)
{
if(now== && !dis) return;
d[now]=dis;
ok|=dis==K;
if(now>)
if(dis<=K)
{
f[]=;
f[]=;
for(int i=;i<now;++i)
if(d[i]==dis)
{
f[]=(LL)f[]*L%mod;
f[]=(LL)f[]*L%mod;
}
else
{
f[]=(LL)f[]*(L-dis+d[i]+)%mod;
f[]+=f[];
f[]-=f[]>=mod ? mod : ;
f[]=(LL)f[]*(L-dis+d[i])%mod;
}
sum=(LL)sum*f[]%mod;
}
else
for(int i=;i<now;++i) sum=(LL)sum*min(L,L-K+d[i])%mod;
if(now==N)
{
if(!ok) return;
int j;
for(int tmp=N-,i=;i<=N;i=j+)
{
for(j=i;d[j]==d[i] && j<=N;++j);
j--;
int cnt=j-i+;
if(d[i]==K) cnt--;
sum=(LL)sum*C[tmp][cnt]%mod;
tmp-=cnt;
}
ans+=sum;
ans-=ans>=mod ? mod : ;
return;
}
for(;dis<=K+;++dis) dfs(now+,dis,ok,sum);
} int main()
{
C[][]=;
for(int i=;i<=;++i)
{
C[i][]=;
for(int j=;j<=i;++j)
{
C[i][j]=C[i-][j]+C[i-][j-];
C[i][j]-=C[i][j]>=mod ? mod : ;
}
}
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d%d",&N,&K,&L);
ans=;
if(K<=L) dfs(,,false,);
cout<<ans<<'\n';
}
}
