avatar
文章
24
标签
19
首页
时间轴
标签
友链
关于
ruogu's blog
首页
时间轴
标签
友链
关于
杂题（三）
阅读量:|评论数:

uoj516 矩阵乘法

http://uoj.ac/problem/516

这题我不会。。看了别人代码才会。

考虑fif_i表示后s[i..n]s[i..n]形成的字符串，那么fi=fi+1+si+fi+1f_i=f_{i+1}+s_i+f_{i+1}，其中++表示拼接。

那么考虑转化成类似子序列自动机形式，或者可以说直接转化成矩阵，就直接如上面的柿子一样乘一下就行。

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
//Author:xht37
#include <bits/stdc++.h>

#define ui unsigned int
#define ll long long
#define ul unsigned ll
#define ld long double

#define pi pair< int, int >
#define fi first
#define se second
#define mp make_pair

#define ls (p << 1)
#define rs (ls | 1)
#define md ((t[p].l + t[p].r) >> 1)

#define pq priority_queue
#define pb push_back
#define vi vector< int >
#define si set< int >::iterator

#define fl(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout);

using namespace std;

namespace io {
	const int SI = 1 << 21 | 1;
	char IB[SI], *IS, *IT, OB[SI], *OS = OB, *OT = OS + SI - 1, c, ch[100];
	int f, t;
	#define gc() (IS == IT ? (IT = (IS = IB) + fread(IB, 1, SI, stdin), IS == IT ? EOF : *IS++) : *IS++)
	inline void flush() {
		fwrite(OB, 1, OS - OB, stdout), OS = OB;
	}
	inline void pc(char x) {
		*OS++ = x;
		if (OS == OT) flush();
	}
	template<class I>
	inline void rd(I &x) {
		for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
		for (x = 0; c >= '0' && c <= '9'; x = (x << 3) + (x << 1) + (c & 15), c = gc());
		x *= f;
	}
	inline void rds(char *s, int &x) {
		for (c = gc(); c < 33 || c > 126; c = gc());
		for (x = 0; c >= 33 && c <= 126; s[++x] = c, c = gc());
		s[x+1] = '\0';
	}
	template<class I>
	inline void print(I x, char k = '\n') {
		if (!x) pc('0');
		if (x < 0) pc('-'), x = -x;
		while (x) ch[++t] = x % 10 + '0', x /= 10;
		while (t) pc(ch[t--]);
		pc(k);
	}
	struct Flush {
		~Flush() {
			flush();
		}
	} flusher;
}
using io::rd;
using io::rds;
using io::print;

namespace Rd {
	inline bool gt() {
		int a = rand(), b = rand();
		while (a == b) a = rand(), b = rand();
		return a < b;
	}
	template<class I>
	inline I Rand(I k) {
		if (!k) return 0;
		I w = 1;
		while (w < k) w <<= 1;
		while (w >= k) {
			I o = 1, x = 0;
			while (o < k) o <<= 1, x = (x << 1) + gt();
			w = x;
		}
		return w;
	}
	template<class I>
	inline I rdm(I l, I r) {
		return l + Rand(r - l + 1);
	}
	template<class I>
	inline void rdms(I *a, int n) {
		pair< int, I > p[n+1];
		map< int, bool > m;
		m.clear();
		for (int i = 1; i <= n; i++) {
			int o = rdm(0, 1000000000);
			while (m[o]) o = rdm(0, 1000000000);
			m[o] = 1;
			p[i] = mp(o, a[i]);
		}
		sort(p + 1, p + n + 1);
		for (int i = 1; i <= n; i++) a[i] = p[i].se;
	}
}
using Rd::gt;
using Rd::rdm;
using Rd::rdms;

namespace kc {
	template<class I>
	inline I Min(I x, I y) {
		return x < y ? x : y;
	}
	template<class I>
	inline I Max(I x, I y) {
		return x > y ? x : y;
	}
	template<class I>
	inline void Swp(I &x, I &y) {
		x ^= y ^= x ^= y;
	}
	template<class I>
	inline I Abs(I x) {
		return x >= 0 ? x : -x;
	}
}
using kc::Min;
using kc::Max;
using kc::Swp;
using kc::Abs;

namespace Md {
	const int P = 998244353;
	inline int Add(int a, int b) {
		return a + b >= P ? a + b - P : a + b;
	}
	inline int Sub(int a, int b) {
		return a - b < 0 ? a - b + P : a - b;
	}
	inline int Mul(int a, int b) {
		return 1ll * a * b % P;
	}
	inline int ksm(int a, ll b = P - 2) {
		b %= P - 1;
		int c = 1;
		while (b) {
			if (b & 1) c = Mul(c, a);
			a = Mul(a, a), b >>= 1;
		}
		return c;
	}
	inline int Div(int a, int b) {
		return 1ll * a * ksm(b) % P;
	}
}
using Md::Add;
using Md::Sub;
using Md::Mul;
using Md::Div;
using Md::ksm;

