Codeforces 1109D. Sasha and Interesting Fact from Graph Theory
解题思路:
这题我根本不会做,是周指导带飞我.
首先对于当前已经有 \(m\) 个联通块的有标号生成树的数量是
\[ n^{m-2}\prod_{i=1}^msize_i \] 其中 \(size_i\) 是第 \(i\) 个联通块的大小.原理就是考虑 \(prufer\) 编码,先把每个联通块看成一个点,那么序列中每出现一个第 \(i\) 联通块缩成的点,能连的边的数量是 \(size[i]\) ,所以序列每一位的方案数是 \(\sum size[i]=n\),考虑每一个点的度数是在序列中的出现次数\(+1\),所以对于每一个联通块还要补上一条连边的方案数.
然后这个题相当于就是确定了一条链,在剩下 \(n-i-2\) 个联通块的基础上求有标号生产树数量,其中 \(i\) 是 \(a,b\) 之间的点数,根据上面的式子,可以得到答案的式子
\[ ans = \sum_{i=0}^{n-2}\binom{m-1}{i}\binom{n-2}{i}\times i!\times n^{n-i-3}\times (i+2)\times m^{n-i-2} \]code
/*program by mangoyang*/#include#define inf (0x7f7f7f7f)#define Max(a, b) ((a) > (b) ? (a) : (b))#define Min(a, b) ((a) < (b) ? (a) : (b))typedef long long ll;using namespace std;template inline void read(T &x){ int ch = 0, f = 0; x = 0; for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = 1; for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - 48; if(f) x = -x;}#define int llconst int N = 10000005, mod = 1e9+7;int js[N], inv[N], n, m, a, b, ans;inline int Pow(int a, int b){ if(b == -1) b = mod - 2; int ans = 1; for(; b; b >>= 1, a = a * a % mod) if(b & 1) ans = ans * a % mod; return ans;}inline int C(int x, int y){ if(x < y) return 0; return js[x] * inv[y] % mod * inv[x-y] % mod; }signed main(){ read(n), read(m), read(a), read(b); js[0] = inv[0] = 1; for(int i = 1; i <= max(n, m); i++) js[i] = js[i-1] * i % mod, inv[i] = Pow(js[i], mod - 2); for(int i = 0; i <= n - 2; i++) (ans += C(m - 1, i) * C(n - 2, i) % mod * js[i] % mod * Pow(n, n - i - 3) % mod * (i + 2) % mod * Pow(m, n - i - 2) % mod) %= mod; cout << ans << endl; return 0;}