BestCoder Round #40

4/4

弱渣做不动CF了，弱渣只能水水BC了，于是就开始每周开心地BC了，顺便写个水水的题解~~

题A hdu 5224

题意：略

题解：枚举边长即可。

 1 /*zhen hao*/
 2 #include 
 3 using namespace std;
 4 
 5 #define lson l, m, rt*2
 6 #define rson m + 1, r, rt*2+1
 7 #define xx first
 8 #define yy second
 9 
10 typedef pair<int,int> pii;
11 typedef long long ll;
12 typedef unsigned long long ull;
13 
14 int main() {
15 //  freopen("case.in", "r", stdin);
16   int T;
17   cin >> T;
18   while (T--) {
19     int n;
20     scanf("%d", &n);
21     int ans = 1 << 30;
22     for (int i = 1; i * i <= n; i++) {
23       if (n % i == 0) {
24         ans = min(ans, 2 * (i + n / i));
25       }
26     }
27     printf("%d\n", ans);
28   }
29   return 0;
30 }

题B hdu 5225

题意：略

题解：可以用递推算出每个大小为n的排列的逆序对总数，就是考虑每次增加n之后逆序对数增加多少，分别把n放在第一个位置……第n个位置。得到s[n]；然后就是对于一个排列运用类似的方法，不断细化，想数位dp得到答案的过程一样。具体是这样，我也不知道怎么水出来的~~

 1 /*zhen hao*/
 2 #include 
 3 using namespace std;
 4 
 5 #define lson l, m, rt*2
 6 #define rson m + 1, r, rt*2+1
 7 #define xx first
 8 #define yy second
 9 
10 typedef pair<int,int> pii;
11 typedef long long ll;
12 typedef unsigned long long ull;
13 
14 const int mod = 1e9 + 7, maxn = 1e2 + 10;
15 int p[maxn], vis[maxn], n;
16 ll s[maxn], f[maxn];
17 
18 void init() {
19   f[1] = 1; s[1] = 0;
20   for (int i = 2; i < maxn; i++) {
21     f[i] = f[i - 1] * i % mod;
22     s[i] = (s[i - 1] * i % mod + f[i - 1] * i * (i - 1) / 2) % mod;
23   }
24 //  cout << s[5] << endl;
25 }
26 
27 ll slove() {
28   ll ret = 0;
29   memset(vis, 0, sizeof vis);
30   ll big = 0;
31   for (int i = 1; i <= n; i++) {
32     for (int j = 1; j < p[i]; j++) if (!vis[j]) {
33       ll extra = 0;
34       for (int k = 1; k < j; k++) if (!vis[k]) extra++;
35       ret += ((big + extra) * f[n - i] + s[n - i]) % mod;
36       if (ret >= mod) ret -= mod;
37     }
38     for (int j = 1; j < p[i]; j++) if (!vis[j]) big++;
39     vis[p[i]] = 1;
40   }
41   return ret;
42 }
43 
44 int main() {
45 //  freopen("case.in", "r", stdin);
46   init();
47   while (scanf("%d", &n) == 1) {
48     for (int i = 1; i <= n; i++) scanf("%d", p + i);
49     printf("%I64d\n", slove());
50   }
51   return 0;
52 }

题C hdu 5226

题意：略

题解：先说一下我的做法，对于一个组合数可以写成c(a, b) = c(a - 1, b - 1) + c(a - 1, b)，所以上一行是下一行乘以2再减去最右端的（只加了一次），所以可以递推过去。然后就是这道题的一个坑点：不能直接求逆元。为什么呢？因为假设分子的p因子的个数更多，那么modp之后得到的就是0，所以这时候求逆元就不准了，究其原因就是因为gcd！=1，所以不能够求逆元，除去这种情况是可以的，因为p是素数。解决方法有两种：

1、lucas定理，因为是以p为一次划分，所以可以很有效地避免。

2、要求a！/ (b ！ * （a - b）！)，所以求出num[a]表示a！有多少个p，然后只要num[a] - num[b] - num[a - b] > 0就直接是0，其余就可以用逆元来处理。