const int N = 2e3 + 7, M = 27;
int n, ans;
char s[N];

struct Mat {
	int a[M][M];
	inline Mat() {
		memset(a, 0, sizeof(a));
	}
	inline friend Mat operator * (Mat a, Mat b) {
		Mat c = Mat();
		for (int i = 0; i < M; i++)
			for (int k = 0; k < M; k++)
				for (int j = 0; j < M; j++)
					c.a[i][j] = Add(c.a[i][j], Mul(a.a[i][k], b.a[k][j]));
		return c;
	}
} x, a[M];

int main() {
	rd(n), rds(s, n), x = Mat();
	for (int i = 0; i < M; i++) x.a[i][i] = 1;
	for (int i = 0; i < M - 1; i++)
		for (int j = 0; j < M; j++)
			if (i ^ j) a[i].a[j][j] = 1;
			else for (int k = 0; k < M; k++)
				a[i].a[i][k] = 1;
	for (int i = n; i; i--) x = x * a[s[i]-'a'] * x;
	for (int i = 0; i < M - 1; i++) ans = Add(ans, x.a[i][26]);
	print(ans);
	return 0;
}

（复制了别人代码，侵删）


nowcoder 5555a 动态规划

https://ac.nowcoder.com/acm/contest/5555/A

首先要把m\sqrt{m}拆成k∏pik\sqrt{\prod{p_i}}的形式。这时就是mm划分成nn个的方案数。n,m≤1000n,m\leq 1000

我tm写了个按m\sqrt{m}分类的方法，竟然过了。。

正解是考虑加一个数或者整体加11。

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
#include <bits/stdc++.h>
#define ld double
#define ull unsigned long long
#define ll long long
#define pii pair <int, int>
#define iiii pair <int, pii >
#define mp make_pair
#define INF 1000000000
#define rep(i, x) for(int (i) = 0; (i) < (x); (i)++)
inline int getint() {
  int x = 0, p = 1; char c = getchar();
  while (c <= 32) c = getchar();
  if (c == 45) p = -p, c = getchar();
  while (c > 32) x = x * 10 + c - 48, c = getchar();
  return x * p;
}
using namespace std;
const int mod = 998244353;
inline void reduce(int &x) { x += x >> 31 & mod; }
inline int mul(int x, int y) { return 1ll * x * y % mod; }
//ruogu_alter
const int N = 1005;
int g[N][N], f[N][N], n, m;
//
int main() {
  n = getint(); m = getint(); int val = 1;
  for (int i = 2; i * i <= m; i++) {
    if (m % (i * i)) continue;
    while (m % (i * i) == 0) m /= (i * i), val *= i;
  }
  m = val;
  f[0][0] = 1;
  for (int i = 0; i <= min(35, m); i++) {
    for (int j = 1; j <= n; j++) {
      for (int k = i; k <= m; k++) {
        reduce(f[j][k] += f[j - 1][k - i] - mod);
      }
    }
  }
  g[0][0] = 1;
  for (int i = 36; i <= m; i++) {
    for (int j = 1; j <= min(n, 35); j++) {
      for (int k = i; k <= m; k++) {
        reduce(g[j][k] += g[j - 1][k - i] - mod);
      }
    }
  }
  int res = 0;
  rep(i, n + 1) rep(j, m + 1) reduce(res += mul(f[i][j], g[n - i][m - j]) - mod);
  cout << res << endl;
  return 0;
}

nowcoder 5555b 数据结构

https://ac.nowcoder.com/acm/contest/5555/B

考试的时候，我想了许多种不同的没有考虑随机数的方法，大概是小常数的O(nlog⁡2n)O(n\log^2n)，但是都是mlemle，大抵都要维护哈希表。

其实发现对于每1616位分一块的话，必然有一块是完全相同的。就插入到vectorvector里就很轻易的过了。。awsl

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
#include<bits/stdc++.h>
#define fo(i, x, y) for(int i = x, _b = y; i <= _b; i ++)
#define ff(i, x, y) for(int i = x, _b = y; i <  _b; i ++)
#define fd(i, x, y) for(int i = x, _b = y; i >= _b; i --)
#define ll long long
#define pp printf
#define hh pp("\n")
using namespace std;
 
int n, m;
 
#define ull unsigned long long
 
ull G(ull x) {
    x^=x<<13;
    x^=x>>7;
    x^=x<<17;
    return x;
}
 
const int N = 1e6 + 5;
 
ull a[N];
 
ull x;
 
vector<int> d[4][1 << 16];
 
ull zh(ull x, int y) {
    return x >> (16 * y) & 65535;
}
 
#define low(x) ((x) & -(x))
 
int pd(ull x, ull y) {
    x ^= y;
    int s = 0;
    for(; x && s <= 3; x -= low(x))   s ++;
    return s <= 3;
}
 
const int mo = 998244353;
 
ll ans;
 
