题解 | #强智杯"2020年湖南省大学生计算机程序设计竞赛 C题 题解

强智杯"2020年湖南省大学生计算机程序设计竞赛 C Absolute Difference Equation 题解

vp 出了7个题，死活想不出C，哎脑子还是不够用。

比赛链接：强智杯"2020年湖南省大学生计算机程序设计竞赛

C Absolute Difference Equation

题意

对于一个长度为 $nn$ 的 $0\mathrm{/}10/1$ 字符串 $aa$，一次操作为 $f(a)=b_1,b_2,\dots ,b_{n-1}f(a)\; =\; b\_1,b\_2,\backslash dots,b\_\{n-1\}$。其中 $b_i=\mathrm{\mid }{a}_i-a_{i+1}\mathrm{\mid }b\_i\; =\; \backslash vert\; a\_i\; -\; a\_\{i+1\}\backslash vert$。 对于一个给定的 $0\mathrm{/}10/1$ 字符串，某些位上为 $??$，可以任意填 $0\mathrm{/}10/1$，求经过 $n-1n\; -\; 1$ 次操作后剩下的唯一的数为 $11$ 的初始数组的方案数。

题解

对于题目中的 $b_i=\mathrm{\mid }{a}_i-a_{i+1}\mathrm{\mid }b\_i\; =\; \backslash vert\; a\_i\; -\; a\_\{i+1\}\backslash vert$，可以视为 $b_i=a_i⨁a_{i+1}b\_i\; =\; a\_i\backslash bigoplus\; a\_\{i+1\}$。 观察长度为 $1,2,3,41,2,3,4$ 的 $0\mathrm{/}10/1$ 串经过 $n-1n\; -\; 1$ 次操作后的数的结果。

$n=1n\; =\; 1$ 时，$n-1n\; -\; 1$ 次操作后剩下的数为 $a_{1}a\_1$。

$n=2n\; =\; 2$ 时，$n-1n\; -\; 1$ 次操作后剩下的数位 $a_1⨁a_{2}a\_1\backslash bigoplus\; a\_2$。

$n=3n\; =\; 3$ 时， 第一次操作后 $a^{\mathrm{\prime }}=a_1⨁a_2,a_2⨁a_{3}a\text{'}\; =\; a\_1\backslash bigoplus\; a\_2,\; a\_2\backslash bigoplus\; a\_3$。

第二次操作后 $a^{\mathrm{\prime }\mathrm{\prime }}=a_1⨁a_2⨁a_2⨁a_{3}a\text{'}\text{'}\; =\; a\_1\backslash bigoplus\; a\_2\backslash bigoplus\; a\_2\backslash bigoplus\; a\_3$。

$n=4n\; =\; 4$ 时， 第一次操作后 $a^{\mathrm{\prime }}=a_1⨁a_2,a_2⨁a_3,a_3⨁a_{4}a\text{'}\; =\; a\_1\backslash bigoplus\; a\_2,\; a\_2\backslash bigoplus\; a\_3,a\_3\backslash bigoplus\; a\_4$。

第 $n-1n\; -\; 1$ 次操作后 $a^{\mathrm{\prime }\mathrm{\prime }\mathrm{\prime }}=a_1⨁a_2⨁a_2⨁a_3⨁a_2⨁a_3⨁a_3⨁a_{4}a\text{'}\text{'}\text{'}\; =\; a\_1\backslash bigoplus\; a\_2\backslash bigoplus\; a\_2\backslash bigoplus\; a\_3\backslash bigoplus\; a\_2\backslash bigoplus\; a\_3\backslash bigoplus\; a\_3\backslash bigoplus\; a\_4$。

计算一下每个位置的数出现在最终的数里的次数，

$n=1n\; =\; 1$，$11$

$n=2n\; =\; 2$，$111\backslash quad\; 1$

$n=3n\; =\; 3$，$1211\backslash quad\; 2\backslash quad\; 1$

$n=4n\; =\; 4$，$13311\backslash quad\; 3\backslash quad\; 3\backslash quad\; 1$

于是我们就发现，每个位置上的数在最终的表达式里出现的次数恰好和杨辉三角相同，也就是组合数学。

对于最终的答案是否为 $11$，我们只需要判断每个 $11$ 出现在最终表达式中的次数之和的奇偶就行了。

这里给出组合数学奇偶性判断的结论： 对于 $C(n,m)C(n,\; m)$，若 $nn$ & $m=mm\; =\; m$，则为奇数，否则为偶数。

于是我们就可以愉快的进行DP方程转移了，具体见代码及注释。

代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e6 + 10, mod = 1e9 + 7;

char s[N];
int f[N][2][2]; // f[i][j][k]: 第 i 位为 0/1 且 前i个数中 1 出现在最终表达式中的个数为 0/1 的方案数

bool get(int n, int m){ // 判断组合数奇偶性
    return ((n & m) == m);
}
void solve(){
    int n = strlen(s + 1);
    
    for(int i = 0; i <= n; i ++){
        for(int j = 0; j < 2; j ++){
            for(int k = 0; k < 2; k ++) f[i][j][k] = 0;
        }
    }

    f[0][0][0] = 1;
    for(int i = 1; s[i]; i ++){
        int odev = get(n - 1, i - 1);

        // 当前为1或由？变成1，若当前位出现的次数为奇数，那么就能改变前i个的奇偶性，0 -> 1，1 -> 0，否则只能直接转移
        if(s[i] == '1' || s[i] == '?'){ 
            f[i][1][1] = (f[i - 1][1][odev ^ 1] + f[i - 1][0][odev ^ 1]) % mod;
            f[i][1][0] = (f[i - 1][1][odev ^ 0] + f[i - 1][0][odev ^ 0]) % mod;
        }

        // 当前为0或由？变成0，因为当前是0所以出现在最终表达式中的次数不影响结果，直接转移 0 -> 0，1 -> 1
        if(s[i] == '0' || s[i] == '?'){
            f[i][0][1] = (f[i - 1][1][1] + f[i - 1][0][1]) % mod;
            f[i][0][0] = (f[i - 1][1][0] + f[i - 1][0][0]) % mod;
        }
    }
    cout << (f[n][1][1] + f[n][0][1]) % mod << "\n"; // 最终为1的答案之和
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    while(cin >> (s + 1)){
        solve();
    }
    return 0;
}