题目：
2019-2020 ICPC 南昌现场赛 M：XOR Sum
题意：
定义
f
(
i
,
k
)
=
1
⨁
2
⨁
3
⨁
.
.
.
.
.
.
⨁
i
k
−
1
⨁
i
k
f(i,k)=1\bigoplus 2\bigoplus 3\bigoplus ……\bigoplus i^k-1\bigoplus i^k
f
(
i
,
k
)
=
1
⨁
2
⨁
3
⨁
.
.
.
.
.
.
⨁
i
k
−
1
⨁
i
k
，求
∑
k
=
1
t
∑
i
=
x
y
f
(
i
,
k
)
\sum_{k=1}^{t}\sum_{i=x}^{y}f(i,k)
∑
k
=
1
t
∑
i
=
x
y
f
(
i
,
k
)
模
1
e
9
+
7
1e9+7
1
e
9
+
7
的结果
分析：
若
x
x
x
是偶数，则
x
⨁
x
+
1
=
1
x\bigoplus x+1=1
x
⨁
x
+
1
=
1
，
x
⨁
x
+
1
⨁
x
+
2
⨁
x
+
3
=
0
x\bigoplus x+1\bigoplus x+2\bigoplus x+3=0
x
⨁
x
+
1
⨁
x
+
2
⨁
x
+
3
=
0
，所以有：
f
(
i
,
k
)
=
{
i
k
(
i
k
m
o
d
4
=
0
)
1
(
i
k
m
o
d
4
=
1
)
i
k
+
1
(
i
k
m
o
d
4
=
2
)
0
(
i
k
m
o
d
4
=
3
)
f(i,k)=\begin{cases} & i^k~~~~~~~\text(i^k~mod~4=0) \\ & 1~~~~~~~~\text( i^k~mod~4=1) \\ & i^k+1\text( i^k~mod~4=2) \\ & 0~~~~~~~~\text( i^k~mod~4=3) \end{cases}
f
(
i
,
k
)
=
⎩
⎪
⎪
⎪
⎨
⎪
⎪
⎪
⎧
i
k
(
i
k
m
o
d
4
=
0
)
1
(
i
k
m
o
d
4
=
1
)
i
k
+
1
(
i
k
m
o
d
4
=
2
)
0
(
i
k
m
o
d
4
=
3
)
题目所求化简为两类：
∑
k
=
1
t
∑
i
=
x
y
i
k
[
i
k
m
o
d
4
=
0
o
r
2
]
+
∑
k
=
1
t
∑
i
=
x
y
[
i
k
m
o
d
4
=
1
o
r
2
]
\sum_{k=1}^{t}\sum_{i=x}^{y}i^k[i^k~mod~4=0~or~2]+\sum_{k=1}^{t}\sum_{i=x}^{y}[i^k~mod~4=1~or~2]
k
=
1
∑
t
i
=
x
∑
y
i
k
[
i
k
m
o
d
4
=
0
o
r
2
]
+
k
=
1
∑
t
i
=
x
∑
y
[
i
k
m
o
d
4
=
1
o
r
2
]
第一类
：发现当且仅当
i
i
i
为偶数时，
i
k
m
o
d
4
=
0
o
r
2
i^k~mod~4=0~or~2
i
k
m
o
d
4
=
0
o
r
2
，那么得到:
∑
k
=
1
t
∑
i
=
x
y
i
k
[
i
k
m
o
d
4
=
0
o
r
2
]
=
∑
k
=
1
t
2
k
∑
i
=
⌊
x
+
1
2
⌋
⌊
y
2
⌋
i
k
\sum_{k=1}^{t}\sum_{i=x}^{y}i^k[i^k~mod~4=0~or~2]=\sum_{k=1}^{t}2^k\sum_{i=\left \lfloor \frac{x+1}{2} \right \rfloor}^{\left \lfloor \frac{y}{2} \right \rfloor}i^k
k
=
1
∑
t
i
=
x
∑
y
i
k
[
i
k
m
o
d
4
=
0
o
r
2
]
=
k
=
1
∑
t
2
k
i
=
⌊
2
x
+
1
⌋
∑
⌊
2
y
⌋
i
k
这个是可以枚举
k
k
k
，拉格朗日插值算幂次和，复杂度为
O
(
t
2
)
O(t^2)
O
(
t
2
)
，显然是跑不过的，更换枚举项看看？？
∑
k
=
1
t
2
k
∑
i
=
⌊
x
+
1
2
⌋
⌊
y
2
⌋
i
k
=
∑
i
=
⌊
x
+
1
2
⌋
⌊
y
2
⌋
∑
k
=
1
t
(
2
i
)
k
\sum_{k=1}^{t}2^k\sum_{i=\left \lfloor \frac{x+1}{2} \right \rfloor}^{\left \lfloor \frac{y}{2} \right \rfloor}i^k=\sum_{i=\left \lfloor \frac{x+1}{2} \right \rfloor}^{\left \lfloor \frac{y}{2} \right \rfloor}\sum_{k=1}^{t}(2i)^k
k
=
1
∑
t
2
k
i
=
⌊
2
x
+
1
⌋
∑
⌊
2
y
⌋
i
k
=
i
=
⌊
2
x
+
1
⌋
∑
⌊
2
y
⌋
k
=
1
∑
t
(
2
i
)
k
设
g
(
i
)
=
∑
k
=
1
t
i
k
g(i)=\sum_{k=1}^{t}i^k
g
(
i
)
=
∑
k
=
1
t
i
k
，
S
(
x
)
=
∑
i
=
0
x
g
(
i
)
S(x)=\sum_{i=0}^{x}g(i)
S
(
x
)
=
∑
i
=
0
x
g
(
i
)
，
S
(
x
)
S(x)
S
(
x
)
就是一个最高次为
t
+
1
t+1
t
+
1
的多项式，和
南昌网络赛B：Polynomial
差不多，最后的答案就是
S
(
⌊
y
2
⌋
)
−
S
(
⌊
x
+
1
2
⌋
)
S(\left \lfloor \frac{y}{2} \right \rfloor)-S(\left \lfloor \frac{x+1}{2} \right \rfloor)
S
(
⌊
2
y
⌋
)
−
S
(
⌊
2
x
+
1
⌋
)
，拉格朗日插值直接算即可
第二类：
i
m
o
d
4
=
2
i~mod~4=2
i
m
o
d
4
=
2
时，
k
=
1
k=1
k
=
1
才会有贡献；
i
m
o
d
4
=
3
i~mod~4=3
i
m
o
d
4
=
3
时，
k
k
k
为偶数时才有
i
k
m
o
d
4
=
1
i^k~mod~4=1
i
k
m
o
d
4
=
1
；
i
m
o
d
4
=
1
i~mod~4=1
i
m
o
d
4
=
1
时，
k
k
k
取任意值都有贡献，这部分都可以
O
(
1
)
O(1)
O
(
1
)
计算
代码：
#include <bits/stdc++.h>
#define x first
#define y second
#define pii pair<int,int>
#define sz(x) (int)(x).size()
#define Max(x,y) (x)>(y)?(x):(y)
#define Min(x,y) (x)<(y)?(x):(y)
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long LL;
const int mod = 1e9+7;
const int maxn = 1e6+16;
LL per[maxn],suf[maxn],fac[maxn],S[maxn];
LL qpow(LL a,LL x,LL mod){
LL res = 1ll;
while(x){
if(x&1) res = res * a % mod;
a = a * a % mod;
x >>= 1;
}
return res;
}
//预处理阶乘的逆元
void init1(int n,int mod){
LL res = 1;
for(int i = 1;i <= n+2; ++i) res = res*i%mod;
fac[n+2] = qpow(res,mod-2,mod);
for(int i = n+1;i >= 0; --i) fac[i] = (i+1)*fac[i+1]%mod;
}
//给定最高次为n的多项式的n+1个点分别为：(0,f0),(1,f1),(2,f2)...(n,fn),求f(k)的值
LL Lagrange(LL f[],int n,LL k){
if(k <= n) return f[k];
per[0] = suf[n+1] = 1;
for(int i = 0;i <= n; ++i) per[i+1] = (k-i)%mod*per[i]%mod;
for(int i = n;i >= 0; --i) suf[i] = (k-i)%mod*suf[i+1]%mod;
LL fk = 0;
for(int i = 0;i <= n; ++i){
LL tep = f[i]*per[i]%mod*suf[i+1]%mod*fac[i]%mod*fac[n-i]%mod;
if((n-i)&1) fk = (fk-tep+mod)%mod;
else fk = (fk+tep)%mod;
}
return fk;
}
//计算 [L,R] 有多少个数 mod 4 == a
LL cal(LL L,LL R,int a){
LL sum1 = (R-a)/4;
if(R >= a) sum1++;
LL sum2 = (L-1-a)/4;
if(L-1 >= a) sum2++;
return (sum1-sum2)%mod;
}
LL solve(LL t,LL x,LL y){
LL ans = Lagrange(S,t+1,y/2)-Lagrange(S,t+1,(x+1)/2-1)+mod;
ans += cal(x,y,2);
ans += t*cal(x,y,1);
ans += t/2*cal(x,y,3);
return ans % mod;
}
int main(){
LL t,x,y;
cin >> t >> x >> y;
init1(t+5,mod);
for(int i = 1;i <= t+1; ++i){
S[i] = (qpow(2*i,t+1,mod)-2*i+mod)*qpow(2*i-1,mod-2,mod)%mod+S[i-1];
if(S[i] >= mod) S[i] -= mod;
}
cout << solve(t,x,y) << '\n';
return 0;
}