[UVA] 11719 - Gridland Airports
| I I U P C 2 0 0 9 | |
|
| |
| Problem G: Gridland Airports | |
|
| |
| The country ‘Gridland’ is a strange country which have R*C cities arranged in R rows and C columns. The bottom-left city is (1,1) and the upper-right city is (R,C).
The governor of ‘Gridland’ has hired you to assign some flight routes between the cities in ‘Gridland’. You have to establish minimum number of direct flight connections such that every pair of city is connected by a direct flight or some flight sequences. If a flight connection is established between two cities that can be used in both directions. But there is a restriction: a direct flight connection between two cities A(r1, c1) and B(r2, c2) can be established only if |r1-r2|+|c1-c2| == odd.
Find how many ways you can setup flight routes such that every pair of city is connected and the number of direct flight connections is minimum.
| |
| Input | |
| First line of input is T(≤5000) which is the number of cases. Then there are T lines each containing two numbers R, C and 2 ≤ R, C ≤ 10^8.
| |
| Output | |
| Output the number of ways to setup the flight route network. As the answer could be very big so output answer MOD (10^16+7).
| |
| Sample Input | Output for Sample Input |
| 2 2 2 49 49 | 4 1661809100947531 |
|
| |
| Problem Setter: Tasnim Imran Sunny Special Thanks: Md. Mahbubul Hasan, Md. Arifuzzaman Arif | |
在一個 RxC 的網格中，在限定條件下可以制定飛行航班。
問最小生成樹的個數。
題目解法：
by 八雲大神
將 (x,y) x+y 的奇偶性分成兩堆，恰好是 complete bipartite graph。
利用公式找到生成樹個數。
#include <stdio.h>
#define LL long long
LL modmultiply(LL a,LL b,LL c) {
LL x = 0,y = a%c;
while(b > 0) {
if(b%2 == 1) {
x = (x+y)%c;
}
y = (y*2)%c;
b /= 2;
}
return x%c;
}
LL modpow(LL x, LL y, LL mod) {
LL ret = 1;// ret = x^y%mod;
while(y) {
if(y&1)
//ret = (ret*x)%mod;
ret = modmultiply(ret, x, mod);
//x = (x*x)%mod;
x = modmultiply(x, x, mod);
y >>= 1;
}
return ret;
}
int main() {
LL MOD = 10000000000000007LL;
LL n, m, R, C;
int testcase;
scanf("%d", &testcase);
while(testcase--) {
scanf("%lld %lld", &R, &C);
m = R*C/2, n = R*C-m;
long long a1 = modpow(n, m-1, MOD);
long long b1 = modpow(m, n-1, MOD);
printf("%lld\n", modmultiply(a1, b1, MOD));
}
return 0;
}
import java.util.Scanner;
import java.math.BigInteger;
//complete bipartite graph
//a complete bipartite graph K(m,n) has m^(n-1) * n^(m-1) spanning trees.
public class Main {
public static void main(String[] args) {
int testcases;
BigInteger mod = BigInteger.valueOf(10000000000000007L);
Scanner cin = new Scanner(System.in);
testcases = cin.nextInt();
while (testcases-- != 0) {
long R, C, m, n;
R = cin.nextLong();
C = cin.nextLong();
m = R*C/2;
n = R*C-m;
BigInteger a = BigInteger.valueOf(m);
BigInteger b = BigInteger.valueOf(n);
BigInteger pa = a.modPow(b.subtract(BigInteger.ONE), mod);
BigInteger pb = b.modPow(a.subtract(BigInteger.ONE), mod);
BigInteger ret = pa.multiply(pb).mod(mod);
System.out.println(ret);
}
}
}