博物馆(museum)

这题求的是到某个点为终点的概率
以某个点为终点的概率可以是这个状态被进入的期望次数
即f[i][j]表示第一个人到i点 第二个人到j点的进入这个状态的期望次数
12
p是停留在某个点的概率 d是某个点的度数 S1 S2是初始状态
这个方程有环
所以用高斯消元做
把每个fij看成一个元 拿去解方程 即可出解

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <vector>
#include <functional>
#include <ctime>
#include <cstdlib>
#include <sstream>
#include <set>
#include <deque>
using namespace std;
typedef long long ll;
typedef long double ld;

struct line
{
    int to, next;
}li[1005];

int n, m, a, b, be[25], d[25], to[1005][2], fr[25][25], tot, l;
double p[25], v[405][405], ans[405];

void makeline(int fr, int to)
{
    ++l;
    li[l].next = be[fr];
    be[fr] = l;
    li[l].to = to;
}

int main()
{
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
    scanf("%d%d%d%d", &n, &m, &a, &b);
    for (int i = 0; i < m; ++i)
    {
        int fr, to;
        scanf("%d%d", &fr, &to);
        makeline(fr, to);
        makeline(to, fr);
        ++d[fr], ++d[to];
    }
    for (int i = 1; i <= n; ++i)
        scanf("%lf", &p[i]);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
        {
            fr[i][j] = tot;
            to[tot][0] = i, to[tot][1] = j;
            ++tot;
        }
    for (int i = 0; i < tot; ++i)
    {
        int u1 = to[i][0], u2 = to[i][1];
        v[i][i] = -1 ;
        if (u1 == u2) continue;
        v[i][i] += p[u1] * p[u2];
        double va1 = p[u1] * (1 - p[u2]) / d[u2],
                     va2 = (1 - p[u1]) * p[u2] / d[u1],
                     va = (1 - p[u1]) * (1 - p[u2]) / d[u1] / d[u2];

        for (int j1 = be[u2]; j1; j1 = li[j1].next)
            v[fr[u1][li[j1].to]][i] = va1;

        for (int j1 = be[u1]; j1; j1 = li[j1].next)
            v[fr[li[j1].to][u2]][i] = va2;

        for (int j1 = be[u1]; j1; j1 = li[j1].next)
            for (int j2 = be[u2]; j2; j2 = li[j2].next)
                v[fr[li[j1].to][li[j2].to]][i] = va;
    }
    v[fr[a][b]][tot] = -1;/*
    for (int i = 0; i < tot; ++i)
    {
        for (int j = 0; j <= tot; ++j) printf("%.2f ", v[i][j]);
        printf("\n");
    }*/

    for (int i = 0; i < tot; ++i)
    {
        int t = -1;
        for (int j = i; j < tot; ++j)
            if (t == -1 || abs(v[j][i]) > abs(v[t][i]))
                t = j;
        for (int j = 0; j <= tot; ++j)
            swap(v[i][j], v[t][j]);
        for (int j = i + 1; j < tot; ++j)
        {
            double va = v[j][i] / v[i][i];
            for (int k = i; k <= tot; ++k)
                v[j][k] -= va * v[i][k];
        }
    }
    for (int i = tot - 1; i >= 0; --i)
    {
        for (int j = i + 1; j < tot; ++j)
            v[i][tot] -= ans[j] * v[i][j];
        ans[i] = v[i][tot] / v[i][i];
    }/*
    for (int i = 0; i < tot; ++i)
        printf("%.6f ", ans[i]);
        printf("\n");*/

    for (int i = 1; i <= n; ++i)
        printf("%.6f ", ans[fr[i][i]] + 1e-8);
    fclose(stdin);fclose(stdout);
}

BZOJ 3451: Tyvj1953 Normal