int main() {
//  freopen("a.in", "r", stdin) ;
    scanf("%d %d", &n, &m);
    scanf("%llu", &a[0]);
    fo(i, 1, n) a[i] = G(a[i - 1]);
    fo(i, 0, n - 1) {
        fo(j ,0, 3) {
            d[j][zh(a[i], j)].push_back(i);
        }
    }
    fo(i, 1, m)  {
        scanf("%llu", &x);
        int ye = 0;
        fo(j ,0, 3) {
            int v = zh(x, j);
            ff(k, 0, d[j][v].size()) {
                int y = d[j][v][k];
                if(pd(x, a[y])) {
                    ye = 1; break;
                }
            }
            if(ye) break;
        }
        ans = (ans * 2 + ye) % mo;
    }
    pp("%lld\n", ans);
}

侵删


loj2305 2-sat

我竟然一时半会想不清楚2-sat怎么输出方案。。直到看了板子。

有两个注意点：

1.1.tarjan获得的顺序反过来就是拓扑序；

2.2.就是要求尽可能取拓扑序大的然后判一下合不合法。

然后就是考虑这个三进制的状态其实用二进制枚举就已经可以包含所有情况了。复杂度是O(n2d)O(n2^d)。

注意这题现场没有spj，所以可能需要自己手写一个spj。但是这题的spj应该不算太难写。

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
#include <bits/stdc++.h>
#define ld double
#define ull unsigned long long
#define ll long long
#define pii pair<int, int>
#define iiii pair<int, pii>
#define mp make_pair
#define INF 1000000000
#define rep(i, x) for (int(i) = 0; (i) < (x); (i)++)
inline int getint() {
    int x = 0, p = 1;
    char c = getchar();
    while (c <= 32) c = getchar();
    if (c == 45)
        p = -p, c = getchar();
    while (c > 32) x = x * 10 + c - 48, c = getchar();
    return x * p;
}
using namespace std;
const int mod = 1e9 + 7;
inline void reduce(int &x) { x += x >> 31 & mod; }
inline int mul(int x, int y) { return 1ll * x * y % mod; }
// ruogu_alter
mt19937 rnd(time(0));
vector<pii> ex, ey;
const int N = 1e5 + 5;
int n, m, a[N], dfn[N], low[N], c, cnt, blo[N];
bool inst[N];
vector<int> st, g[N];
char s[N];
vector<int> v;
//
void tarjan(int x) {
    dfn[x] = low[x] = ++cnt;
    inst[x] = true;
    st.emplace_back(x);
    for (int to : g[x]) {
        if (!dfn[to]) {
            tarjan(to);
            low[x] = min(low[x], low[to]);
        } else if (inst[to]) {
            low[x] = min(low[x], dfn[to]);
        }
    }
    if (low[x] == dfn[x]) {
        ++c;
        int y = -1;
        while (y != x) {
            blo[y = st.back()] = c;
            st.pop_back();
            inst[y] = false;
        }
    }
}
inline void add(int x, int y) { g[x].emplace_back(y); }
inline int getid(int x, int y) { return (y - (y >= a[x])) * n + x; }
inline int op(int x) { return x < n ? x + n : x - n; }
void solve() {
    rep(i, n + n) g[i].clear();
    cnt = c = 0;
    rep(i, m) {
        int x = ex[i].first, xx = ex[i].second, vx = getid(x, xx);
        int y = ey[i].first, yy = ey[i].second;
        if (a[x] == xx)
            continue;
        if (a[y] == yy)
            add(vx, op(vx));
        else {
            int vy = getid(y, yy);
            add(vx, vy);
            add(op(vy), op(vx));
        }
    }
    memset(dfn, 0, sizeof(dfn));
    rep(i, n + n) if (!dfn[i]) tarjan(i);
    rep(i, n) if (blo[i] == blo[i + n]) return;
    rep(i, n) {
        if (blo[i] < blo[i + n])
            putchar('A' + (!a[i]));
        else
            putchar('B' + (a[i] != 2));
    }
    exit(0);
}
void dfs(int x) {
    if (x == v.size()) {
        solve();
        return;
    }
    a[v[x]] = rnd() % 3;
    dfs(x + 1);
    int y;
    while ((y = rnd() % 3) == a[v[x]])
        ;
    a[v[x]] = y;
    dfs(x + 1);
}
int main() {
    n = getint();
    m = getint();
    scanf("%s", s);
    rep(i, n) a[i] = s[i] - 'a';
    m = getint();
    rep(i, m) {
        char cx, cy;
        int x = getint() - 1;
        scanf("%c", &cx);
        int y = getint() - 1;
        scanf("%c", &cy);
        ex.emplace_back(x, cx - 'A');
        ey.emplace_back(y, cy - 'A');
    }
    rep(i, n) if (s[i] == 'x') { v.emplace_back(i); }
    dfs(0);
    printf("%d\n", -1);
    return 0;
}

loj3045 生成函数/fwt

https://loj.ac/problem/3045

这题的生成函数做法没看懂过，但是这题的fwt做法非常精彩，可以反复阅读。

