CF296B Yaroslav and Two Strings

题意：有两个串，每个串的内容要么是数字要么是问号，一共多少种方案使得两个串中存在两个位置一个位置比另一个大，一个位置比另一个小。问号可以填0～9.
思路：
容斥原理，看一共有多少状态减去非法状态，一共的状态数等于10的问号次方，非法状态，要么就是全大于等于，要么就是全小于等于，要么就是全等于，假设res1,res2,res3是这三个解，total是一共的方案数，答案是total-res1-res2+res3,为什么要加上res3呢，因为我们一共要减去的是一个相等的方案数，然后res1,res2里面都包含了全部等于的情况，最后再减去res3。

#include<iostream>
#include<cstring>
using namespace std;
const int N=100010;
const int mod=1e9+7;
typedef long long ll;
string s1,s2;
int main()
{
   
	ll ans=1;
	ll r1=1;	//完全大于
	ll r2=1;
	ll r3=1;
	int n;
	cin>>n;
	cin >> s1 >> s2;
	for(int i=0;i<s1.size();i++)
		if(s1[i]=='?')
			ans=(ll)ans*10%mod;
	for(int i=0;i<s2.size();i++)
		if(s2[i]=='?')
			ans=(ll)ans*10%mod;
		//cal r1
	for(int i=0;i<n;i++)
	{
   
		if(s1[i]!='?' && s2[i]!='?')
		{
   
			if(s1[i]<s2[i])
			{
   
				r1=0;
				break;
			}
		}
		else if(s1[i]=='?' && s2[i]=='?')
		{
   
			r1=(ll)r1*55%mod;
		}
		else if(s1[i]!='?')
		{
   
			r1=r1*(s1[i]-'0'+1)%mod;
		}
		else
			r1=r1*(10-(s2[i]-'0'))%mod;
	}

		// cal r2;
	for(int i=0;i<n;i++)
	{
   
		if(s1[i]!='?' && s2[i]!='?')
		{
   
			if(s1[i]>s2[i])
			{
   
				r2=0;
				break;
			}
		}
		// 00 11 22 29	99 
		else if(s1[i]=='?' && s2[i]=='?')
		{
   
			r2=(ll)r2*55%mod;
		}
		else if(s1[i]!='?')
		{
   
			r2=r2*(10-(s1[i]-'0'))%mod;
		}
		else
			r2=r2*(s2[i]-'0' + 1)%mod;
	}

		// cal r3;
	for(int i=0;i<n;i++)
	{
   
		if(s1[i]!='?' && s2[i]!='?')
		{
   
			if(s1[i]!=s2[i])
			{
   
				r3=0;
				break;
			}
		}
		else if(s1[i]==s2[i])
		{
   
			r3=r3*10%mod;
		}
	}
	cout << ((ans - r1 - r2 + r3)%mod+mod)%mod <<endl;
	return 0;
}

dp代码：

#include<iostream>
#include<cstring>
using namespace std;
const int N=100010;
const int mod=1e9+7;
typedef long long ll;
string s1,s2;
ll f[N][4];// f[i][0] 考虑前i个只有s[j]==w[j]的情况
// f[i][1]	只有s[j]>w[j]的情况
// f[i][2] 	只有s[j]<w[j]
// f[i][3]	合法状态
int main()
{
   
	int n;
	cin >> n;
	cin >> s1;
	cin >> s2;
	s1=' '+s1;
	s2=' '+s2;
	f[0][0]=1;
	for(int i=1;i<=n;i++)
	{
   
		if(s1[i]=='?'&&s2[i]=='?')
		{
   
			for(char j='0';j<='9';j++)
				for(char k='0';k<='9';k++)
				{
   
					if(j>k)
					{
   
						f[i][3]+=f[i-1][3];
						f[i][3]+=f[i-1][2];
						f[i][1]+=f[i-1][0];
						f[i][1]+=f[i-1][1];
					}
					else if(j==k)
					{
   
						f[i][0]+=f[i-1][0];
						f[i][1]+=f[i-1][1];
						f[i][2]+=f[i-1][2];
						f[i][3]+=f[i-1][3];
					}	
					else	if(j<k)
					{
   
						f[i][3]+=f[i-1][1];
						f[i][3]+=f[i-1][3];
						f[i][2]+=f[i-1][0];
						f[i][2]+=f[i-1][2];
					}
				}
		}
		else if(s1[i]=='?')
		{
   
			for(char j='0';j<='9';j++)
			{
   	
				if(j==s2[i])
				{
   
					f[i][0]+=f[i-1][0];
					f[i][3]+=f[i-1][3];
					f[i][2]+=f[i-1][2];
					f[i][1]+=f[i-1][1];
				}
				else if(j>s2[i])
				{
   
						f[i][3]+=f[i-1][3];
						f[i][3]+=f[i-1][2];
						f[i][1]+=f[i-1][0];
						f[i][1]+=f[i-1][1];
				}
				else if(j<s2[i])
				{
   
						f[i][3]+=f[i-1][1];
						f[i][3]+=f[i-1][3];
						f[i][2]+=f[i-1][0];
						f[i][2]+=f[i-1][2];
				}
			}	
		}
		else if(s2[i]=='?')
		{
   
			for(char j='0';j<='9';j++)
			{
   	
				if(j==s1[i])
				{
   
					f[i][0]+=f[i-1][0];
					f[i][3]+=f[i-1][3];
					f[i][2]+=f[i-1][2];
					f[i][1]+=f[i-1][1];
				}
				else if(j<s1[i])
				{
   
						f[i][3]+=f[i-1][3];
						f[i][3]+=f[i-1][2];
						f[i][1]+=f[i-1][0];
						f[i][1]+=f[i-1][1];
				}
				else if(j>s1[i])
				{
   
						f[i][3]+=f[i-1][1];
						f[i][3]+=f[i-1][3];
						f[i][2]+=f[i-1][0];
						f[i][2]+=f[i-1][2];
				}
			}	
		}
		else	
		{
   
			if(s1[i]==s2[i])
			{
   
				f[i][0]+=f[i-1][0];
				f[i][1]+=f[i-1][1];
				f[i][3]+=f[i-1][3];
				f[i][2]+=f[i-1][2];
			}
			else if(s1[i]>s2[i])
			{
   
				f[i][3]+=f[i-1][3];
				f[i][3]+=f[i-1][2];
				f[i][1]+=f[i-1][1];
				f[i][1]+=f[i-1][0];
			}
			else	
			{
   
				f[i][3]+=f[i-1][3];
				f[i][3]+=f[i-1][1];
				f[i][2]+=f[i-1][2];
				f[i][2]+=f[i-1][0];
			}
		}
		f[i][0]%=mod;
		f[i][1]%=mod;
		f[i][2]%=mod;
		f[i][3]%=mod;
	}
	cout<<f[n][3]<<endl;
	return 0;
}