网站建设服务合同书,临沂做网站的,做的网站如何投入搜索引擎,可以制作试卷的app正题
题目链接:https://www.luogu.com.cn/problem/P7717 题目大意
求有多少个长度为nnn的序列aaa满足#xff0c;都在[0,k][0,k][0,k]的范围内且满足mmm个限制刑如#xff1a;axxorayza_x\ xor\ a_yzax xor ayz 0≤n,m≤5105,0≤k2300\leq n,m\leq 5\times 10^5,0\…正题
题目链接:https://www.luogu.com.cn/problem/P7717 题目大意
求有多少个长度为nnn的序列aaa满足都在[0,k][0,k][0,k]的范围内且满足mmm个限制刑如axxorayza_x\ xor\ a_yzax xor ayz
0≤n,m≤5×105,0≤k2300\leq n,m\leq 5\times 10^5,0\leq k2^{30}0≤n,m≤5×105,0≤k230 解题思路
首先假设有合法方案那么对于一个位置axa_xax确定之后与它直接或间接限制的aya_yay都将被确定。
我们可以设限制为一条边然后先dfsdfsdfs判断一次是否限制之间没有冲突。
然后考虑对于每个联通块我们随意找到一个位置xxx那么其他的点都将被表达为axxorwa_x\ xor\ wax xor w的形式。
然后我们要求找到有多少个axa_xax满足对于所有的www都有axxorw≤ka_x\ xor\ w\leq kax xor w≤k。
这个可以用TrieTrieTrie数来做每次封闭的是一个子树直接处理就好了。
时间复杂度O(nlogk)O(n\log k)O(nlogk) code
#includecstdio
#includecstring
#includealgorithm
#includestack
#define ll long long
using namespace std;
const ll N5e510,P1e97;
struct node{ll to,next,w;
}a[N1];
ll n,m,k,tot,ls[N],z[N];
ll cnt,t[N][2],res,ans1;
bool v[N];stackll s;
void addl(ll x,ll y,ll w){a[tot].toy;a[tot].nextls[x];ls[x]tot;a[tot].ww;return;
}
bool dfs(ll x){v[x]1;s.push(z[x]);for(ll ils[x];i;ia[i].next){ll ya[i].to;if(v[y]){if((z[x]^a[i].w)!z[y])return 1;}else{z[y]z[x]^a[i].w;if(dfs(y))return 1; }}return 0;
}
void Limit(ll x,ll w,ll p){if(x-1||p0)return;if(!x){xcnt;t[x][0]t[x][1]0;}if((kp)1)Limit(t[x][(wp)1^1],w,p-1);else{t[x][(wp)1^1]-1;Limit(t[x][(wp)1],w,p-1);}return;
}
void Count(ll x,ll L,ll R){if(Lk)return;if(x-1)res-min(R,k)-L1;if(x0)return;ll mid(LR)1;Count(t[x][0],L,mid);Count(t[x][1],mid1,R);return;
}
signed main()
{scanf(%lld%lld%lld,n,m,k);for(ll i1;im;i){ll x,y,w;scanf(%lld%lld%lld,x,y,w);addl(x,y,w);addl(y,x,w);}res0;for(ll i1;in;i){if(v[i])continue;cntt[0][0]0;if(dfs(i))return puts(0)0;while(!s.empty())Limit(t[0][0],s.top(),29),s.pop();resk1;Count(1,0,(130)-1);ansans*res%P;}printf(%lld\n,ans);return 0;
}