有个注意，\sum\limits_{T}(-1)^{|T \and U|}，当UU非空，结果是00。

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
#include <bits/stdc++.h>
#define ld double
#define ull unsigned long long
#define ll long long
#define pii pair <int, int>
#define iiii pair <int, pii >
#define mp make_pair
#define INF 1000000000
#define rep(i, x) for(int (i) = 0; (i) < (x); (i)++)
inline int getint() {
  int x = 0, p = 1; char c = getchar();
  while (c <= 32) c = getchar();
  if (c == 45) p = -p, c = getchar();
  while (c > 32) x = x * 10 + c - 48, c = getchar();
  return x * p;
}
using namespace std;
const int mod = 998244353;
inline void reduce(int &x) { x += x >> 31 & mod; }
inline int mul(int x, int y) { return 1ll * x * y % mod; }
//ruogu_alter
const int N = 5e4 + 5;
int n, a[N], f[2][N];
//
int modpow(int x, int y) {
  int ans = 1;
  while (y) {
    if (y & 1) ans = mul(ans, x);
    x = mul(x, x);
    y >>= 1;
  }
  return ans;
}
int main() {
  n = getint();
  rep(i, n) a[i] = getint();
  f[0][0] = 1; int sum = 0; 
  rep(ii, n) {
    int x = getint(); sum += x;
    for (int j = sum; j >= x; --j) {
      reduce(f[0][j] += f[a[ii]][j - x] - mod);
      reduce(f[1][j] += f[a[ii] ^ 1][j - x] - mod);
    }
  }
  int res = 0;
  for (int i = 1; i <= sum; i++) {
    reduce(res += mul(modpow(i, mod - 2), f[1][i]) - mod);
  }
  cout << mul(sum, res) << endl;
  return 0;
}

nowcoder 5555c 动态规划

https://ac.nowcoder.com/acm/contest/5555/C

这题有两个套路，拼起来就是一道我不会的题。。（逃

1.1.计算两个字符串交换的权值，对于每个ii，考虑两个串[1..i][1..i]中11的个数的差值，求和。

2.2.怎么统计？数位dpdp，维护两个数组，ff表示权值和，gg表示满足这个情况的串的个数。

具体

[x][y][a][b][x][y][a][b]四维表示前ii个字符，11的个数差值为jj，第一个串、第二个串是否已经小于ss的方案数。

连这种题都不会，我真sl。

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
#include <bits/stdc++.h>
#define ld double
#define ull unsigned long long
#define ll long long
#define pii pair <int, int>
#define iiii pair <int, pii >
#define mp make_pair
#define INF 1000000000
#define rep(i, x) for(int (i) = 0; (i) < (x); (i)++)
inline int getint() {
  int x = 0, p = 1; char c = getchar();
  while (c <= 32) c = getchar();
  if (c == 45) p = -p, c = getchar();
  while (c > 32) x = x * 10 + c - 48, c = getchar();
  return x * p;
}
using namespace std;
const int mod = 998244353;
inline void reduce(int &x) { x += x >> 31 & mod; }
inline int mul(int x, int y) { return 1ll * x * y % mod; }
//ruogu_alter
const int N = 1005;
char s[N];
int n;
int g[N][N << 1][2][2], f[N][N << 1][2][2];
//
int main() {
  scanf("%s", s); n = strlen(s);
  rep(i, n) s[i] -= '0';
  g[0][N][0][0] = 1;
  rep(i, n) for (int j = -i; j <= i; j++) rep(x, 2) rep(y, 2) {
    if (g[i][j + N][x][y]) {
      rep(a, 2) rep(b, 2) {
        if (!x && a > s[i]) continue;
        if (!y && b > s[i]) continue;
        int tox = (x || a < s[i]), toy = (y || b < s[i]), toj = j + a - b;
        //cout << i << " " << j << " " << x << " " << y << " " << a << " " << b << endl;
        reduce(g[i + 1][toj + N][tox][toy] += g[i][j + N][x][y] - mod);
        reduce(f[i + 1][toj + N][tox][toy] += f[i][j + N][x][y] - mod);
        reduce(f[i + 1][toj + N][tox][toy] += mul(abs(toj), g[i][j + N][x][y]) - mod);
      }
    }
  }
  int res = 0;
  rep(i, 2) rep(j, 2) reduce(res += f[n][N][i][j] - mod);
  res = mul(res, (mod + 1) / 2);
  cout << res << endl;
  return 0;
}

soj945 贪心/构造

http://120.27.222.204:12243/problem/945

http://120.27.222.204:12243/uploads/std/2020-5-16.pdf

看题解吧。

感觉自己还是不太会构造。。

代码可以辅助题解看吧（逃

http://120.27.222.204:12243/submission/79525


abc168f 离散化/BFS

https://atcoder.jp/contests/abc168/tasks/abc168_f

直接对坐标全部离散化，然后横坐标一小段和纵坐标一小段组合就是一个矩形了，可以对这个进行bfs。


soj958/gym102201c 圆方树/树形dp

https://codeforces.com/gym/102201/problem/C