考虑两个点a,b
a对b的删除时间有1的贡献当且仅当
在a到b的路径上的所有点中a是第一个删除的
这个有1/dist(a,b)的概率 对答案的贡献是1
所以这题就是求Σ1/(u,v)
这个可以用树分治做(233)
然后树分治合并两棵子树的f的时候要n^2的时间
这个可以fft优化到nlogn
总复杂度nlog^2n

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <vector>
#include <functional>
#include <ctime>
#include <cstdlib>
#include <sstream>
#include <set>
#include <deque>
using namespace std;
typedef long long ll;
typedef long double ld;

const int maxn = 300005;
const int P = (1 << 21) * 479 + 1;
const int G = 3;

struct line
{
    int to, next;
}li[maxn * 2];

int be[maxn], mx[maxn], f[maxn], b[maxn], fa[maxn], is[maxn], g[maxn][2], gt[maxn][2], d[maxn], br[maxn];
ll t1[maxn], t2[maxn], tt1[maxn], tt2[maxn];
int l, n, tot, tot1;
ld ans;
queue<int> q;
stack<int> s;
vector<int> v;

int getz(int now)
{
    int tot = 0, as = -1;
    for (q.push(now), b[now] = 1, fa[now] = -1; !q.empty(); )
    {
        int now = q.front();
        ++tot;
        q.pop();
        s.push(now);
        f[now] = mx[now] = 0;
        for (int i = be[now]; i; i = li[i].next)
        {
            int to = li[i].to;
            if (is[to] || b[to]) continue;
            fa[to] = now;
            b[to] = 1;
            q.push(to);
        }
    }
    for (; !s.empty(); )
    {
        int now = s.top();
        s.pop();
        b[now] = 0;
        ++f[now];
        if (fa[now] != -1)
            f[fa[now]] += f[now],
            mx[fa[now]] = max(mx[fa[now]], f[now]);
        mx[now] = max(mx[now], tot - f[now]);
        if (as == -1 || mx[as] > mx[now])
            as = now;
    }
    return as;
}

bool cmp(int a, int b)
{
    return f[a] < f[b];
}

int bitre(int a, int n)
{
    int ans = 0;
    for (int i = 0; i < n; ++i)
        ans += (1 << i) * ((a & (1 << (n - i - 1))) ? 1 : 0);
    return ans;
}

ll power(ll a, ll n)
{
    ll ans = 1;
    while (n)
    {
        if (n & 1) ans = (ans * a) % P;
        a = (a * a) % P;
        n >>= 1;
    }
    return ans;
}

void fnt(ll y[], const ll b[], ll n, ll rev = 1)
{
    ll len = 1 << n;
  for (ll i = 0; i < len; ++i)
    y[i] = b[bitre(i, n)];
    for (int i = 1; i <= n; ++i)
    {
        ll m = 1 << i;
        ll wn = power(G, (P - 1) / m);
        for (int j = 0; j < len; j += m)
        {
            ll w = 1;
            for (int k = j; k < j + m / 2; ++k)
            {
                ll u = y[k], v = (w * y[k + m / 2]) % P;
                y[k] = (u + v) % P, y[k + m / 2] = (u - v) % P;
                w = (w * wn) % P;
            }
        }
    }
    if (rev == 1) return;
    ll re = power(len, P - 2);
    for (int i = 0; i < len; ++i)
        y[i] = (y[i] * re % P + P) % P;
    reverse(y + 1, y + len);
}

void calc2(int v)
{
    int n, len;
    for (n = 0; (1 << n) < (v + 1) * 2; ++n);
    len = 1 << n;
    for (int i = 0; i < len; ++i)
        t1[i] = g[i][0] != tot1 ? 0 : g[i][1],
        t2[i] = gt[i][0] != tot ? 0 : gt[i][1];
    fnt(tt1, t1, n);
    fnt(tt2, t2, n);
    for (int i = 0; i < len; ++i) tt1[i] = (tt1[i] * tt2[i]) % P;
    fnt(t1, tt1, n, -1);
    for (int i = 2; i < len; ++i)
        ans += 1.0 / i * t1[i];
}

