20联赛集训day6

发表于 更新于 分类于

莫名其妙的混了一个上午

卷

众所周知，集训队作业一下发，队员们立刻开始了卷卷卷的日子。

qjd 作为国家队的候选人之一，当然要争当卷王。于是他把这一堆集训队作业摆成了一个树状结构，第一天他就打算做一大批集训队作业题。

然而如果做的两个集训队作业题在树上有直接连边（即在树上相邻），那么 qjd 就会感觉非常不爽从而出 \(114514\) 个多项式毒瘤题扔给大家做。

小 w 非常不希望这样的事情发生，为了拯救世界，他主动要求帮助 qjd 选择一些集训队作业题做。可是 qjd 是有要求的，他给每个题目定义了一个难度 \(w-i\)，小 w 要让选出题的难度之积尽量大。

简要地说，给定一棵树，你需要求出最大乘积独立集。

由于答案很大，你只需要输出答案 \(\bmod 10^9+7\) 的结果即可。

此外，你可以认为 \(w-i\) 是在给定范围内随机生成的.

最开始抄了个高精度，好像不怎么行...

\(w-i\)随机生成，取对数直接冲了。

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 2e5 + 5;
const ll MOD = 1e9 + 7;
int n;
vector<int> e[N];
ll f[N][2], w[N];
long double g[N][2];

long double chkmax(long double a, long double b) {
    return a > b ? a : b;
}