记几个结论：

1.1.奇环符号是正的，偶环符号是负的，可以对环长归纳；

2.2.图的正负是每个环的正负相乘：首先如果环上的点编号都连续，那肯定环与环之间没有影响；

否则要做的操作是既交换行又交换列；交换行和列正负号都会反过来，两个都交换就抵掉了；

然后答案就是(−1)偶环个数∗2长度大于2的环个数(-1)^{偶环个数}*2^{长度大于2的环个数}。然后就要树形dpdp了。

很艰难。。圆点方点分开考虑，方形点可以把环上的东西排开然后线性的dpdp。最终复杂度是O(N+M)O(N+M)的。

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
#include <bits/stdc++.h>
#define ld double
#define ull unsigned long long
#define ll long long
#define pii pair <int, int>
#define iiii pair <int, pii >
#define mp make_pair
#define INF 1000000000
#define rep(i, x) for(int (i) = 0; (i) < (x); (i)++)
inline int getint() {
  int x = 0, p = 1; char c = getchar();
  while (c <= 32) c = getchar();
  if (c == 45) p = -p, c = getchar();
  while (c > 32) x = x * 10 + c - 48, c = getchar();
  return x * p;
}
using namespace std;
const int mod = 998244353;
inline void reduce(int &x) { x += x >> 31 & mod; }
inline int mul(int x, int y) { return 1ll * x * y % mod; }
//ruogu_alter
const int N = 2e5 + 5;
int n, m, f[N][2], dp[N][2][2], suf[N], dfn[N], low[N], cnt, c;
vector<int> g[N], gg[N], st;
//
inline void addedge(int x, int y) {
  gg[x].emplace_back(y);
  gg[y].emplace_back(x);
}
void tarjan(int x) {
  dfn[x] = low[x] = ++cnt; st.emplace_back(x);
  for (int to : g[x]) {
    if (!dfn[to]) {
      tarjan(to);
      low[x] = min(low[x], low[to]);
      if (low[to] == dfn[x]) {
        int y;
        do {
          y = st.back(); st.pop_back();
          addedge(y, c);
        } while (y != to);
        addedge(x, c++);
      }
    }
    else low[x] = min(low[x], dfn[to]);
  }
}
void dfs(int x, int p) {
  vector<int> v;
  for (int to : gg[x]) if (to != p) {
    dfs(to, x);
    v.emplace_back(to);
  }
  if (!v.size()) f[x][0] = 1;
  else if (x < n) {
    int pre = 1; suf[v.size()] = 1;
    for (int i = v.size() - 1; i >= 0; i--) suf[i] = mul(suf[i + 1], f[v[i]][0]);
    f[x][0] = suf[0];
    rep(i, v.size()) {
      reduce(f[x][1] += mul(pre, mul(suf[i + 1], f[v[i]][1])) - mod);
      pre = mul(pre, f[v[i]][0]);
    }
  }
  else if (v.size() == 1) {
    f[x][0] = f[v[0]][1];
    f[x][1] = mul(f[v[0]][0], mod - 1);
  }
  else {
    rep(i, 2) rep(j, 2) dp[1][i][j] = mul(f[v[1]][i], f[v[0]][j]);
    reduce(dp[1][1][1] -= mul(f[v[0]][0], f[v[1]][0]));
    for (int i = 2; i < v.size(); i++) {
      int to = v[i];
      rep(y, 2) {
        dp[i][1][y] = dp[i][0][y] = 0;
        reduce(dp[i][1][y] += mul(dp[i - 1][1][y], f[to][1]) - mod);
        reduce(dp[i][1][y] -= mul(dp[i - 1][0][y], f[to][0]));
        dp[i][0][y] = mul(dp[i - 1][1][y], f[to][0]);
      }
    }
    f[x][0] = dp[v.size() - 1][1][1];
    reduce(f[x][1] -= dp[v.size() - 1][1][0]);
    reduce(f[x][1] -= dp[v.size() - 1][0][1]);
    int pw = 1;
    for (int to : v) pw = mul(pw, f[to][0]);
    reduce(pw += pw - mod);
    if (gg[x].size() & 1) reduce(f[x][1] += pw - mod);
    else reduce(f[x][1] -= pw);
  }
}
int main() {
  c = n = getint(); m = getint();
  rep(i, m) {
    int x = getint() - 1, y = getint() - 1;
    g[x].emplace_back(y);
    g[y].emplace_back(x);
  }
  tarjan(0);
  dfs(0, -1);
  cout << f[0][1] << endl;
  return 0;
}

soj957/gym102201d 数据结构/扫描线

https://codeforces.com/gym/102201/problem/D

这题其实挺有趣而且难的。需要看题解才能弄清楚，但是要记住这类题目大概xx和yy中有一维度是单调不降的。

