社区讨论
求调
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 条回复,欢迎继续交流。
正在加载回复...