void dfs(int u, int fa) {
    f[u][1] = w[u];
    f[u][0] = 1;
    g[u][1] = log(1.0 * w[u]);
    for (int v : e[u]) {
        if (v == fa) continue;
        dfs(v, u);
        g[u][1] = g[v][0] + g[u][1];
        g[u][0] = chkmax(g[v][1], g[v][0]) + g[u][0];
        f[u][1] = f[v][0] * f[u][1] % MOD;
        if (g[v][1] > g[v][0]) f[u][0] = f[v][1] * f[u][0] % MOD;
        else f[u][0] = f[u][0] * f[v][0] % MOD;
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%lld", &w[i]);
    for (int i = 1; i < n; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        e[u].push-back(v);
        e[v].push-back(u);
    }
    dfs(1, 0);
    ll ans = (g[1][0] > g[1][1]) ? f[1][0] : f[1][1];
    printf("%lld\n", ans);
    return 0;
}

简单题

小 w 居然过了数学预赛，和 qjd 一起来到了数竞班上课qjd 看了一眼讲义上的题，发现谁的不行，于是自己又随口说了一道题，给定一个包含 \(n\) 个元素的集合 \(P=\{1,2,3,...,n\}\)，求有多少个集合 \(A\subseteq P\)，满足任意 \(x\in A\) 有 \(2x\notin A\)，且对于 \(A\) 在 \(P\) 中的补集 \(B\)，也满足任意 \(x\in B\) 有 \(2x\notin B\)。 小 w 花费了 \(10^{100}\) 天终于算出来了这个答案，但是 qjd 居然又加了一个条件！他要求 \(A\) 的大小恰好为 \(m\)，这样又有多少个 \(A\) 呢？ 这回 小 w 真的不会了，他找到了你，希望能够得到帮助。由于答案太大，你只需要输出答案 \(\bmod\ 10000019\) 即可。

把每个\(p,p*2,p*2^2,p*2^3,\cdots,p*2^k\)分为一组。

其中\(p\)时素数 ，可以发现不同组别直接是不影响的，而同组的可以分成两类，\(A\)必须选其中一类。

如果有偶数个，那么直接乘一个\(2\)的贡献。

如果是奇数个，多出来的一个可以给\(A\)也可以给\(B\)。

最后对于每个询问，减去至少要选的，剩下的从奇数组里面选\(\binom{n}{m}\)个，乘上一个\(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
38
39
40
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 10000020, p = N - 1;
int a[N], q;
ll n;

int fpow(int a, int b) {
	int res = 1;
	for (; b; b >>= 1, a = a * 1ll * a % p) if (b & 1) res = res * 1ll * a % p;
	return res;
}
int C(ll n, ll m) {
	if (m > n) return 0;
	return a[n] * 1ll * fpow(a[n - m], p - 2) % p * 1ll * fpow(a[m], p - 2) % p;
}
int solve(ll n, ll m) {
	if (m == 0) return 1;
    return solve(n / p, m / p) * 1ll * C(n % p, m % p) % p;
}

int main() {
    scanf("%lld %d", &n, &q);
	a[0] = 1;
	for (int i = 1; i <= p; i++) a[i] = a[i - 1] * 1ll * i % p;
	ll len = 0, two = 1, pp = 0;
    for (int i = 0; 1 <= (n >> i); i++) {
    	ll l = n >> (i + 1), r = n >> i, cnt = ((r + 1) >> 1) - ((l + 1) >> 1);
    	if (i & 1) len += ((i + 1) >> 1) * cnt, two = two * fpow(2, cnt % (p - 1)) % p;
    	else len += (i >> 1) * cnt, pp += cnt;
    }
    while (q--) {
    	ll x;
    	scanf("%lld", &x);
    	if (x < len || x > len + pp) puts("0");
    	else printf("%lld\n", solve(pp, x - len) * two % p);
    }
	return 0;
}

粉丝

众所周知，qjd 有很多很多的粉丝，小 w 便是 qjd 的脑残粉之一。

又到了一年粉丝见面会的日子，qjd 委托小 w 帮他准备一下粉丝见面会的相关事宜，其中有一项便是座位的编排 总共有 \(n\) 位粉丝会来参加见面会，为了便于大家观赏英俊潇洒、风流倜傥、一表人才、玉树临风、气宇轩昂、温文尔雅、风度翩翩的 qjd，qjd 希望把这总共 \(n\) 个座位分成 \(k\) 组（\(k\) 是任意正整数），设第 \(i\) 组有 \(s-i\) 个座位，那么他需要满足: \(\forall 1 \le i ; k,s-i \le s_{i+1}\) \(x \le s-1 \le y\) 其中，\(x,y\) 是给定正整数。 由于小 w 已经帮忙安排过很多次 qjd 的粉丝见面会了，所以他很快就给出了一个不错的方案。然而 qjd 对此却不屑一顾，便又问：那你能算出总共有多少种合法的方案吗？小 w 懵逼了，因为他连怎么从 \(1\) 数到 \(100\) 都不会！ 于是他来寻求你的帮助，为了方便，qjd 会给定一个正整数 \(P\)，你只要输出答案对 \(P\) 取模的结果即可。

考虑可以拆成只有 \(≥x\)的限制,用\(≥x\)的答案减去\(≥y+1\)的答案。

直接\(dp\)的话，用\(f[i][j]\)表示枚举到\(i\)，总和为\(j\)的方案数，类似于背包，复杂度为\(O(n^2)\)

分别用 \(≤\sqrt n\) 的数和 \(>\sqrt n\) 的数进行划分\(n\)的\(dp\)，最后枚举其中一个的和，把两部分的方案数合并。

两种划分数的\(dp\)：

一种\(f(i,j)\)表示当前 \(dp\) 到数字 \(i\)，总和为 \(j\)。 每次枚举选了多少个\(i\),转移方程为\(f[i][j]=f[i-1][j]+f[i][j-i]\)

一种\(g(i,j)\)表示当前总共分成了\(i\)个数字，总和为\(j\)，转移方程为\(g[i][j]=g[i-1][j]+g[i][j-i]\) 。

可以看出，两部分转移方程都是一样的，但理解的方式有些差异。

第一种类似于完全背包，不记录选了多少个数。

第二种因为要把每个数加 \(\sqrt n +1\)，总和最后要发生变化，所以要记录选出多少个数，以便统计总和的增加值。

把每个数减去\(\sqrt n +1\)后 , \(g(i,j)\)可以理解为把\(j\)个相同的球，放入\(i\)个相同的箱子，允许空箱的方案数。

有两种选择，一个是把所有箱子都放一个球，这样的话就和 \(g[i][j-i]\)相同。另一种是新开一个空箱子，也就是\(g[i][j]=g[i-1][j]\)。

因为每一种放球的情况和每次放球的操作一一对应，所以可以用\(g[i][j]=g[i-1][j]+g[i][j-i]\) 来转移方案数。

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
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;
int n, x, y, p, sqr, f[N], h[N], g[N];

int solve(int x) {
	if (x > n) return 0;
    int limit = max(x, sqr);
    memset(f, 0, sizeof f);
    memset(g, 0, sizeof g);
    memset(h, 0, sizeof h);
    f[0] = 1;
    for (int i = x; i <= limit; i++)
    	for (int j = i; j <= n; j++) f[j] = (f[j] + f[j - i]) % p;
    g[0] = 1; h[0] = 1;
    for (int i = 1; i <= n / limit; i++)
    	for (int j = 0; j <= n; j++) {
    		if (j >= i) g[j] = (g[j] + g[j - i]) % p;
    		if (j + i * (limit + 1) <= n) h[j + i * (limit + 1)] = (h[j + i * (limit + 1)] + g[j]) % p;
    	}
    	int res = 0;
    	for (int i = 0; i <= n; i++) res = (res + f[i] * 1ll * h[n - i] % p) % p;
    	return res;
}

int main() {
    scanf("%d %d %d %d", &x, &y, &n, &p);
    sqr = (int)sqrt(n + 0.5);
    return printf("%d\n", ((solve(x) - solve(y + 1) % p + p) % p)), 0;
}

字符串

qjd 拿到了一个长度为 \(n\) 的字符串 \(S\)！ 因为这个字符串长得很菜，所以 qjd 决定把这个字符串五马分尸。即，他要把这个 \(S\) 分成五段，也就是找到五个字符串 \(A,B,C,D,E\)，使得 \(A+B+C+D+E=S\)，其中 \(+\) 表示把两个字符串连接起来。 注意 qjd 不一定恰好要把它分成五段，即 \(A,B,C,D,E\) 中可以有空串。 接下来，qjd 会把 \(A+C+E\) 作为一个新的字符串 \(T\)，他希望这个字符串是回文的，并且他希望 \(T\) 越长越好。由于 qjd 是个大鸽子，你能来帮帮他完成这个任务吗？形式化的，你需要最大化 \(|A|+|C|+|E|\)，使得 \(A+C+E\) 是个回文串。

感觉很难的一道题。

首先把两边能选的先选调。

剩下部分再选一个回文串出来。

先马拉车预处理一下每个中心点的最长回文串。

因为还可以和一端的前缀接上一些字符，反串跑一下\(kmp\)，反串的某个前缀和正串前缀的\(\text{boder}\)相当于正串某个后缀的前缀和前缀的最长回文串长度。

考虑一下回文串是前缀的情况再单独延伸一段，和回文串后面接一段两种情况。

一开始去两端时也有两种情况，要看哪一段不能继续延伸，正反串交换跑一下就可以。

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
#include <bits/stdc++.h>
using namespace std;

const int N = 1e7 + 1e6 +5;
int mid, rad, r[N * 2], f[N], g[N], mx[N], n;
char ms[N * 2], s[N], sr[N];

int solve(const char *s, const char *sr) {
    for (int i = 1; i <= n; i++) {
    	ms[i * 2] = s[i];
    	ms[i * 2 - 1] = '#';
    }
    ms[n + n + 1] = '#', ms[0] = '&';
    mid = 0, rad = 0;
    for (int i = 1; i <= n + n + 1; i++) {
    	r[i] = 0;
    	if (i <= mid + rad) r[i] = min(r[mid + mid - i], mid + rad - i);
    	for (; ms[i - r[i] - 1] == ms[i + r[i] + 1]; r[i]++);
    	if (i + r[i] > mid + rad) mid = i, rad = r[i];
    }
   int j = 0;
   for (int i = 2; i <= n; i++) {
       while (j && s[j + 1] != s[i]) j = f[j];
       j += s[j + 1] == s[i];
       f[i] = j;
   }
   memset(mx, 0, sizeof mx);
   j = 0;
   for (int i = 2; i <= n; i++) {
   	   while (j && s[j + 1] != sr[i]) j = f[j];
   	   j += s[j + 1] == sr[i];
   	   g[i] = j; mx[i] = max(mx[i - 1], g[i]);
   }
   int res = 0;
   for (int i = 0; i <= n; i++) {
   	   int len = (r[i + i + 1] / 2), k = g[n - i - len];
       res = max(res, r[i + i + 1] + 2 * min(k, i - len));
       if (mx[n - i - len] >= i - len) res = max(res, r[2 * i + 1] + i + i - len - len);
   }
   for (int i = 1; i <= n; i++) {
       int len = (r[i + i] / 2), k = g[n - i - len];
       res = max(res, r[i + i] + 2 * min(k, i - len - 1));
       if (mx[n - i - len] >= i - len - 1) res = max(res, r[2 * i] + i + i - len - len - 2);
   }
   return res;
}

int main() {
    scanf("%s", s + 1);
    n = strlen(s + 1);
    int l = 1, r = n, p = 0;
    while (l + 1 < r && s[l] == s[r]) l++, r--, p++, p++;
    for (int i = l; i <= r; i++) s[i + 1 - l] = s[i];
    n -= p;
    for (int i = 1; i <= n; i++) sr[i] = s[n - i + 1];
    return printf("%d\n", max(solve(s, sr), solve(sr, s)) + p), 0;
}