https://www.dropbox.com/s/57m4x4ae7dqpacz/gp5div1sol.pdf

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
#include <bits/stdc++.h>
#define ld double
#define ull unsigned long long
#define ll long long
#define pii pair <int, int>
#define iiii pair <int, pii >
#define mp make_pair
#define INF 1000000000
#define rep(i, x) for(int (i) = 0; (i) < (x); (i)++)
inline int getint() {
  int x = 0, p = 1; char c = getchar();
  while (c <= 32) c = getchar();
  if (c == 45) p = -p, c = getchar();
  while (c > 32) x = x * 10 + c - 48, c = getchar();
  return x * p;
}
using namespace std;
const int mod = 1e9 + 7;
const ll inf = 2e18;
inline void reduce(int &x) { x += x >> 31 & mod; }
inline int mul(int x, int y) { return 1ll * x * y % mod; }
//ruogu_alter
const int N = 2.5e5 + 10;
int n, a[N], b[N], c[N], d[N], sx, sy, ex, ey;
ll res = inf;
//
void work() {
  vector<iiii> v;
  if (sx > ex) swap(sx, ex), swap(sy, ey);
  rep(i, n) if (a[i] >= sx && a[i] <= ex) v.emplace_back(a[i], mp(b[i], d[i]));
  sort(v.begin(), v.end());
  set<pair<int, ll>> s; s.emplace(sy, 0);
  for (auto &e : v) {
    int l = e.second.first, r = e.second.second;
    set<pair<int, ll>> :: iterator it = s.lower_bound(mp(e.second.first, -inf));
    if (it == s.end() || it -> first > r) continue;
    ll vx = inf, vy = inf;
    while (it != s.end() && it -> first <= r) {
      vx = min(vx, it -> second + it -> first - l);
      vy = min(vy, it -> second + r - it -> first);
      it = s.erase(it);
    }
    s.emplace(l, vx);
    s.emplace(r, vy);
  }
  if (ey < s.begin() -> first || ey > s.rbegin() -> first) return;
  for (auto &e : s) res = min(res, ex - sx + e.second + abs(e.first - ey));
}
int main() {
  n = getint(); sx = getint(); sy = getint(); ex = getint(); ey = getint();
  rep(i, n) {
    a[i] = getint(); b[i] = getint(); c[i] = getint(); d[i] = getint();
  }
  work();
  swap(sx, sy); swap(ex, ey);
  rep(i, n) swap(a[i], b[i]), swap(c[i], d[i]);
  work();
  if (res == inf) cout << abs(ex - sx) + abs(ey - sy) << endl;
  else cout << res << endl;
  return 0;
}

soj956/cf639e 贪心/二分

https://codeforces.com/contest/639/problem/E

这题一看就很套路，就是这个完成肯定有个顺序的，就是按照aiti\frac{a_i}{t_i}排序，这个列一列就知道。

然后就直接二分嘛，注意aiti\frac{a_i}{t_i}相同的和aia_i相同的在这题都需要特判断。

然后我第一次提交忘记开longlonglong long了。

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
#include <bits/stdc++.h>
#define ld double
#define ull unsigned long long
#define ll long long
#define pii pair <int, int>
#define iiii pair <int, pii >
#define mp make_pair
#define INF 1000000000
#define rep(i, x) for(int (i) = 0; (i) < (x); (i)++)
inline int getint() {
  int x = 0, p = 1; char c = getchar();
  while (c <= 32) c = getchar();
  if (c == 45) p = -p, c = getchar();
  while (c > 32) x = x * 10 + c - 48, c = getchar();
  return x * p;
}
using namespace std;
const int mod = 1e9 + 7;
inline void reduce(int &x) { x += x >> 31 & mod; }
inline int mul(int x, int y) { return 1ll * x * y % mod; }
//ruogu_alter
const int N = 2e5 + 5;
int n, a[N], b[N], id[N];
ll l[N], r[N], T;
//
bool cmp(int x, int y) {
  return 1ll * a[y] * b[x] < 1ll * a[x] * b[y];
}
bool cmp2(int x, int y) {
  return a[x] > a[y];
}
inline pair<long double, long double> calc(int x, double y) {
  ll L = l[x], R = r[x];
  return mp((1.0 - y * r[x] / (1.0 * T)) * a[x], (1.0 - y * l[x] / (1.0 * T)) * a[x]); 
}
int main() {
  n = getint();
  rep(i, n) a[i] = getint();
  rep(i, n) T += 1ll * (b[i] = getint());
  rep(i, n) id[i] = i;
  sort(id, id + n, cmp);
  ll tnow = 0;
  for (int ii = 0, j; ii < n; ii = j + 1) {
    j = ii; ll L = tnow, R = L;
    while (j + 1 < n && 1ll * a[id[ii]] * b[id[j + 1]] == 1ll * b[id[ii]] * a[id[j + 1]]) ++j;
    for (int k = ii; k <= j; k++) R += b[id[k]];
    for (int k = ii; k <= j; k++) l[id[k]] = L + b[id[k]], r[id[k]] = R;
    tnow = R;
  }
  rep(i, n) id[i] = i;
  sort(id, id + n, cmp2);
  double lb = 0.0, rb = 1.0;
  rep(tt, 50) {
    double mid = (lb + rb) / 2.0; long double now = INF;
    bool fg = true;
    for (int i = 0, j; i < n; i = j + 1) {
      j = i; 
      while (j + 1 < n && a[id[j + 1]] == a[id[i]]) ++j;
      long double tomn = now;
      for (int k = i; k <= j; k++) {
        pair<long double, long double> u = calc(id[k], mid); 
        if (u.second > now) {
          fg = false;
          break;
        }
        tomn = min(tomn, u.first);
      }
      if (!fg) break;
      now = tomn;
    }
    if (fg) lb = mid; else rb = mid;
  }
  printf("%.11f\n", lb);
  return 0;
}

