Div. 2 Codeforces Round #822 A-F( 三 ) _生活百科

那么有如下公式：
\[\begin{aligned} f(n,m) &= \sum_{i = 0}^{m-1} [parity(i) \neq parity(n+i)]\\ &= 2\sum_{k = 0}^{\frac{m}{2}-1} [parity(2k) \neq parity(n+2k)]\\ &= 2\sum_{k = 0}^{\frac{m}{2}-1} [parity(k) \neq parity(\frac{n}{2}+k)]\\ &= 2f(\frac{n}{2},\frac{m}{2})\end{aligned}\]

\(n\) 为奇数，有如下关系：
\[\begin{aligned} && &parity(2k) \neq parity(n+2k) \\ &\Leftrightarrow& &parity(2k) = parity(n+2k-1)\\ &\Leftrightarrow& &parity(k) = parity(\frac{n-1}{2}+k)\\\end{aligned}\]以及，
\[\begin{aligned} && &parity(2k+1) \neq parity(n+2k+1) \\ &\Leftrightarrow& &parity(2k) = parity(n+2k+1)\\ &\Leftrightarrow& &parity(k) = parity(\frac{n+1}{2}+k)\\\end{aligned}\]证明同上。
\[\begin{aligned} f(n,m) &= \sum_{i = 0}^{m-1} [parity(i) \neq parity(n+i)]\\ &= \sum_{k = 0}^{\frac{m}{2}-1} ([parity(2k) = parity(n+2k-1)] + [parity(2k) = parity(n+2k+1)])\\ &= \sum_{k = 0}^{\frac{m}{2}-1} ([parity(k) = parity(\frac{n-1}{2}+k)] + [parity(k) = parity(\frac{n+1}{2}+k)])\\ &= m - f(\frac{n-1}{2},\frac{m}{2}) - f(\frac{n+1}{2},\frac{m}{2})\end{aligned}\]

至此，我们就可以通过记忆化搜索进行求解了。
时间复杂度 \(O(\log n \log m)\)
空间复杂度 \(O(\log n \log m)\)
代码

#include <bits/stdc++.h>#define ll long longusing namespace std;bool check(ll a, ll b) {return __builtin_parityll(a) != __builtin_parityll(b);}map<pair<ll, ll>, ll> mp;ll f(ll n, ll m) {if (m == 0) return 0;if (mp.count({ n,m })) return mp[{n, m}];if (m & 1) return mp[{n, m}] = f(n, m - 1) + check(m - 1, n + m - 1);if (n & 1) return mp[{n, m}] = m - f(n / 2, m / 2) - f((n + 1) / 2, m / 2);else return mp[{n, m}] = 2 * f(n / 2, m / 2);}bool solve() {ll n, m;cin >> n >> m;cout << f(n, m) << '\n';return true;}int main() {std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t--) {if (!solve()) cout << -1 << '\n';}return 0;}

【Div. 2 Codeforces Round #822A-F】