牛客网提高组6 解题报告

A

题目描述

Venn非常喜欢积木，所以这是一道和积木有关的题。
BLUESKY007和Venn在堆积木。Venn有一个 $n \times m$ 的场地，BLUESKY007有 $q$ 次操作。
BLUESKY007每次会选定一个矩形区域。具体的每次给一组 $(x_{1}, y_{1}), (x_{2}, y_{2})$ 表示矩阵的左下角和右上角。在这个矩阵所覆盖的每一个格子里，累加一个积木块。每个积木块可以可以抽象为一个 $1 \times 1 \times 1$ 的正方体。
现在，Venn想知道他们堆出来的物体的表面积。
注意：堆出物体的底面积也算作表面积，请结合样例理解.

输入描述:

第一行三个整数 $n, m, q$
接下来q行，每行四个整数 $x_{1}, y_{1}, x_{2}, y_{2}$

表示BLUESKY007选择的矩阵的左下角和右上角坐标。

输出描述:

一行一个整数表示物体的表面积

示例1

输入

4 4 3
1 1 4 4
1 1 2 2
3 3 4 4

输出

示例2

输入

4 4 1
1 1 2 2

输出

分析

因为只有 $1$ 次询问，所以先先二维差分，然后再求前缀和还原原数组。得到原数组后怎么求表面积呢？（我特喵就是表面积求错了真自闭了，比赛最后下载完大样例才发现5555）。
对于每个点，如果有积木，先算上上下部分， $s = s + 2$ 。再考虑四周，每个面的表面积怎么算入答案呢？我们需要比较四周积木和它的高度，如果比它小，就要加上他们的高度差作为表面积。

代码如下

#include <bits/stdc++.h>
#define LL long long
using namespace std;
int mp[5005][5005];
LL s, sum;
int main(){
    int i, j, n, m, q, a, b, c, d, maxn;
    scanf("%d%d%d", &n, &m, &q);
    while(q--){
        scanf("%d%d%d%d", &a, &b, &c, &d);
        mp[a][b]++, mp[c+1][b]--, mp[a][d+1]--, mp[c+1][d+1]++;
    }
    for(i = 1; i <= n + 1; i++){
        for(j = 1; j <= m + 1; j++){
            mp[i][j] += mp[i-1][j] + mp[i][j-1] - mp[i-1][j-1];
            //printf("%d %d %d\n", i, j, mp[i][j]);
        }
    }
    for(i = 1; i <= n; i++){
        for(j = 1; j <= m; j++){
            if(mp[i][j]) sum += 2;
            if(mp[i][j] > mp[i][j-1]) sum += (mp[i][j] - mp[i][j-1]);
            if(mp[i][j] > mp[i][j+1]) sum += (mp[i][j] - mp[i][j+1]);
            if(mp[i][j] > mp[i-1][j]) sum += mp[i][j] - mp[i-1][j];
            if(mp[i][j] > mp[i+1][j]) sum += (mp[i][j] - mp[i+1][j]);
        }
    }
    printf("%lld", sum);
    return 0;
}

B

题目描述

BLUESKY007鸽鸽又在玩她的数列了。
这次BLUESKY007有一个长度为n的正整数数列，里面每一个数值都不超过k。一个数列 $b_{1}, b_{2}, b_{3} . . . b_{n}$

为回文数列，当且仅当该数列满足 $\forall i \in [1, n] <mtext> </mtext> ， b_{i} = b_{n - i + 1}$
BLUESKY007非常关注序列的回文性质，并且她关注的回文种类和她的心情有关。
当她开心时她喜欢不存在长度为奇数且大于1的回文子串的数列,当她不开心时她喜欢不存在长度为偶数且大于1的回文子串的数列。
Venn又把BLUESKY007鸽鸽的数列弄坏了，导致里面的部分数字不见了。Venn想趁BLUESKY007鸽鸽回来之前，恢复整个序列，但是他只知道BLUESKY007鸽鸽现在的心情，以及这个数列原本是BLUESKY007喜欢的数列。
Venn为了恢复整个序列，他想知道有多少种不同的数列可能是原本的数列。
由于可能的数列太多会导致Venn崩溃，所以你只需要告诉他这个数字对998244353取模的答案即可。
输入描述:
第一行三个正整数n,k,m表示数列的长度，数列里面数字的上限，以及BLUESKY007此时的心情，m=0表示心情不好，m=1表示心情偷税。
第二行n个整数， $a_{1}, a_{2}, a_{3} . . . a_{n}$

