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)
Problem Description
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
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
Input
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, the first line contains 3 integers n,k,L.
T<=5 n,k<=12,L<=10^9.
Output
For each test case, output the answer in one line.
Sample Input
2
3 3 3
4 4 4
Sample Output
8
668
题意：
有一张n个点的无向完全图，第i个点的编号是i，每条边的边权在1到L之间的正整数，问存在多少个图使得1到n的最短路是k。
k<=12,L<=10^9,n<=12.
不会啊不会啊，借鉴了 Claris 神犇： http://www.cnblogs.com/clrs97/p/5690267.html
考场上咋办？
审题：
1、无向、完全图（即每个点都要与其他点有连边），由此应该想到如果k>l，无解
2、n=1，无解，n=2，输出1
限制非常宽的搜索，为了好搜，要自己加限制
计数问题可以强制不下降搜索，结果再用排列组合累计
进一步分析，
本题要求是最短路，那么如果我们算出了每个点的最短路，利用乘法原理在L范围内累积即可
再加限制：限制每个点到1号点的最短路
所以
枚举每个点到1号点的最短路
考虑两个点之间的边
如果i和j到1号点的最短距离相等，那么i与j之间的连边就可以是任意值
否则，就要考虑在满足最短路限制、边长限制下，这条边的情况。
至于边长是多少，不关心，他们与到1号点的最短路无关（已经枚举限制了），只需计算方案数，推推式子
对本题认识就这些了。。。。。。
#include<cstdio> #include<algorithm> using namespace std; int n,k,l,ans; int d[20],f[2],C[15][15]; const int mod=1e9+7; void dfs(int now,int dis,bool ok,int sum) //当前枚举哪个点，这个点到1的最短距离，是否满足第n个点到1的最远距离为k，当前方案数 { if(now==2 && !dis) return;//dis初值为0，只有第一个点的距离为0 d[now]=dis; ok|=dis==k; if(now>1)//计算当前点和前面所有点之间连边的方案数 if(dis<=k) { f[0]=1; f[1]=0; //f[i][0/1]：第now与1到i之间的边是否存在一条边使当前dis成立 for(int i=1;i<now;i++) if(d[i]==dis) //1到now的最短距离==1到i的最短距离 ，那么now和i之间的边可以为任意长度，第i个点对dis是否成立毫无影响 { f[1]=1ll*f[1]*l%mod; f[0]=1ll*f[0]*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[1]=(1ll*f[1]*(l-dis+d[i]+1)%mod+f[0])%mod; //d[i]+val>=dis ==> dis-d[i]<=val<=L ==> val有L-(dis-d[i])+1种选择 f[0]=1ll*f[0]*(l-dis+d[i])%mod; //d[i]+val>dis ==> dis-d[i]<val<=L ==> val有L-(dis-d[i])种选择 } sum=1ll*sum*f[1]%mod; } else for(int i=1;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-2,i=2;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+1;dis++) dfs(now+1,dis,ok,sum); //边长>k且<l的边全部看为k+1 } int main() { C[0][0]=1; for(int i=1;i<=12;i++) { C[i][0]=1; for(int j=1;j<=i;j++) C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod; } int T; scanf("%d",&T); while(T--) { scanf("%d%d%d",&n,&k,&l); if(k>l) { puts("0"); continue; } ans=0; dfs(1,0,0,1); printf("%d ",ans); } }
#include<cstdio> #include<iostream> #include<algorithm> using namespace std; typedef long long LL; const int mod=1e9+7; int N,K,L; int C[13][13]; int d[13]; int f[2]; int ans; void dfs(int now,int dis,bool ok,int sum) { if(now==2 && !dis) return; d[now]=dis; ok|=dis==K; if(now>1) if(dis<=K) { f[0]=1; f[1]=0; for(int i=1;i<now;++i) if(d[i]==dis) { f[1]=(LL)f[1]*L%mod; f[0]=(LL)f[0]*L%mod; } else { f[1]=(LL)f[1]*(L-dis+d[i]+1)%mod; f[1]+=f[0]; f[1]-=f[1]>=mod ? mod : 0; f[0]=(LL)f[0]*(L-dis+d[i])%mod; } sum=(LL)sum*f[1]%mod; } else for(int i=1;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-2,i=2;i<=N;i=j+1) { for(j=i;d[j]==d[i] && j<=N;++j); j--; int cnt=j-i+1; if(d[i]==K) cnt--; sum=(LL)sum*C[tmp][cnt]%mod; tmp-=cnt; } ans+=sum; ans-=ans>=mod ? mod : 0; return; } for(;dis<=K+1;++dis) dfs(now+1,dis,ok,sum); } int main() { C[0][0]=1; for(int i=1;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]; C[i][j]-=C[i][j]>=mod ? mod : 0; } } int T; scanf("%d",&T); while(T--) { scanf("%d%d%d",&N,&K,&L); ans=0; if(K<=L) dfs(1,0,false,1); cout<<ans<<' '; } }
