社区讨论

求调

CF296B Yaroslav and Two Strings参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@m1gjlfye
此快照首次捕获于
2024/09/24 22:39
去年
此快照最后确认于
2024/09/25 14:41
去年
查看原帖
CPP
#include <bits/stdc++.h>
typedef long long ll;
#define int long long

const int N = 1e5 + 10, mod = 1e9 + 7;

int n; 
int dp[2][2][2]; 

char a[N], b[N]; 

signed main() {

//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);

	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);

	std::cin >> n;
	
	for (int i = 1; i <= n; ++ i) std::cin >> a[i];
	for (int i = 1; i <= n; ++ i) std::cin >> b[i]; 
	
	dp[0][0][0] = 1; 
	for (int i = 1; i <= n; ++ i) {
		int smaller = 45ll, bigger = 45ll, same = 10ll;  
		bool f1 = a[i] == '?', f2 = b[i] == '?';
		if (!f1 && !f2) smaller = a[i] < b[i], bigger = a[i] > b[i], same = a[i] == b[i];
		else if (!f1 && f2) smaller = '9' - a[i], bigger = a[i] - '0', same = 1; 
		else if (!f2 && f1) smaller = '9' - b[i], bigger = b[i] - '0', same = 1; 
		dp[i & 1][0][0] = dp[i & 1 ^ 1][0][0] * same % mod;
		dp[i & 1][0][1] = (dp[i & 1 ^ 1][0][0] * smaller % mod + dp[i & 1 ^ 1][0][1] * (smaller + same) % mod) % mod;
		dp[i & 1][1][0] = (dp[i & 1 ^ 1][0][0] * bigger % mod + dp[i & 1 ^ 1][1][0] * (bigger + same) % mod) % mod;
		dp[i & 1][1][1] = (dp[i & 1 ^ 1][1][1] * (smaller + bigger + same) % mod + dp[i & 1 ^ 1][0][1] * bigger % mod + dp[i & 1 ^ 1][1][0] * smaller % mod) % mod;
	}
	std::cout << dp[n & 1][1][1] << "\n"; 
	

	return 0;
}

回复

0 条回复,欢迎继续交流。

正在加载回复...