表示当前的数列。如果 $a_{i} = 0$ 说明第i位上面的数字遗失了，否则表示原本的数列这个位置上的数。

输出描述:

一行一个整数，表示答案。

示例1

输入

5 2 1
1 0 0 1 2

输出

示例2

输入

5 3 1
1 0 0 1 2

输出

示例3

输入

4 200000 1
0 0 12345 0

输出

735945883

示例4

输入

4 3 0
1 0 0 2

输出

示例5

输入

10 4 0
1 0 0 2 0 0 3 0 0 4

输出

343

分析

首先我们要发现：
$m = 0$ 时， $\forall i \in [1, n], a_{i}! = a_{i + 1}$
$m = 1$ 时， $\forall i \in [1, n], a_{i}! = a_{i + 2}$
然后我们发现 $m = 1$ 的情况其实就是把 $m = 0$ 分奇偶做然后把答案相乘。现在只考虑 $m = 0$ 的情况。

要不先讲讲我在考场上的60pts做法？

注意到 $k \leq 1000$ ，而我们每个位置填什么数受制于 $i - 1$ 和 $i + 1$ 的位置上的数，换句话说，在 $i$ 这个位置填不同的数有不同的答案。于是我想到了一种不用考虑 $i + 1$ 位置的 $d p$ 。
记 $f [i] [j]$ 表示前 $i$ 个数，第 $i$ 个数填 $j$ 的方案数总和。转移方程如下：
$f [i] [j] = \sum_{t = 1}^{k} f [i - 1] [t] (t \neq j)$ 。每次枚举 $t$ 复杂度就会变成 $O (n * k^{2})$ ，考虑到 $t$ 是处于前一维的，我们可以用前缀和优化。
记 $s s [i] [j]$ 表示 $\sum_{t = 1}^{k} f [i - 1] [t] (t \neq j)$ , $s [i]$ 表示 $\sum_{j = 1}^{k} f [i] [j]$ ，那么
$s s [i] [j] = s [i] - f [i] [j]$ 。于是就得到了 $60 p t s$ ，

代码如下：

#include <bits/stdc++.h>
#define mod 998244353
#define LL long long
using namespace std;
int v[25], a[200005], ans, k, n, m, cnt, f[2005][2005], s[2005][2005], sum[2005];
LL z = 1, s1, s2;
int pd(){
    int i;
    //for(i = 1; i <= n; i++) printf("%d ", a[i]);
    //printf("\n");
    if(m){
        for(i = 1; i <= n; i++){
            if(a[i] == a[i+2]) return 0;
        }
        return 1;
    }
    else{
        for(i = 1; i <= n; i++) if(a[i] == a[i+1]) return 0;
        return 1;
    }
}
void dfs(int p){
    int i;
    if(p == n + 1){
        cnt++;
        if(pd()) ans++;
        return;
    }
    if(v[p]) dfs(p + 1);
    else{
        for(i = 1; i <= k; i++){
            a[p] = i;
            dfs(p + 1);
        }
    }
}
int main(){
    int i, j = 0, q;
    scanf("%d%d%d", &n, &k, &m);
    if(n <= 20){
        for(i = 1; i <= n; i++){
            scanf("%d", &a[i]);
            if(a[i] > 0) v[i] = 1;
        }
        //for(i = 1; i <= n; i++) printf("%d ", v[i]);
        dfs(1);
        printf("%d", ans);
    }
    else{
        for(i = 1; i <= n; i++) scanf("%d", &a[i]);
        if(m){
            for(i = 1; i <= 2; i++){
                if(a[i]) f[i][a[i]] = 1;
                else for(j = 1; j <= k; j++) f[i][j] = 1;
                for(j = 1; j <= k; j++) sum[i] = (sum[i] + f[i][j]) % mod;
                for(j = 1; j <= k; j++) s[i][j] = ((sum[i] - f[i][j]) % mod + mod) % mod;
            }
            //printf("%d\n", s[2][2]);
            for(i = 3; i <= n; i++){
                if(a[i]) f[i][a[i]] = s[i-2][a[i]];
                else for(j = 1; j <= k; j++) f[i][j] = s[i-2][j];
                for(j = 1; j <= k; j++) sum[i] = (sum[i] + f[i][j]) % mod;
                for(j = 1; j <= k; j++) s[i][j] = ((sum[i] - f[i][j]) % mod + mod) % mod;
            }
            for(i = 1; i <= k; i++){
                s1 = (s1 + f[n][i]) % mod;
                s2 = (s2 + f[n-1][i]) % mod;
            }
            printf("%d", z * s1 * s2 % mod);
        }
        else{
            if(a[1]) f[1][a[1]] = 1;
            else for(i = 1; i <= k; i++) f[1][i] = 1;
            for(j = 1; j <= k; j++) sum[1] = (sum[1] + f[1][j]) % mod;
            for(j = 1; j <= k; j++) s[1][j] = ((sum[1] - f[1][j]) % mod + mod) % mod;
            for(i = 2; i <= n; i++){
                if(a[i]) f[i][a[i]] = s[i-1][a[i]];
                else for(j = 1; j <= k; j++) f[i][j] = s[i-1][j];
                for(j = 1; j <= k; j++) sum[i] = (sum[i] + f[i][j]) % mod;
                for(j = 1; j <= k; j++) s[i][j] = ((sum[i] - f[i][j]) % mod + mod) % mod;
            }
            for(i = 1; i <= k; i++) s1 = (s1 + f[n][i]) % mod;
            printf("%d", s1);
        }
    }
    return 0;
}