void calc(int now)
{
    getz(now);
    while (!v.empty()) v.pop_back();
    for (int i = be[now]; i; i = li[i].next)
        if (!is[li[i].to])
            v.push_back(li[i].to);
    sort(v.begin(), v.end(), cmp);
    ++tot1;
    for (int k = 0; k < v.size(); ++k)
    {
        int to = v[k];
        ++tot;
        for (q.push(to), br[to] = tot, d[to] = 1; !q.empty();)
        {
            int now = q.front();
            q.pop();
            if (gt[d[now]][0] != tot)
                gt[d[now]][0] = tot,
                gt[d[now]][1] = 0;
            ++gt[d[now]][1];
            for (int i = be[now]; i; i = li[i].next)
            {
                int to = li[i].to;
                if (br[to] == tot || is[to]) continue;
                br[to] = tot;
                d[to] = d[now] + 1;
                q.push(to);
            }
        }
        for (int i = 1; i <= f[to]; ++i)
        {
            if (gt[i][0] != tot) break;
            ans += 1.0 / (i + 1) * gt[i][1];
        }
        calc2(f[to] + 1);
        for (int i = 1; i <= f[to]; ++i)
        {
            if (g[i + 1][0] != tot1)
                g[i + 1][0] = tot1,
                g[i + 1][1] = 0;
            if (gt[i][0] != tot) break;
            g[i + 1][1] += gt[i][1];
        }
    }
}

void solve(int now)
{
    int z = getz(now);
    is[z] = 1;
    calc(z);
    for (int i = be[z]; i; i = li[i].next)
        if (!is[li[i].to])
            solve(li[i].to);
}

void makeline(int fr, int to)
{
    ++l;
    li[l].next = be[fr];
    be[fr] = l;
    li[l].to = to;
}

int main()
{
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
    scanf("%d", &n);
    for (int i = 1; i < n; ++i)
    {
        int fr, to;
        scanf("%d%d", &fr, &to);
        makeline(fr, to);
        makeline(to, fr);
    }
    solve(0);
    printf("%.4f", n + (double)ans * 2);
    fclose(stdin);fclose(stdout);
}

BZOJ 3450: Tyvj1952 Easy

对于连续的一段o
考虑第i个o
贡献的权值是2i-1
这样Σvi=n^2(1<= i <= n) 对所有n都有效 f[i]表示考虑前i个按键 期望收益是多少 问题是怎么转移呢0.0 显然f[i] = f[i - 1] + (i的期望收益) (根据期望可加) i的期望收益 枚举所有?的选择 设第j种选择最后有连续len[j]个o 一共m种选择 则i的期望收益为: ----------------------------- Σ(len[j] * 2 - 1) / m = (Σ(len[j]) / m) * 2 - 1 ----------------------------- Σ(len[j]) / m其实考虑前i位 最后连续的o的期望长度 这样就很简单了 g[i]表示前i为最后连续o的期望长度 然后就可以推了 但是如果长度为0 则按那个公式期望收益为0*2-1 = -1 显然是错的 要特判掉 怎么弄呢= = 可以从g[i - 1]转移 如果s[i] == 'x'就不管了 f[i] = f[i - 1] 如果s[i] == 'o'也不会有0的情况 直接转移即可 f[i] = f[i - 1] + g[i] * 2 - 1 如果s[i] == '?'那么有1/2的概率会长度为0则 f[i] = f[i - 1] + (g[i - 1] * 2 + 1) / 2即可(有1/2概率没收益)

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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <vector>
#include <functional>
#include <ctime>
#include <cstdlib>
#include <sstream>
#include <set>
#include <deque>
using namespace std;
typedef long long ll;
typedef long double ld;
 
const int maxn = 300005;
 
ld f[maxn], g[maxn];
int n;
 
