BestCoder Round #85
5/5
好久没写博客了，难得有空写个题解，难得有空补不动~~
题A hdu5776 sum
题意：略
题解：dp[x]表示前缀modm的余数有没有出现，如果同一个结果出现两次，那么就说明中间的一段是可以整除m的，当然不要忘了本身前缀就能够整除。
1 /*zhen hao*/
2 #include
3 #include
4 #include
5 #include
6 #include
7 #include <string>
8 #include
9 #include <set>
10 #include
代码君
题B hdu5777 domino
题意：略
题解：仔细观察发现贪心可解，sort一下即可。
1 /*zhen hao*/
2 #include
3 #include
4 #include
5 #include
6 #include
7 #include <string>
8 #include
9 #include <set>
10 #include
代码君
题C hdu5778 abs
题意：略
题解：质因子都是2说明这个数一定是平方数，然后对于x，我们先把它去个根的sx，然后我们枚举距离这个sx最近的距离d，然后判断d的质因子是不是都是一个。还有一个问题，我们取得这个sx可能sx+1更优，所以要先判断一下哪个距离x更近。
1 /*zhen hao*/
2 #include
3 #include
4 #include
5 #include
6 #include
7 #include <string>
8 #include
9 #include <set>
10 #include
代码君
题D 5779 Tower Defence
题意：略
题解：太弱了，第一眼看不到题解的状态转移，实际上题解的状态转移描述得已经够专业了。但是我是结合代码才看得懂(/▽╲)！！这里详细地解释一下怎么转移的吧，毕竟都把代码看懂了。
题目说最短路不是k，很容易由反证法得到这个最短路是小于k的。
先定义一个状态数组，f(i,j,k)表示与1连接的那个连通块（包括1）的size，当前的最短路是j，得到这个最短路的点数是k。
我们发现如果想要最短路的长度加一，那么必须是从非连通块里面的点连到这k个点的其中x个(1 <= x <= k)，所以我们要枚举接下来的连通块以外的新点的个数x，目的是更新状态f(i+x,j+1,x)。
转移：（假设上一层是k个点，下一层是x个点）
（1）对于第二层的每个点x，从第一层的k个点里面人选1到k个连边，方法数是2 ^ k - 1。
（2）对于第二层的每个点x自己互相连边，方案数是2 ^ (x * (x - 1) / 2)，因为共有这么条边，可以连也可以不连
（3）这个最难想，因为我们增加了x个点，那么原来图中有多少个点是可以换位置的呢？答案就是非1和非最短路为j的点，所以由i - k - 1个点里面选x作为最短路为j+1的点。
这三步我们得到了f(i,j,k)。
给定n和k怎么得到答案呢？枚举与1连通的点，然后剩余的点可以乱排，同样要考虑排列组合。
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 N = 61, mod = 1e9 + 7;
15 ll f[N][N][N], C[N][N], p2[N * N], p2_1[N];
16
17 void add(ll& a, ll b) {
18 a += b;
19 if (a >= mod) a -= mod;
20 }
21
22 void init() {
23 for (int i = 0; i < N; i++) {
24 C[i][0] = 1;
25 for (int j = 1; j <= i; j++)
26 add(C[i][j], (C[i - 1][j] + C[i - 1][j - 1]) % mod);
27 }
28 // cout << C[5][3] << endl;
29 p2[0] = p2_1[0] = 1;
30 for (int i = 1; i < N * N; i++) p2[i] = p2[i - 1] * 2 % mod;
31 for (int i = 1; i < N; i++) p2_1[i] = (p2[i] + mod - 1) % mod;
32 // cout << p2[5] << ' ' << p2_1[5] << endl;
33 f[1][0][1] = 1;
34 for (int i = 1; i < N; i++)
35 for (int j = 0; j < i; j++)
36 for (int k = 1; k <= i; k++) if (f[i][j][k]) {
37 ll tmp = f[i][j][k];
38 for (int l = 1; l + i < N; l++) {
39 tmp = tmp * p2_1[k] % mod;
40 ll val = tmp;
41 val = val * p2[l * (l - 1) / 2] % mod;
42 val = val * C[i + l - 1][l] % mod;
43 add(f[i + l][j + 1][l], val);
44 }
45 }
46 }
47
48 ll get_ans(int n, int k) {
49 ll ans = 0;
50 for (int i = 1; i <= n; i++)
51 for (int j = 0; j < k; j++)
52 for (int l = 1; l <= i; l++) if (f[i][j][l]) {
53 ll tmp = f[i][j][l];
54 tmp = tmp * C[n - 1][n - i] % mod;
55 tmp = tmp * p2[(n - i) * (n - i - 1) / 2] % mod;
56 add(ans, tmp);
57 }
58 return ans;
59 }
60
61 int main() {
62 // freopen("case.in", "r", stdin);
63
64 init();
65 int T;
66 cin >> T;
67 while (T--) {
68 int n, k;
69 cin >> n >> k;
70 cout << get_ans(n, k) << '\n';
71 }
72
73 return 0;
74 }
代码君
题E hdu5780 gcd
题意：略
题解：实际上官方题解已经写得很详细了，我再复述有点多余(/▽╲)改天有空补上这个公式证明吧，希望我不会忘记。
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 N = 1e6, mod = 1e9 + 7;
15 int phi[N + 10];
16 ll s[N + 10];
17
18 void phi_table() {
19 phi[1] = 1;
20 for (int i = 2; i <= N; i++) if (!phi[i])
21 for (int j = i; j <= N; j += i) {
22 if (!phi[j]) phi[j] = j;
23 phi[j] = phi[j] / i * (i - 1);
24 }
25 for (int i = 1; i <= N; i++)
26 s[i] = (s[i - 1] + phi[i]) % mod;
27 }
28
29 ll quick(ll a, ll b, ll c) {
30 ll ret = 1;
31 while (b > 0) {
32 if (b & 1) ret = ret * a % c;
33 b = b / 2;
34 a = a * a % c;
35 }
36 return ret;
37 }
38
39 ll get_ans(int x, int n) {
40 if (x == 1) return 0ll;
41 ll ret = 0;
42 ll inv = quick(x - 1, mod - 2, mod);
43 for (int i = 1, j; i <= n; i = j + 1) {
44 j = n / (n / i);
45 ll sd = 2ll * s[n / i] - 1;
46 ll a0 = quick(x, i, mod), qn = quick(x, j - i + 1, mod) + mod - 1;
47 ll tmp = a0 * qn % mod;
48 tmp = tmp * inv % mod;
49 tmp = (tmp + mod - (j - i + 1)) % mod;
50 tmp = sd * tmp % mod;
51 ret += tmp;
52 if (ret >= mod) ret -= mod;
53 }
54 return ret;
55 }
56
57 int main() {
58 // freopen("case.in", "r", stdin);
59
60 phi_table();
61 int T;
62 cin >> T;
63 while (T--) {
64 int x, n;
65 scanf("%d%d", &x, &n);
66 cout << get_ans(x, n) << endl;
67 }
68
69 return 0;
70 }
代码君