最后官方并不需要我那样递推过去，而是用一个性质：C（x + 1，y）即为∑x C（i，y），具体可以联系杨辉三角来证。

 1 /*zhen hao*/
 2 #include 
 3 using namespace std;
 4 
 5 #define lson l, m, rt*2
 6 #define rson m + 1, r, rt*2+1
 7 #define xx first
 8 #define yy second
 9 
10 typedef pair<int,int> pii;
11 typedef long long ll;
12 typedef unsigned long long ull;
13 
14 const int maxn = 2e5 + 10;
15 ll p;
16 ll f[maxn], c[maxn];
17 
18 ll quick(ll a, ll b) {
19   ll ret = 1;
20   while (b > 0) {
21     if (b & 1) ret = ret * a % p;
22     a = a * a % p;
23     b = b / 2;
24   }
25   return ret;
26 }
27 
28 void init() {
29   f[0] = 1;
30   for (int i = 1; i < maxn; i++) f[i] = f[i - 1] * i % p;
31   for (int i = 0; i < maxn; i++) c[i] = quick(f[i], p - 2);
32 }
33 
34 ll C(int n, int m) {
35   if(n == 0 && m == 0) return 1;
36   if(n == 0) return 0;
37   if(n % p < m % p) return 0;
38   int x = n % p, y = m % p;
39   return f[x] * c[y] % p * c[x-y] % p * C(n / p, m / p);
40 }
41 
42 ll slove(int x, int y) {
43   if (x < 0 || y < 0) return 0;
44   ll ret = 1  , s = 1;
45   for (int i = 1; i <= x; i++) {
46     s = (s * 2 % p - C(i - 1, y)) % p;
47     ret = (ret + s) % p;
48   }
49   return (ret + p) % p;
50 }
51 
52 int main() {
53 //  freopen("case.in", "r", stdin);
54   int x1, x2, y1, y2;
55   while (scanf("%d%d%d%d%I64d", &x1, &y1, &x2, &y2, &p) != EOF) {
56     init();
57     ll ans1 = (slove(x2, y2) + slove(x1 - 1, y1 - 1)) % p;
58     ll ans2 = ((slove(x1 - 1, y2)) + slove(x2, y1 - 1)) % p;
59     ll ans = (ans1 - ans2) % p;
60     printf("%I64d\n", (ans + p) % p);
61   }
62   return 0;
63 }

题D hdu 5227

题意：给你四元对（t，a，b，k），满足下面条件就是合法的：

1、 1 <= a, b, k <= t

2、 gcd（a，b） >= k

然后给你一颗树，每个点表示一个四元对，随机选两个点，然后这路径上的点就是来玩游戏的点，玩游戏的方法就是每次选一个四元对，然后变成一个更小的合法四元对，然后最后不能操作者输，现在让你算出有多少种选法是必败的？

题解：很容易想到nim，每个四元对当做一堆石头，个数就是比它小的四元对个数，然后假设知道之后我们知道一条路径的异或值为0就是必败的，所以就转化成树分治的求异或值为0的路径数量，这个比较简单，所以本题就难在求比当前四元对小的合法的四元对的数量。

