T1
题解
这道题应该是可以通过组合数直接计算的，但是我不会数学证明，所以就用了一种简单粗暴的方式。
ans=∑2|iC(n,i)∗C(n,n−i)
ans=∑2|iC(n,i)2
1018
肯定不能直接枚举，如果要计算的话也需要用到lucas定理。观察发现这题的模数比较小，所以从模数入手。 考虑Lucas定理。
n=a[0]∗p0+a[1]∗p1+a[2]∗p2+...
m=b[0]∗p0+b[1]∗p1+b[2]∗p2+...
对n,m进行p进制分解，那
C(n,m)%p=C(a[0],b[0])∗C(a[1],b[1])∗....%p
如果某一位
a[i]<b[i]
，那么答案在模p意义下一定是0，也就是没有贡献，所以我们现在考虑计算出所有有贡献的答案。 确定了a之后，我们就可以通过枚举计算每一位的选择。因为i必须是偶数，所以我们可以进行数位dp.
f[i][0/1]
表示确定了第i位后，m是偶数/奇数的总贡献。 转移过程直接看代码吧。
代码
using namespace std;
LL jc[
2000000],inv[
2000000],f[
10][
10],mi[
10];
LL n;
int a[
10],cnt;
LL quickpow(LL num,
int x)
{
LL ans=
1,base=num
%p;
while (
x) {
if (
x&
1) ans=ans
*base%p;
x>>=
1;
base=base
*base%p;
}
return ans;
}
LL calc(
int n,
int m)
{
return jc[n]
*inv[
m]
%p*inv[n-
m]
%p;
}
LL pow(LL
x){
return x*x%p;
}
int main()
{
freopen(
"a.in",
"r",stdin);
freopen(
"a.out",
"w",stdout);
cin>>n;
jc[
0]=
1;
for (
int i=
1;i<=p;i++) jc[i]=(LL)jc[i-
1]
*i%p;
for (
int i=
0;i<=p;i++) inv[i]=quickpow(jc[i],p-
2);
LL
x=n;
while (
x) {
a[++cnt]=(LL)
x%p;
x/=p;
}
mi[
0]=
1;
for (
int i=
1;i<=cnt;i++) mi[i]=mi[i-
1]
*mi[i-
1]
%p;
for (
int i=
0;i<=a[
1];i++)
(f[
1][i
*mi[
0]
%2]+=pow(calc(a[
1],i)))
%=p;
for (
int i=
2;i<=cnt;i++)
for (
int j=
0;j<=a[i];j++){
LL t=j
*mi[i-
1]
%2;
(f[i][t]+=f[i-
1][
0]
*pow(calc(a[i],j))
%p)
%=p;
(f[i][(t+
1)
%2]+=f[i-
1][
1]
*pow(calc(a[i],j))
%p)
%=p;
}
cout<<f[cnt][
0]<<endl;
}
T3
题解
可持久化trie 首先我们考虑如果只有异或操作该怎么做。因为是对全局取xor，所以我们可以把要异或的值记录下来，每次查询的时候考虑上异或值即可，不会对trie的形态造成影响。 然后考虑and，对于每一位分开考虑，如果是and 1的话没有影响。关键就是and 0,会使所有数当前位的取值变成0。 or的话，如果是or 1,会使所有数当前位变成1。我们不妨对于每一位开一个标记数组，表示当前位是否全部相同以及值是多少。如果某一位在操作的过程中由值不全相同变成相同，那么我们就重构可持久化trie，如果某一位全部相同，我们就把所有数同一放到左儿子，方便查询。 因为每一位只有一次由不同变成相同的机会，所以重构的次数不会太多，最多只有30次。 注意异或的时候别忘了修改每一位的标记。
代码
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
#define N 100003
using namespace std;
int xornum,n,m,a[N],ch[N*
20][
2],size[N*
20],pd[N],opt[N],root[N],sz;
void insert(
int i,
int x)
{
int pre=root[i-
1];
root[i]=++sz;
int now=root[i];
for (
int i=
30;i>=
0;i--){
int t=(x>>i)&
1;
if (pd[i]) t=
0;
size[now]=size[pre]+
1;
ch[now][t^
1]=ch[pre][t^
1];
ch[now][t]=++sz;
now=ch[now][t]; pre=ch[pre][t];
}
size[now]=size[pre]+
1;
}
int query(
int i,
int j,
int x)
{
int ans=
0;
int R=i;
int L=j;
for (
int t=
30;t>=
0;t--) {
if (pd[t]) ans+=(
1<<t)*opt[t],R=ch[R][
0],L=ch[L][
0];
else {
int son=(xornum>>t)&
1;
int k=size[ch[R][son]]-size[ch[L][son]];
if (k>=x) {
ans+=(
1<<t)*
0;
R=ch[R][son],L=ch[L][son];
}
else {
x-=k;
ans+=(
1<<t)*
1;
R=ch[R][son^
1],L=ch[L][son^
1];
}
}
}
return ans;
}
int main()
{
freopen(
"c.in",
"r",stdin);
freopen(
"c.out",
"w",stdout);
scanf(
"%d%d",&n,&m);
for (
int i=
1;i<=n;i++)
scanf(
"%d",&a[i]);
insert(
1,
0);
for (
int i=
1;i<=n;i++)
insert(i+
1,a[i]);
for (
int i=
1;i<=m;i++) {
char s[
10];
scanf(
"%s",s+
1);
int l,r,x;
if (s[
1]==
'X') {
scanf(
"%d",&x);
xornum^=x;
for (
int j=
0;j<=
30;j++)
if (pd[j]&&((x>>j)&
1)) opt[j]^=
1;
}
if (s[
1]==
'O'){
scanf(
"%d",&x);
bool flag=
false;
for (
int j=
0;j<=
30;j++)
if ((x>>j)&
1) {
if (pd[j]) opt[j]=
1;
else{
flag=
true;
pd[j]=opt[j]=
1;
}
}
if (flag) {
sz=
0;
memset(size,
0,
sizeof(size));
memset(ch,
0,
sizeof(ch));
memset(root,
0,
sizeof(root));
insert(
1,
0);
for (
int j=
1;j<=n;j++) insert(j+
1,a[j]);
}
}
if (s[
2]==
'n'){
scanf(
"%d",&x);
bool flag=
false;
for (
int j=
0;j<=
30;j++)
if (((x>>j)&
1)==
0){
if (pd[j]) opt[j]=
0;
else{
flag=
true;
pd[j]=
1;opt[j]=
0;
}
}
if (flag){
sz=
0;
memset(size,
0,
sizeof(size));
memset(ch,
0,
sizeof(ch));
memset(root,
0,
sizeof(root));
insert(
1,
0);
for (
int j=
1;j<=n;j++) insert(j+
1,a[j]);
}
}
if (s[
2]==
's') {
scanf(
"%d%d%d",&l,&r,&x);
printf(
"%d\n",query(root[r+
1],root[l],x));
}
}
}
