ZJUT12 Day3

1、CF 1342C Yet Another Counting Problem

tags：数学

关键点要找到周期性。

$x\%a\%b=x\%b\%a$，然后把$x$变为$x+lcm(a,b)$会发现结果和$x$一样。

那么分成若干个周期分别计算即可。主要时间花在找规律上。

#include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { int t; cin >> t; while (t--) { int a, b, q; cin >> a >> b >> q; ll lcm = a / __gcd(a, b) * b; vector <ll> A(lcm), B(lcm); for (int i = 0; i < lcm; ++i) A[i] = i % a % b, B[i] = i % b % a; vector <ll> tot(lcm); tot[0] = 1; for (int i = 1; i < lcm; ++i) if (A[i] == B[i]) tot[i] = tot[i - 1] + 1; else tot[i] = tot[i - 1]; function <ll(ll)> query = [&](ll r) { ll k = r / lcm; return 1ll * k * tot[lcm - 1] + tot[r % lcm]; }; while (q--) { ll l, r; cin >> l >> r; cout << r - l + 1 - (query(r) - query(l - 1)) << ' '; } cout << endl; } return 0; }

2、CF 1426F Number of Subsequences

tags：字符串，dp

设$dp[i][j]$表示原串第$i$位匹配到$abc$串的第$j$位的方案数和。

那么当$s[i]=a,b,c$时转移方程是很简单的，即第$i-1$位的$j$位方案数加上$i-1$位的$j-1$位方案数。

当$s[i]=?$时，因为$s[i]$此时有三种选法，所以$dp[i][j]$先要加上$3\ast dp[i-1][j]$，再加上把$?$选为$j$时的方案数。这里的转移比较难想到。

此外在问号的情况下选择完某个字符要记得把$dp[i][0]$也乘上3。边界条件要注意。

顺便压了一下空间。

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN = 2e5 + 10, MOD = 1e9 + 7; char s[MAXN]; ll dp[4] = {1}; int main() { int n; cin >> n; scanf("%s", s + 1); for (int i = 1; i <= n; ++i) { if (s[i] == 'c') dp[3] = (dp[3] + dp[2]) % MOD; else if (s[i] == 'b') dp[2] = (dp[2] + dp[1]) % MOD; else if (s[i] == 'a') dp[1] = (dp[1] + dp[0]) % MOD; else { for (int i = 3; i > 0; --i) dp[i] = (3ll * dp[i] + dp[i - 1]) % MOD; dp[0] = (3ll * dp[0]) % MOD; } } cout << dp[3] << endl; return 0; }