http://acm.hdu.edu.cn/contests/contest_show.php?cid=884

1010 - Expectation

 

题意：给定一张无向图，AND生成树的权值为生成树上所有边的AND和，问这张图的生成树权值的数学期望。

遇到按位与的显然可以遍历每一位操作，由于最终要求总的权值和，所以遍历每一位，得到各自的权值和，再按照位加起来，就是总和。

求无向图的生成树个数用矩阵树定理，对于每一位重新建图，得到这一位的生成树个数。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const int N = 5e5 + 10;
const ll mod = 998244353;
int T;
ll K[110][110];
void add(int x, int y) {
    K[x][x]++;
    K[y][y]++;
    K[x][y]--;
    K[y][x]--;
}
ll gauss(int n) {
    ll res = 1ll;
    for (int i = 1; i <= n - 1; i++) {
        for (int j = i + 1; j <= n - 1; j++) {
            while (K[j][i]) {
                int t = K[i][i] / K[j][i];
                for (int k = i; k <= n - 1; k++)
                    K[i][k] = (K[i][k] - t * K[j][k] % mod + mod) % mod;
                swap(K[i], K[j]);
                res = -res;
            }
        }
        res = (res*K[i][i]) % mod;
    }
    return (res + mod) % mod;
}
int n, m;
struct E
{
    int u, v;
    ll w;
};
vector<E>es;
ll Pow(ll a, ll b) {
    ll res = 1ll;
    while (b) {
        if (b & 1)res = res * a%mod;
        a = a * a%mod;
        b >>= 1;
    }
    return res;
}
int main() {
    scanf("%d", &T);
    while (T--) {
        es.clear();
        scanf("%d%d", &n, &m);
        memset(K, 0, sizeof(K));
        for (int i = 1; i <= m; i++) {
            int u, v;
            ll w;
            scanf("%d%d%lld", &u, &v, &w);
            es.push_back(E{ u,v,w });
            add(u, v);
        }
        ll all = gauss(n);
        ll ans = 0ll;
        for (int i = 0; i <= 30; i++) {
            memset(K, 0, sizeof(K));
            for (E& e : es) {
                if ((e.w >> i) & 1)
                    add(e.u, e.v);
            }
            ans = (ans + gauss(n)*(1ll << i) % mod) % mod;
        }
        printf("%lld\n", ans*Pow(all, mod - 2) % mod);
    }
    return 0;
}

 

1005 - Fragrant numbers

 

题意：S串为1145141919不断重复拼成的无限串，要找出一个最短的S的前缀，在任意位置插入 括号，+，*，得到一个算式，结果为 n。

区间dp

dp[l][r][val]dp[l][r][val] 表示 能否用 ll 到 rr 拼出 valval。转移方程就是普通的区间dp。最后遍历 dp[1][r]dp[1][r] 得到结果。

复杂度是 n5n^5。但是打表可以发现结果最多是 12，所以可以大胆猜测最终的长度不会太大，所以把边界设为12，则复杂度变为 123n212^3n^2，再看其实不用每次都遍历 val，只要用一个 set 维护 dp[l][r]dp[l][r] 所有可以拼出的数字即可，这些数字个数很少。

果然复杂度还是玄学。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const int N = 5e5 + 10;
const ll mod = 998244353;
int T;
int n;
int num[20][10], a[N];
int mp[]{ 0,1,1,4,5,1,4,1,9,1,9,1,1,4,5,1,4,1,9,1,9 };
unordered_set<int>st[20][10];
int main() {
	memset(a, -1, sizeof(a));
	for (int i = 1; i <= 12; i++) {
		num[i][1] = mp[i];
		for (int j = 2; j <= 4; j++) {
			num[i][j] = num[i][j - 1] * 10 + mp[i + j - 1];
		}
	}
	for (int len = 1; len <= 12; len++) {
		for (int l = 1; l + len - 1 <= 12; l++) {
			int r = l + len - 1;
			if (len <= 4)st[l][r].insert(num[l][len]);
			for (int i = l; i < r; i++) {
				for (int u : st[l][i]) {
					for (int v : st[i + 1][r]) {
						if (u + v <= 5000)st[l][r].insert(u + v);
						if (u * v <= 5000)st[l][r].insert(u * v);
					}
				}
			}
		}
	}
	for (int r = 1; r <= 12; r++) {
		for (int u : st[1][r]) {
			if (a[u] == -1)a[u] = r;
		}
	}
	scanf("%d", &T);
	while (T--) {
		scanf("%d", &n);
		printf("%d\n", a[n]);
	}
	return 0;
}