int main()
{
    scanf("%d\n", &n);
    for (int i = 1; i <= n; ++i)
    {
        char c = getchar();
        if (c == 'x') f[i] = f[i - 1], g[i] = 0;
        if (c == 'o') g[i] =  g[i - 1] + 1, f[i] = f[i - 1] + g[i - 1] * 2 + 1;
        if (c == '?') g[i] = (g[i - 1] + 1) / 2, f[i] = f[i - 1] + g[i - 1] + 0.5;
    }
    printf("%.4f", (double)f[n]);
}

BZOJ 2752: [HAOI2012]高速公路(road)

这题应该不算严格的概率题。。
只是把总长度/方案数而已。。
根据期望可加(其实也可以就只是考虑每个收费站对答案的贡献)我们可以考虑对于每个收费站的期望 然后加起来
对于一个l~r之间的收费站i 对答案的贡献是(i – l + 1) * (r – i) * vi
把它化开 发现只要用线段树维护Σvi、Σi*vi、Σi*i*vi即可

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <vector>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <stack>
#include <iostream>
#include <algorithm>
#include <string>
#include <functional>
#include <sstream>
using namespace std;
typedef long long ll;
typedef long double ld;

const ll maxn = 100005;

struct node
{
  ll sum, sum1, sum2, lazy;
}t[maxn * 4];

ll sum[maxn], sum2[maxn], n, m;

void lazy(ll now, ll l, ll r)
{
  if (!t[now].lazy) return;
  ll p = t[now].lazy;
  t[now].lazy = 0;
  t[now].sum += (r - l + 1) * p;
  t[now].sum1 += (sum[r] - sum[l - 1]) * p;
  t[now].sum2 += (sum2[r] - sum2[l - 1]) * p;
  if (l == r) return;
  t[now * 2].lazy += p;
  t[now * 2 + 1].lazy += p;
}

void modify(ll l, ll r, ll now, ll lf, ll rt, ll v)
{
  lazy(now, l, r);
  if (l >= lf && r <= rt)
  {
    t[now].lazy += v;
    return;
  }
  ll mid = (l + r) / 2;
  if (lf <= mid) modify(l, mid, now * 2, lf, rt, v);
  if (rt >= mid + 1) modify(mid + 1, r, now * 2 + 1, lf, rt, v);
  lazy(now * 2, l, mid);
  lazy(now * 2 + 1, mid + 1, r);
  t[now].sum = t[now * 2].sum + t[now * 2 + 1].sum;
  t[now].sum1 = t[now * 2].sum1 + t[now * 2 + 1].sum1;
  t[now].sum2 = t[now * 2].sum2 + t[now * 2 + 1].sum2;
}

ll query(ll l, ll r, ll now, ll lf, ll rt)
{
  lazy(now, l, r);
  if (l >= lf && r <= rt) return (rt + lf - 1) * t[now].sum1 - t[now].sum2 - (lf * rt - rt) * t[now].sum;
  ll mid = (l + r) / 2, ans = 0;
  if (lf <= mid) ans += query(l, mid, now * 2, lf, rt);
  if (rt >= mid + 1) ans += query(mid + 1, r, now * 2 + 1, lf, rt);
  return ans;
}

ll gcd(ll a, ll b)
{
  return (!b) ? a : gcd(b, a % b);
}

int main()
{
  freopen("input.in", "r", stdin);
  freopen("output.out", "w", stdout);
  scanf("%lld%lld", &n, &m);
  for (ll i = 1; i <= n; ++i)
    sum[i] = sum[i - 1] + i, sum2[i] = sum2[i - 1] + (ll)i * i;
  for (ll i = 0; i < m; ++i)
  {
    char c;
    ll l, r;
    scanf("\n%c%lld%lld", &c, &l, &r);
    if (c == 'C')
    {
      ll v;
      scanf("%lld", &v);
      modify(1, n, 1, l, r - 1, v);
    }
    else
    {
      ll t = query(1, n, 1, l, r), k = (1 + (r - l)) * (r - l) / 2;
      ll g = gcd(t, k);
      printf("%lld/%lld\n", t / g, k / g);
    }
  }
  fclose(stdin);fclose(stdout);
}