题意
原题链接
订正链接
构造一个图,图的所有边权等于$1$,求使$1$到$n$的最短路距离为$k$的方案数。
对于$ 100\text{%}$的数据$n,k \leq 100$
思路
(为了图(wo)方(tai)便(cai),下文的$m$代表上文题意中的$k$,下文的$k$详见下文)
考虑$dp$。
因为这张图的最短路距离为$k$,所以考虑分层图。
设$f[i][j][k]$表示前$i$层总共选了$j$个,第$i$层选了$k$个。
很明显$f[0][1][1]=1$(前$0$层选$1$个,第$0$层选$1$个,因为第$0$层有一点$1$)。
暴力枚举$i,j,k,l$,分别表示前$i$层,选了$j$个,第$i$层选了$k$个,第$i-1$层选了$l$个。
${f[i][j][k]+=f[i-1][j-k][l] \times {(2^l -1)}^k \times 2^{\frac{k\times (k-1)}{2}} \times {C}_{n-j+k-1}^{k}}$
当$i=n$时,该层必须有$n$(上一个$dp$式子是必须没有$n$)。
$f[i][j][k]+=f[i-1][j-k][l] \times {(2^l -1)}^k \times 2^{\frac{k\times (k-1)}{2}} \times {C}_{n-j+k-1}^{k-1}$
${(2^l-1)}^k$: 当前层每个点至少要与上一层的一个点有边,每个点有$ 2^l -1$种连法,总共有$k$个点
$2^{\frac{k\times (k-1)}{2}} $: $k$个点之间可以互相连
$C_{n-j+k-1}^{k}$: $n-j+k$个点选$k$个的方案数,但是$n$不能选
$C_{n-j+k-1}^{k-1}$: $n-j+k$个点选$k$个的方案数,但是$n$必须选
$ans+=f[m][i][j] \times 2^{j\times (n-i)} \times 2^{\frac{(n-i)\times (n-i-1)}{2}}$
还剩$ x=n-i $个点未考虑
$2^{j\times x} $: 剩下的点可以和任何一个已经选了的点连边
$2^{\frac{x\times (x-1)}{2}} $:剩下的点之间互相连边
Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 |
#include<algorithm> #include<bitset> #include<complex> #include<deque> #include<exception> #include<fstream> #include<functional> #include<iomanip> #include<ios> #include<iosfwd> #include<iostream> #include<istream> #include<iterator> #include<limits> #include<list> #include<locale> #include<map> #include<memory> #include<new> #include<numeric> #include<ostream> #include<queue> #include<set> #include<sstream> #include<stack> #include<stdexcept> #include<streambuf> #include<string> #include<typeinfo> #include<utility> #include<valarray> #include<vector> #include<cctype> #include<cerrno> #include<cfloat> #include<ciso646> #include<climits> #include<clocale> #include<cmath> #include<csetjmp> #include<csignal> #include<cstdarg> #include<cstddef> #include<cstdio> #include<cstdlib> #include<cstring> #include<ctime> using namespace std; #define mod 1000000007 #define re register #define int long long class Quick_Input_Output{ private: static const int S=1<<21; #define tc() (A==B&&(B=(A=Rd)+fread(Rd,1,S,stdin),A==B)?EOF:*A++) char Rd[S],*A,*B; #define pc putchar public: #undef gc #define gc getchar inline int read(){ int res=0,f=1;char ch=gc(); while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=gc();} while(ch>='0'&&ch<='9') res=res*10+ch-'0',ch=gc(); return res*f; } inline void write(int x){ if(x<0) pc('-'),x=-x; if(x<10) pc(x+'0'); else write(x/10),pc(x%10+'0'); } #undef gc #undef pc }I; #define File freopen("timegate.in","r",stdin);freopen("timegate.out","w",stdout); int n,m,ans,f[110][110][110],C[110][110],pw[10010]; int fpow(int a,int b){ re int s=1ll; while(b){ if(b&1) s*=a,s%=mod; a*=a;a%=mod; b>>=1ll; } return s; } signed main(){ File n=I.read();m=I.read(); for(int i=0;i<=100;i++) C[i][0]=1; for(int i=1;i<=100;i++) for(int j=1;j<=100;j++) C[i][j]=C[i-1][j]+C[i-1][j-1],C[i][j]%=mod; pw[0]=1;for(int i=1;i<=10000;i++) pw[i]=pw[i-1]*2,pw[i]%=mod; f[0][1][1]=1; for(int i=1;i<=m;i++){ for(int j=1;j<=n;j++){ for(int k=1;k<=j;k++){ for(int l=1;l<=j-k;l++){ if(n-j+k<k)continue; if(i<m){ f[i][j][k]+=f[i-1][j-k][l]%mod*fpow(pw[l]-1,k)%mod*pw[k*(k-1)/2]%mod*C[n-j+k-1][k]%mod; f[i][j][k]%=mod; }else{ f[i][j][k]+=f[i-1][j-k][l]%mod*fpow(pw[l]-1,k)%mod*pw[k*(k-1)/2]%mod*C[n-j+k-1][k-1]%mod; f[i][j][k]%=mod; } } } } } for(int i=m+1;i<=n;i++){ for(int j=1;j<=i;j++){ int x=n-i; ans+=f[m][i][j]%mod*pw[j*x]%mod*pw[x*(x-1)/2]%mod; ans%=mod; } } I.write(ans);putchar('\n'); return 0; } |