soj951 组合

http://120.27.222.204:12243/problem/951

http://120.27.222.204:12243/utility/2020.5.23.pdf

精彩的需要组合意义的题。可以看题解。

那么注意这题的重要结论，就是

考虑mm个带标号小球，颜⾊为ii的有aia_i个，那么随便排列要求每种颜⾊最⼤的位置标号也最⼤的⽅案数就n!∏ai\frac{n!}{\prod {a_i}}。


soj949 行列分开/哈希

http://120.27.222.204:12243/problem/949

http://120.27.222.204:12243/utility/2020.5.23.pdf

这题我看错题了。。确实可以行列分开，然后考虑选外面还是选里面的。

那么套路就是选外面还是选里面可以赋随机权值然后哈希，然后找哈希值出现次数最多的一种哈希值。


soj944 思考

http://120.27.222.204:12243/problem/944

我的思考和题解的思考完全不一样，自然就毫无正确可言。。

其实要注意这样的题某个数列的最后一个元素一定出现在最终序列的头或者尾，然后同时这个元素如果在某个数列不在尾巴，那么这个数列后面的元素一定不放在他那一侧。而且，答案还一定是22的幂次！


cf960g 数学

https://codeforces.com/contest/960/problem/g

首先有个发现，就是最大值在中间，然后可以左右合并成一个数列，最后答案再乘上(A+BA)\binom{A+B}{A}。

然后我们惊奇的发现，就是第一类斯特林数。原因是我从大到小加入每个数，选择一个组加入，插入在其中一个数的后边，或者新建一组，恰好和第一类斯特林数二维递推式一样。

至于求第一类斯特林数一项或者一行，复杂度都是一样的，参建

https://www.jianshu.com/p/b50df663cd94

woc神仙，全写全了！！

代码不见了。


soj942 线段树/gcd

首先从一个点向右延伸的gcdgcd只有loglog个不同的，那我们自然可以从右往左枚举，然后在枚举到ll的时候就是此时线段树上ll到rr处的答案乘积。

如果直接线段树每个节点维护该区间所有的位置答案的乘积，那么修改的时候是log3nlog^3n的，因为到线段树确定节点了以后还需要快速幂，更为重要的是push_downpush\_down的时候也要快速幂。那么我们可以引入新方法：标记永久化。

具体见代码，大概我不push_downpush\_down，但是对每个点维护一个tagtag表示这个区间都要乘上这个数，然后维护同时维护一个这个区间的答案。

修改的时候，我们给对应线段树节点乘上tagtag，他的祖先都更新一遍区间答案；

而在查询的时候，如果完全包含给定区间，就乘上这个区间的答案；

否则，如果部分包含这个区间，就乘上区间的tagtag乘长度交；

这样，只有在查询的时候需要快速幂，复杂度O(nlog2n)O(nlog^2n)。

代码不见了。


cf1082f 动态规划

https://codeforces.com/contest/1082/problem/F

把trie树建出来。

我们考虑dp[x][y][z]dp[x][y][z]表示以xx为根的子树，然后xx到根的第一个选点在yy，xx子树内选了zz个点的最优情况。

我想的是dp[x][y][z]dp[x][y][z]表示以xx为根的子树，xx子树内有多少个点还没被选点覆盖，xx子树内选了zz个点的最优情况。

感觉我这个状态应该也是对的吧。。不太清楚。

loj3046 线段树合并/虚树/复刻

https://loj.ac/problem/3046

又复习了一遍！！

主要是转化成对每个点算一遍贡献（就是经过这个点的虚树大小），然后加起来没想到。。

相当于每条链就是xx和yy加入然后在他们的lcalca处删除。

https://www.luogu.com.cn/blog/Sooke/solution-p5327

可以看看别人写的题解。

可以看看我当年写的代码。

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
#include <bits/stdc++.h>
#define ld double
#define ull unsigned long long
#define ll long long
#define pii pair<int, int>
#define iiii pair<int, pii>
#define mp make_pair
#define INF 1000000000
#define MOD 1000000007
#define rep(i, x) for (int(i) = 0; (i) < (x); (i)++)
inline int getint() {
    int x = 0, p = 1;
    char c = getchar();
    while (c <= 32) c = getchar();
    if (c == 45)
        p = -p, c = getchar();
    while (c > 32) x = x * 10 + c - 48, c = getchar();
    return x * p;
}
using namespace std;
// ruogu
const int N = 1e5 + 5;
int n, m;
vector<int> G[N];
int cnt, dep[N], in[N], out[N], re[N], id[N], to[20][N << 1], lb[N << 1];
int rt[N], sum[N * 40], ls[N * 40], rs[N * 40], mx[N * 40], mn[N * 40], dat[N * 40];
vector<int> vs, Q[N][2];
ll res;
//

