惊了
\(Description\)
给定\(n,k,L\)，表示，有一张\(n\)个点的无向完全图，每条边的边权在\([1,L]\)之间。求有多少张无向完全图满足，\(1\)到\(n\)的最短路为\(k\)。
\(n,k\leq 12,\ L\leq10^9\)。\(Solution\)
考虑暴力，直接枚举\(1\)到每个点的最短路\(d_i\)是多少。
对于方案数，如果\(d_i=d_j\)，那么\(i,j\)之间的边权随便定。否则设\(d_i\lt d_j\)，那么\(i,j\)之间的边权不小于\(d_j-d_i\)，且对于\(j\)，至少存在一个\(i\)满足\(d_i+e[i][j]=d_j\)。 这样的复杂度是\(O(12^{13})\)的（\(d_i\geq k\)的全在一起算）。注意到我们并不关心具体\(d_i=x\)的点是哪些。所以考虑直接枚举\(d_i=x\)的点有多少个。
\(DFS\)一下，算下组合数就好啦。复杂度是\(C_{n-1+k}^k\)叭？具体：首先要强制\(d_1=0,d_n=k\)。 对于当前的\(x\)，如果有\(t\)个点\(d_i=x\)，它们之间可以任意连边，方案数是，\(\prod_{i=0}^{t-1}L^i\)。（当然还要乘个组合数） 然后这\(t\)个点和之前\(m\)个点连边，不考虑存在\(d_i+e[i][j]=x\)的限制，（每个点的）方案数是\(\prod_{i=1}^{m}(L-(x-d_i)+1)\)，容斥一下，再减掉\(\prod_{i=1}^{m}(L-(x-d_i))\)，就可以啦。 如果要求的最短路\(\geq k\)，不需要减后面那项（在边权范围内xjb连即可，不是需要恰好\(=k\)）。 最后再算一下\(n\)点连边的方案数即可。//312MS 1200K#include#include #include #define mod 1000000007#define gc() getchar()typedef long long LL;const int N=15;int n,K,L,C[N][N],now,d[N],pw[N];LL Ans;inline int read(){ int now=0;register char c=gc(); for(;!isdigit(c);c=gc()); for(;isdigit(c);now=now*10+c-48,c=gc()); return now;}void DFS(int x,int coef){ LL c1=1,c2=1; for(int i=1; i<=now; ++i) c1=c1*(L-x+d[i]+1)%mod, c2=c2*(L-x+d[i])%mod; LL c3=c1+mod-c2; if(x==K) { LL c=coef*c3%mod*pw[n-1-now]%mod;//n与其他点的贡献 for(int i=now+1; i