写挂了
by Z_301 @ 2024-01-09 08:53:03
这种容斥是错的,能看一下吗?
```cpp
// Problem: Yaroslav and Two Strings
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF296B
// Memory Limit: 250 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define int long long
#define F(i,a,b) for(int i=(a);i<=(b);i++)
#define dF(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
inline int rd() {
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9') {
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9') {
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
inline void write(int x) {
if(x<0)x = ~x + 1, putchar('-');
if (x > 9) write(x / 10);
putchar(x % 10 + '0');
}
inline int lowbit(int x) {
return x&(-x);
}
typedef long long ll;
typedef pair<int,int> Pair;
const int N=200005,M=(N<<1),inf=0x3f3f3f3f,mod=1e9+7;
int n,ans,f[N][3];
int qpow(int a,int b){
int res=1;
for(;b;b>>=1){
if(b&1)res=res*a%mod;
a=a*a%mod;
}return res;
}
void solve(){
n=rd();string x,y;
cin>>x>>y;
x=" "+x,y=" "+y;
f[0][0]=f[0][1]=f[0][2]=1;
F(i,1,n){
if(x[i]=='?'&&y[i]=='?'){
ans+=2;
f[i][0]=f[i-1][0]*45%mod;
f[i][1]=f[i-1][1]*45%mod;
f[i][2]=f[i-1][2]*10%mod;
}else if(x[i]=='?'){
ans++;
f[i][0]=f[i-1][0]*(y[i]-'0')%mod;
f[i][1]=f[i-1][1]*(9-(y[i]-'0'))%mod;
f[i][2]=f[i-1][2];
}else if(y[i]=='?'){
ans++;
f[i][0]=f[i-1][0]*(9-(x[i]-'0'))%mod;
f[i][1]=f[i-1][1]*(x[i]-'0')%mod;
f[i][2]=f[i-1][2];
}else{
f[i][0]=f[i-1][0]*(x[i]<y[i])%mod;
f[i][1]=f[i-1][1]*(x[i]>y[i])%mod;
f[i][2]=f[i-1][2]*(x[i]==y[i])%mod;
}
}
ans=qpow(10,ans)-(f[n][0]+f[n][1]+f[n][2])%mod;
cout<<(ans%mod+mod)%mod<<endl;
}
signed main() {
int T=1;
while(T--) {
solve();
}
return 0;
}
```
@[Z_301](/user/175087)
by 紊莫 @ 2024-01-10 18:52:51
0表示严格小于,1是严格大于,2是等于
by 紊莫 @ 2024-01-10 18:54:55