题解 CF296B 【Yaroslav and Two Strings】
eee_hoho
2020-11-11 20:25:09
考虑直接对不可比的串进行dp，设$f_i$表示前$i$个字符不可比的串的个数，$g1_i$表示前$i$个字符可比的字符串且所有$s\leq t$的个数，$g2_i$表示前$i$个字符可比的字符串且所有$s\geq t$的个数，$g3_i$表示前$i$个字符可比的字符串且$s=t$的个数。
于是考虑转移方程：
1. $s_i\neq ?,w_i\neq?$
$$\begin{cases}f_i=f_{i-1}+g1_{i-1}[s_i>w_i]+g2_{i-1}[s_i<w_i]-g3_{i-1}[s_i\ne w_i]\\g1_i=g1_{i-1}[s_i\le w_i]\\g2_i=g2_{i-1}[s_i\ge w_i]\\g3_i=g3_{i-1}[s_i=w_i]\end{cases}$$
就是之前的方案乘和这一位相反的方案，但还要减去之前都相等的方案。
2. $s_i=?,w_i\neq?$
有一个是问号的做法是类似的，所以我只拿一个来说。
$$\begin{cases}f_i=10f_{i-1}+(9-(w_i-'0'))g1_{i-1}+(w_i-'0')g2_{i-1}-9g3_{i-1}\\g1_i=(w_i-'0'+1)g1_{i-1}\\g2_i=(9-(w_i-'0')+1)g2_{i-1}\\g3_i=g3_{i-1}\end{cases}$$
直接考虑问号会取到哪些值，然后用和上面一样的容斥处理方案。
3. $s_i=?,w_i=?$
$$\begin{cases}f_i=100f_{i-1}+45g1_{i-1}+45g2_{i-1}-90g3_{i-1}\\g1_i=55g1_{i-1}\\g2_i=55g2_{i-1}\\g3_i=10g3_{i-1}\end{cases}$$
多考虑一个问号，就是多用一个求和公式算算就可以了。
最后注意下$i=1$的时候不会构成不可比的串，所以$f_1=0$
**Code**
``` cpp
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
const int N = 1e5;
const int p = 1e9 + 7;
using namespace std;
int n,g1[N + 5],g2[N + 5],f[N + 5],g3[N + 5];
char s[N + 5],w[N + 5];
int main()
{
scanf("%d",&n);
scanf("%s",s + 1);
scanf("%s",w + 1);
g1[0] = g2[0] = g3[0] = 1;
for (int i = 1;i <= n;i++)
{
if (s[i] != '?' && w[i] != '?')
{
if (s[i] <= w[i])
g1[i] = g1[i - 1];
if (s[i] >= w[i])
g2[i] = g2[i - 1];
if (s[i] == w[i])
g3[i] = g3[i - 1];
f[i] = f[i - 1];
if (s[i] < w[i])
f[i] += g2[i - 1],f[i] %= p;
if (s[i] > w[i])
f[i] += g1[i - 1],f[i] %= p;
if (s[i] != w[i])
f[i] -= g3[i - 1],f[i] %= p;
}
if (s[i] == '?' && w[i] != '?')
{
f[i] = 10ll * f[i - 1] % p;
g1[i] = 1ll * g1[i - 1] * (w[i] - '0' + 1) % p;
g2[i] = 1ll * g2[i - 1] * (9 - (w[i] - '0') + 1) % p;
g3[i] = g3[i - 1];
f[i] += 1ll * g1[i - 1] * (9 - (w[i] - '0')) % p;
f[i] %= p;
f[i] += 1ll * g2[i - 1] * (w[i] - '0') % p;
f[i] %= p;
f[i] -= 9ll * g3[i - 1] % p;
f[i] %= p;
}
if (s[i] != '?' && w[i] == '?')
{
f[i] = 10ll * f[i - 1] % p;
g1[i] = 1ll * g1[i - 1] * (9 - (s[i] - '0') + 1) % p;
g2[i] = 1ll * g2[i - 1] * (s[i] - '0' + 1) % p;
g3[i] = g3[i - 1];
f[i] += 1ll * g1[i - 1] * (s[i] - '0') % p;
f[i] %= p;
f[i] += 1ll * g2[i - 1] * (9 - (s[i] - '0')) % p;
f[i] %= p;
f[i] -= 9ll * g3[i - 1] % p;
f[i] %= p;
}
if (s[i] == '?' && w[i] == '?')
{
f[i] = 100ll * f[i - 1] % p;
g1[i] = 55ll * g1[i - 1] % p;
g2[i] = 55ll * g2[i - 1] % p;
g3[i] = 10ll * g3[i - 1] % p;
f[i] += (45ll * g1[i - 1] % p + 45ll * g2[i - 1] % p) % p;
f[i] %= p;
f[i] -= 90ll * g3[i - 1] % p;
f[i] %= p;
}
f[1] = 0;
}
cout<<(f[n] + p) % p<<endl;
return 0;
}
```