宜春网站建设推广,企业网站建设建设,网站建设登录界面代码,软件下载安装免费文章目录CodeForces 1616H Keep XOR LowproblemsolutioncodeCodeForces gym102331 Bitwise XorproblemsolutioncodeCodeForces 1616H Keep XOR Low
problem
洛谷链接
solution
虽然选的是一个子集#xff0c;但本质还是二元限制。
这非常类似以前做过的题目#xff0c;已…
文章目录CodeForces 1616H Keep XOR LowproblemsolutioncodeCodeForces gym102331 Bitwise XorproblemsolutioncodeCodeForces 1616H Keep XOR Low
problem
洛谷链接
solution
虽然选的是一个子集但本质还是二元限制。
这非常类似以前做过的题目已知 ai,ka_i,kai,k求满足 ai⊕aj≤ka_i\oplus a_j\le kai⊕aj≤k 的 aja_jaj 个数。
这是一元限制常见解法是在 trie\text{trie}trie 树上统计。 紧贴 的思想。
具体而言就像数位 dpdpdp 一样贴着 xxx 二进制位的要求走如果 ddd 位为 111那么直接统计 trie\text{trie}trie 树该位 000 子树的个数然后继续往 111 那边走。
我们考虑采用同样的方法来解决本题。只不过此时的 aia_iai 同样未知。
直接设计 dfs(x,y,d):dfs(x,y,d):dfs(x,y,d): 目前在 ddd 二进制位从 x,yx,yx,y 子树中选取子集仅考虑 x−yx-yx−y 间限制的方案数且前 ddd 位都是紧贴的。
首先得从高到低考虑二进制位。初始调用函数 dfs(1,1,30)dfs(1,1,30)dfs(1,1,30)。插入以及统计子树内个数就略过了 xyxyxy。 kkk 的 ddd 位为 111。 直接返回 dfs(lson[x],rson[x],d−1)dfs(lson[x],rson[x],d-1)dfs(lson[x],rson[x],d−1)。 kkk 的 ddd 位为 000。 返回 dfs(lson[x],lson[x],d−1)dfs(rson[x],rson[y],d−1)dfs(lson[x],lson[x],d-1)dfs(rson[x],rson[y],d-1)dfs(lson[x],lson[x],d−1)dfs(rson[x],rson[y],d−1)。 这里不能乘法乱来否则就会包含 xxx 左右儿子组合等等这些异或在该位可是 111超过了 kkk 限制。 x≠yx\ne yxy。 kkk 的 ddd 位为 111。 返回 dfs(lson[x],rson[y],d−1)∗dfs(rson[x],lson[y],d−1)dfs(lson[x],rson[y],d-1)*dfs(rson[x],lson[y],d-1)dfs(lson[x],rson[y],d−1)∗dfs(rson[x],lson[y],d−1)。 实际上应该是两边都要 111 再乘表示仅从 x,yx,yx,y 的各一个儿子中选取的方案数直接乘就是要求 x,yx,yx,y 左右儿子中都要选择了。 最后还要 −1-1−1减去两边没一个选的空集。 这个乘法就包含了 xxx 左右儿子组合yyy 左右儿子组合x,yx,yx,y 左/右儿子组合等等的可能。 这些组合在这一位的异或都是 000都是松弛在限制下面的。 kkk 的 ddd 位为 000。 返回 dfs(lson[x],lson[y],d−1)dfs(rson[x],rson[y],d−1)dfs(lson[x],lson[y],d-1)dfs(rson[x],rson[y],d-1)dfs(lson[x],lson[y],d−1)dfs(rson[x],rson[y],d−1)。 但这里没有考虑到只选 xxx 内部的左右子树和只选 yyy 内部的左右子树的情况。 直接加上 (2siz[lson[x]]−1)(2siz[rson[x]]−1)(2siz[lson[y]]−1)(2siz[rson[y]]−1)(2^{siz[lson[x]]}-1)(2^{siz[rson[x]]}-1)(2^{siz[lson[y]]}-1)(2^{siz[rson[y]]}-1)(2siz[lson[x]]−1)(2siz[rson[x]]−1)(2siz[lson[y]]−1)(2siz[rson[y]]−1)。 为什么这里可以直接乘了而不是继续 dfsdfsdfs 下去呢 注意到如果 x≠yx\neq yxy那么之前必定是有一个更高位使得他们分叉。 而分叉的条件都是那个更高位上的 kkk 是 111。 所以这里可以直接 x/yx/yx/y 子树内部各自乱选反正异或起来至少在那个较高位都是 000。 一定是被限制松弛的方案数。
code
#include bits/stdc.h
using namespace std;
#define int long long
#define mod 998244353
#define maxn 150005
int n, m, root, cnt;
int a[maxn], mi[maxn], l[maxn * 30], r[maxn * 30], siz[maxn * 30];void insert( int now, int d, int x ) {if( ! now ) now cnt;siz[now] ;if( ! ~ d ) return;if( x d 1 ) insert( r[now], d - 1, x );else insert( l[now], d - 1, x );
}int dfs( int x, int y, int d ) {//-1是减去空集的情况数if( ! x ) return mi[siz[y]] - 1;if( ! y ) return mi[siz[x]] - 1;if( x y ) {if( ! ~ d ) return mi[siz[x]] - 1;else if( m d 1 ) return dfs( l[x], r[x], d - 1 );else return ( dfs( l[x], l[x], d - 1 ) dfs( r[x], r[x], d - 1 ) ) % mod;}else {if( ! ~ d ) return mi[siz[x]] * mi[siz[y]] % mod - 1;//1乘是有可能不选这个子树中的子集else if( m d 1 ) return ( dfs( l[x], r[y], d - 1 ) 1 ) * ( dfs( r[x], l[y], d - 1 ) 1 ) % mod - 1;else {int ans ( dfs( l[x], l[y], d - 1 ) dfs( r[x], r[y], d - 1 ) ) % mod;( ans ( mi[siz[l[x]]] - 1 ) * ( mi[siz[r[x]]] - 1 ) % mod ) % mod;( ans ( mi[siz[l[y]]] - 1 ) * ( mi[siz[r[y]]] - 1 ) % mod ) % mod;//这种情况计数是左右子树一定都选了的return ans;}}
}signed main() {scanf( %lld %lld, n, m ); mi[0] 1;for( int i 1, x;i n;i ) {scanf( %lld, x ), insert( root, 30, x );mi[i] ( mi[i - 1] 1 ) % mod;}printf( %lld\n, ( dfs( root, root, 30 ) mod ) % mod );return 0;
}还有一道类似的题目只不过限制变为了 ai⊕aj≥ka_i\oplus a_j\ge kai⊕aj≥k。但做法就完全不一样了。
CodeForces gym102331 Bitwise Xor
problem
CF链接
solution
一堆数按从高到低二进制考虑按第 www 位分为 0/10/10/1 两个集合第 www 位产生贡献肯定是两个数隶属不同的集合。
如此递归分层下去我们发现从小到大排序后只用考虑相邻两个数是否满足限制。
上述结论有一个数学化的表达abc⇒min(a⊕b,b⊕c)≤a⊕cabc\Rightarrow \min(a\oplus b,b\oplus c)\le a\oplus cabc⇒min(a⊕b,b⊕c)≤a⊕c。
可以大概理解为数相差越大二进制位的高位越有可能异或为 111异或结果越有可能更大。
因此可以将 aaa 从小到大排序设 fi:aif_i:a_ifi:ai 结尾的序列的方案数。
转移利用 trie\text{trie}trie 树的紧贴思想去求与 aia_iai 异或 ≥x\ge x≥x 的 aja_jaj 对应的方案数。
code
#include bits/stdc.h
using namespace std;
#define int long long
#define mod 998244353
#define maxn 300005
int n, m;
int a[maxn], cnt;
int trie[maxn * 65][2], sum[maxn * 65];void insert( int x, int val ) {for( int i 60, now 0;~ i;i -- ) {int k x i 1;if( ! trie[now][k] ) trie[now][k] cnt;now trie[now][k];( sum[now] val ) % mod;}
}int query( int x ) {int ans 0, now 0;for( int i 60;~ i;i -- ) {int k x i 1;if( m i 1 ) now trie[now][k ^ 1];else ( ans sum[trie[now][k ^ 1]] ) % mod, now trie[now][k];if( ! now ) break; //很有可能这个数比之大的不存在 那么now就会回到0 如果继续走下去就岔了}return ( ans sum[now] ) % mod;
}signed main() {scanf( %lld %lld, n, m );for( int i 1;i n;i ) scanf( %lld, a[i] );sort( a 1, a n 1 );int ans 0; //f[i]1\sum_{j,a_i^a_jm}f[j]for( int i 1;i n;i ) {int val query( a[i] ) 1; //1是自己单独一个的方案ans ( ans val ) % mod;insert( a[i], val );}printf( %lld\n, ans );return 0;
}