下面是正解！！！

正解是用 $d p$ 进行预处理，这种做法我还真没见过（我太弱啦
记 $f [i] [0 / 1]$ 表示两个非零的数中间有 $i$ 个 $0$ 的方案数， $0$ 表示两数不同， $1$ 表示两数相同。
可以得到转移方程：
$f [i] [1] = (k - 1) * f [i - 1] [0] f [i] [0] = f [i - 1] [1] + (k - 2) * f [i - 1] [0]$
然后就，就，就搞一搞就行了。

代码如下

#include <bits/stdc++.h>
#define mod 998244353
#define N 200005
#define LL long long
using namespace std;
int f[N][2], a[N], b[N], g[N], c[N], cnt, ans, k;
LL z = 1;
int ksm(int a, int b, int p){
    int s = 1;
    while(b){
        if(b & 1) s = z * s * a % mod;
        a = z * a * a % mod;
        b >>= 1;
    }
    return s;
}
int solve(int a[]){
	int i, j, n = a[0], s = 1, cnt = 0;
	for(i = 1; i <= n; i++) if(a[i] && a[i] == a[i+1]) return 0;
	for(i = 1; i <= n; i++)
		if(a[i]){
			j = i;
			break;
		}
	if(i == n + 1) return z * k * ksm(k-1, n-1, mod) % mod;
	if(j > 1) s = ksm(k-1, j-1, mod) % mod;
	for(i = j + 1; i <= n; i++){
		if(!a[i]) cnt++;
		else{
			s = z * s * f[cnt][a[i] == a[j]] % mod;
			j = i;
			cnt = 0;
		}
	}
	if(j < n) s = z * s * ksm(k-1, n-j, mod) % mod;
	return s;
}
int main(){
    int i, j, n, m;
    scanf("%d%d%d", &n, &k, &m);
    f[0][0] = 1; a[0] = n;
    for(i = 1; i <= n; i++){
        f[i][1] = z * (k - 1) * f[i-1][0] % mod;
        f[i][0] = (f[i-1][1] + z * (k - 2) * f[i-1][0] % mod) % mod;
    }
    for(i = 1; i <= n; i++) scanf("%d", &a[i]);
    if(!m) ans = solve(a);
    else{
    	for(i = 1; i <= n; i += 2) b[++b[0]] = a[i];
    	for(i = 2; i <= n; i += 2) c[++c[0]] = a[i];
    	ans = z * solve(b) * solve(c) % mod;
	}
	printf("%d", ans);
    return 0;
}