void init(int x, int p, int d) {
    dep[x] = d;
    in[x] = ++cnt;
    vs.push_back(x);
    id[x] = vs.size() - 1;
    rep(i, G[x].size()) {
        int to = G[x][i];
        if (to == p)
            continue;
        init(to, x, d + 1);
        vs.push_back(x);
    }
    out[x] = cnt - 1;
    --in[x];
    re[in[x]] = x;
}

inline int lca(int x, int y) {
    x = id[x];
    y = id[y];
    if (x > y)
        swap(x, y);
    int len = y - x + 1, L = lb[len];
    int lx = to[L][x], rx = to[L][y - (1 << L) + 1];
    return dep[lx] < dep[rx] ? lx : rx;
}

void getst() {
    lb[1] = 0;
    for (int i = 2; i <= vs.size(); i++) lb[i] = lb[i >> 1] + 1;
    rep(i, vs.size()) to[0][i] = vs[i];
    rep(i, 19) rep(j, vs.size()) {
        if (j + (1 << i) > vs.size())
            break;
        int lx = to[i][j], rx = to[i][j + (1 << i)];
        to[i + 1][j] = (dep[lx] < dep[rx]) ? lx : rx;
    }
}

inline int getdis(int x, int y) {
    if (x == INF || y == INF || x == -INF || y == -INF)
        return 0;
    return dep[re[x]] + dep[re[y]] - 2 * dep[lca(re[x], re[y])];
}

inline void up(int x) {
    sum[x] = sum[ls[x]] + sum[rs[x]] + getdis(mx[ls[x]], mn[rs[x]]);
    mx[x] = max(mx[ls[x]], mx[rs[x]]);
    mn[x] = min(mn[ls[x]], mn[rs[x]]);
}

int merge(int x, int y, int l, int r) {
    if (!x || !y)
        return x + y;
    dat[x] += dat[y];
    if (!dat[x])
        return 0;
    if (r - l == 1) {
        mx[x] = mn[x] = l;
        sum[x] = 0;
        return x;
    }
    int mid = (l + r) >> 1;
    ls[x] = merge(ls[x], ls[y], l, mid);
    rs[x] = merge(rs[x], rs[y], mid, r);
    up(x);
    return x;
}

void modify(int &id, int l, int r, int x, bool ok) {
    if (!id)
        id = ++cnt;
    if (ok)
        ++dat[id];
    else
        --dat[id];
    if (!dat[id]) {
        id = 0;
        return;
    }
    if (r - l == 1) {
        mx[id] = mn[id] = l;
        return;
    }
    int mid = (l + r) >> 1;
    if (x < mid)
        modify(ls[id], l, mid, x, ok);
    else
        modify(rs[id], mid, r, x, ok);
    up(id);
}

void dfs(int x, int p) {
    rep(i, G[x].size()) {
        int to = G[x][i];
        if (to == p)
            continue;
        dfs(to, x);
        rt[x] = merge(rt[x], rt[to], 0, n);
    }
    modify(rt[x], 0, n, in[x], 1);
    rep(i, Q[x][1].size()) modify(rt[x], 0, n, Q[x][1][i], true);
    res += (sum[rt[x]] + getdis(mn[rt[x]], mx[rt[x]])) / 2ll;
    modify(rt[x], 0, n, in[x], 0);
    rep(i, Q[x][0].size()) rep(j, 2) modify(rt[x], 0, n, Q[x][0][i], false);
}

int main() {
    n = getint();
    m = getint();
    rep(i, n - 1) {
        int x = getint() - 1, y = getint() - 1;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    init(0, -1, 0);
    cnt = 0;
    getst();
    rep(i, m) {
        int x = getint() - 1, y = getint() - 1;
        if (x == y)
            continue;
        int z = lca(x, y);
        Q[x][1].push_back(in[y]);
        Q[y][1].push_back(in[x]);
        Q[x][1].push_back(in[x]);
        Q[y][1].push_back(in[y]);
        Q[z][0].push_back(in[x]);
        Q[z][0].push_back(in[y]);
    }
    mx[0] = -INF;
    mn[0] = INF;
    dfs(0, -1);
    printf("%lld\n", res / 2ll);
    return 0;
}

cf1063f sam/动态规划

https://codeforces.com/problemset/problem/1063/F

文章作者: ruogu
文章链接: http://ruogu-alter.github.io/2020/05/17/%E6%9D%82%E9%A2%98-%E4%B8%89/
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 ruogu's blog！
总结
评论
簡