求这个东西太难了，要参考贾志鹏线性筛，以后再学吧，先套个公式吧 ！！

  1 /*zhen hao*/
  2 #include 
  3 using namespace std;
  4 
  5 #define lson l, m, rt*2
  6 #define rson m + 1, r, rt*2+1
  7 #define xx first
  8 #define yy second
  9 
 10 typedef pair<int,int> pii;
 11 typedef long long ll;
 12 typedef unsigned long long ull;
 13 
 14 const int maxn = 1e4 + 10;
 15 int head[maxn], e = 0, n;
 16 ll phi[maxn], v[maxn], val[maxn];
 17 
 18 struct Edge {
 19   int v, nx;
 20 } edges[maxn * 2];
 21 
 22 ll get(int n, int m) {
 23   if (n > m) swap(n, m);
 24   ll ret = 0;
 25   for (int i = 1, j; i <= n; i = j + 1) {
 26     j = min(n / (n / i), m / (m / i));
 27     ret += 1ll * (phi[j] - phi[i - 1]) * (n / i) * (m / i);
 28   }
 29   return ret;
 30 }
 31 
 32 void phi_table() {
 33   phi[1] = 1;
 34   for (int i = 2; i < maxn; i++) if (!phi[i])
 35     for (int j = i; j < maxn; j += i) {
 36       if (!phi[j]) phi[j] = j;
 37       phi[j] = phi[j] / i * (i - 1);
 38     }
 39   for (int i = 1; i < maxn; i++) phi[i] += phi[i - 1];
 40   for (int i = 1; i < maxn; i++) v[i] = v[i - 1] + get(i, i);
 41 }
 42 
 43 void init() {
 44   e = 0;
 45   memset(head, -1, sizeof head);
 46 }
 47 
 48 void add_edge(int u, int v) {
 49   edges[e] = (Edge){v, head[u]};
 50   head[u] = e++;
 51 }
 52 
 53 int sz[maxn], vis[maxn];
 54 
 55 void dfs_s(int u, int p) {
 56   sz[u] = 1;
 57   for (int i = head[u]; ~i; i = edges[i].nx) {
 58     int v = edges[i].v;
 59     if (v == p || vis[v]) continue;
 60     dfs_s(v, u);
 61     sz[u] += sz[v];
 62   }
 63 }
 64 
 65 int dp[maxn];
 66 
 67 void dfs_t(int& s, int u, int p, int cnt) {
 68   dp[u] = 0;
 69   for (int i = head[u]; ~i; i = edges[i].nx) {
 70     int v = edges[i].v;
 71     if (v == p || vis[v]) continue;
 72     dfs_t(s, v, u, cnt);
 73     dp[u] = max(dp[u], sz[v]);
 74   }
 75   dp[u] = max(dp[u ], cnt - sz[u]);
 76   if (s == -1 || dp[u] < dp[s]) s = u;
 77 }
 78 
 79 ll c1[maxn]; int c;
 80 
 81 void dfs_c(int u, int p, ll d) {
 82   c1[c++] = d;
 83   for (int i = head[u]; ~i; i = edges[i].nx) {
 84     int v = edges[i].v;
 85     if (v == p || vis[v]) continue;
 86     dfs_c(v, u, d ^ val[v]);
 87   }
 88 }
 89 
 90 mapint>::iterator it;
 91 
 92 ll slove(int s) {
 93   dfs_s(s, -1);
 94   int cnt = sz[s], t = s;
 95   s = -1;
 96   dfs_t(s, t, -1, cnt);
 97   vis[s] = 1;
 98   ll ret = 0;
 99   if (!val[s]) ret++;
100   mapint> mp;
101   for (int i = head[s]; ~i; i = edges[i].nx) {
102     int v = edges[i].v;
103     if (vis[v]) continue;
104     c = 0;
105     dfs_c(v, s, val[v]);
106     for (int j = 0; j < c; j++) {
107       if ((c1[j] ^ val[s]) == 0) ret += 2;
108       it = mp.find(c1[j] ^ val[s]);
109       if (it != mp.end()) ret += (*it).yy * 2;
110     }
111     for (int j = 0; j < c; j++) mp[c1[j]]++;
112   }
113   for (int i = head[s]; ~i; i = edges[i].nx) {
114     int v = edges[i].v;
115     if (vis[v]) continue;
116     ret += slove(v);
117   }
118   return ret;
119 }
120 
121 ll gcd(ll a, ll b) {
122   if (!b) return a;
123   return gcd(b, a % b);
124 }
125 
126 int main() {
127 //  freopen("case.in", "r", stdin);
128   phi_table();
129   while (scanf("%d", &n) == 1) {
130     init();
131     for (int i = 1; i < n; i++) {
132       int u, v;
133       scanf("%d%d", &u, &v);
134       add_edge(u, v); add_edge(v, u);
135     }
136     for (int i = 1; i <= n; i++) {
137       int a, b, c, d;
138       scanf("%d%d%d%d", &a, &b, &c, &d);
139       val[i] = v[a - 1] + d - 1;
140       val[i] += get(b - 1, a);
141       val[i] += get(b, c - 1) - get(b - 1, c - 1);
142     }
143     memset(vis, 0, sizeof vis);
144     ll a = 1ll * n * n - slove(1), b = 1ll * n * n;
145     if (!a) puts("0/1");
146     else {
147       ll d = gcd(a, b);
148       printf("%I64d/%I64d\n", a / d, b / d);
149     }
150   }
151   return 0;
152 }