牛客提高R5 A.同余方程
程序员文章站
2022-03-10 15:10:43
题意 "题目链接" Sol 设$solve(x, y)$表示$i \in [0, x], j \in [0, y]$满足题目要求的方案数 首先容斥一下,$ans = solve(r_1, r_2) solve(l_1 1, r_2) solve(l_2 1, r_1) + solve(l_1 1, ......
题意
sol
设\(solve(x, y)\)表示\(i \in [0, x], j \in [0, y]\)满足题目要求的方案数
首先容斥一下,\(ans = solve(r_1, r_2) - solve(l_1 - 1, r_2) - solve(l_2 - 1, r_1) + solve(l_1 -1, l_2 - 1)\)
然后按照套路按位拆分,这里拆的时候是直接对\(x, y\)进行拆分
这样就把问题转换成了看起来似乎简单一些的问题
假设拆完后的数是
110011101
1011
我们只要对于任意一对为1的位,求出小于该位的所有合法解即可
比如\(i = 3, j = 1\)我们要计算的就是\([110010000, 110010111]\)与\([1000, 1001]\)内的合法解
两种都可以写成\([v, v + 2^k]\)的性质
先考虑一种简单的情况,即\(v = 0\)
假设\(i > j\),那么\(\forall z = x \oplus y \leqslant 2^i\), 对于任意的\(x \leqslant 2^j\),都会有唯一的\(y\)与之对应
那么我们只要数出\([0, 2^i]\)中\(\% m == 0\)的数的个数,再乘上\(2^j\)即可
存在\(a[i]\)的限制实际上是一样的。
但是这样统计到的实际上是开区间的信息,只要在右端点处+1即可
#include<iostream> #include<algorithm> #define ll long long using namespace std; const ll mod = 998244353; ll l1, r1, l2, r2, m; ll add(ll x, ll y) { return (x + y >= mod) ? (x + y - mod) : (x + y); } ll calc(ll l, ll r) { if(l == 0) return ((r / m) + 1) % mod; return (r / m - (l - 1) / m) % mod; } ll solve(ll x, ll y) { ll ans = 0; for(ll i = 0, p1 = x; p1; i++, p1 >>= 1) { for(ll j = 0, p2 = y; p2; j++, p2 >>= 1) { if((p1 & 1) && (p2 & 1)) { ll x = i, y = j; if(x < y) swap(x, y); ll ll = ((((p1 ^ 1) << i) ^ ((p2 ^ 1) << j)) >> x) << x; ans = add(ans, (1ll << y) % mod * calc(ll, ll + (1ll << x) - 1) % mod); //cout << ans << endl; } } } // cout << ans << endl; return ans; } int main() { cin >> l1 >> r1 >> l2 >> r2 >> m; cout << (solve(r1 + 1, r2 + 1) - solve(l1, r2 + 1) + mod - solve(r1 + 1, l2) + mod + solve(l1, l2) + mod) % mod; return 0; } /* 1 1 1 1 1 */
上一篇: UART学习之路(三)基于STM32F103的USART实验
下一篇: 大寒和小寒哪个在前