C

题目描述

BLUESKY007和Venn又到了开学的时候，他们分别在班A,B中，这两个班都是OI班。
班A有n人，而班B有m人。
由于NOIp改成了CSP，学校希望从原来A,B班中抽出若干人组成一个新的CSP班，但是为了公平起见，学校会在A,B班抽出相同数量的人组成一个新班。
但是学校并没有决定新班的人数，但是显然新班人数的一半不能超过A班人数或B班人数。
Venn是一个好奇的孩子，他希望知道对于所有可能的分班方案，新班人数之和是多少。
两个分班方案不同，当且仅当新班的人数不同或者两种分班方案中,新班中至少有一个人不同。
由于这个数字很大，你只要输出他对19260817取模的值即可。

输入描述:

一行一个正整数T表示数据组数。
对于每一组数据，一行两个整数n,m表示题面中的意义。

输出描述:

对于每组数据，输出一行一个整数表示答案。

示例1

输入

5
1 1
2 2
5 3
2512 1245
235623434324324 23562343253242

输出

2
12
210
3372436
6579313

分析

这道题本质上就是求
$<munderover> \sum i = 0 m i n (n, m) </munderover> 2 * i * C_{n}^{i} * C_{m}^{i}$
$40 p t s$ ，预处理组合数然后每次询问 $O (n)$ 得到答案就可以了。
$60 p t s$ ，我们需要一些转化。
首先我们要把 $i$ 给拿走啊。高中不是学过一个公式吗（~~我特么早忘了~~
$i * C_{n}^{i} = n * C_{n - 1}^{i - 1}$
这个可以直接推，也可以构造模型理解。
然后我们就可以代入原式了，再加上组合数的对称性可以得到以下推导：
$<munderover> \sum i = 0 m i n (n, m) </munderover> 2 * i * C_{n}^{i} * C_{m}^{i} = <munderover> \sum i = 0 m i n (n, m) </munderover> 2 * m * C_{n}^{i} * C_{m - 1}^{i - 1} = 2 * m * <munderover> \sum i = 0 m i n (n, m) </munderover> C_{n}^{i} * C_{m - 1}^{m - i} = 2 * m * C_{n + m - 1}^{m}$
最后一步用的是范德蒙德公式，即
$<munderover> \sum i = 0 k </munderover> C_{n}^{i} * C_{m}^{k - i} = C_{n + m}^{k}$
这个其实很好理解，从一堆人里选 $k$ 个，等价于分成两拨，一边选 $i$ 个，另一边选 $k - i$ 个，然后求和。
回到题目，我们可以预处理阶乘和阶乘的逆元，然后 $O (1)$ 回答询问。

$100 p t s$ : 空间开不了那么大啊，注意到模数很小(~~没注意到~~，用lucas定理就可以了。

代码如下：

#include <bits/stdc++.h>
#define LL long long
#define mod 19260817
using namespace std;
int fuc[mod + 2], inv[mod + 2];
LL z = 1;
int ksm(int a, int b, int p){
    int s = 1;
    while(b){
        if(b & 1) s = z * s * a % p;
        a = z * a * a % p;
        b >>= 1;
    }
    return s;
}
int C(int n, int m){
    if(n < m || m < 0) return 0;
    return z * fuc[n] * inv[m] % mod * inv[n - m] % mod;
}
int lucas(LL n, LL m, int p){
    if(n <= p && m <= p) return C(n, m);
    return !m? 1: z * lucas(n / p, m / p, p) * C(n % p, m % p) % p;
}
int main(){
    int i, j, T, p = mod;
    LL n, m;
    fuc[0] = 1;
    for(i = 1; i < p; i++) fuc[i] = z * fuc[i-1] * i % p;
    inv[p-1] = ksm(fuc[p-1], mod-2, mod);
    for(i = p-2; i >= 0; i--) inv[i] = z * inv[i+1] * (i + 1) % mod;
    scanf("%d", &T);
    while(T--){
        scanf("%lld%lld", &n, &m);
        printf("%d\n", 2 * m % mod * lucas(n + m - 1, m, mod) % mod);
    }
    return 0;
}