二项式定理前置知识
二项式系数相关性质：
- 对称性：
C
n
m
=
C
n
n
?
m
C_n^m = C_n^{n-m}
Cnm?=Cnn?m?
- 增减性与最大值：二项式系数前半部分逐渐增大，后半部分逐渐减小，中间取最大值。
最大值
m
a
x
=
{
C
n
n
2
C
n
n
?
1
2
=
C
n
n
+
1
2
max=\begin{cases} C_n^{\frac{n}{2}} \\ C_n^{\frac{n-1}{2}}=C_n^{\frac{n+1}{2}}\end{cases}
max={Cn2n??Cn2n?1??=Cn2n+1??? - 二项式系数之和：
C
n
1
+
C
n
2
+
C
n
3
+
.
.
.
+
C
n
n
?
1
+
C
n
n
=
2
n
C_n^1+C_n^2+C_n^3+...+C_n^{n-1}+C_n^n=2^n
Cn1?+Cn2?+Cn3?+...+Cnn?1?+Cnn?=2n
- 二项式奇数项系数之和等于偶数项系数之和，即
C
n
1
+
C
n
3
+
C
n
5
+
.
.
.
=
C
n
2
+
C
n
4
+
C
n
6
+
.
.
.
=
2
n
?
1
C_n^1+C_n^3+C_n^5+...=C_n^2+C_n^4+C_n^6+...=2^{n-1}
Cn1?+Cn3?+Cn5?+...=Cn2?+Cn4?+Cn6?+...=2n?1
题目链接
https://codeforces.com/problemset/problem/1614/C
给定一个序列一些子区间的 所有元素的 或 值，求出原序列所有子序列异或值的和
- 如果整个序列构造出来，如何求子序列的异或和？
思路：按位考虑求每一位对答案的贡献
子序列的话，可以考虑排列组合的方法求所有情况的贡献。
设第i位为1的数字有k个，则为0的数有n-k个。异或值只有奇数个1才会产生贡献，所以从k个1中选择奇数个。而剩下的0可以随便选择，情况为
2
n
?
k
2^{n-k}
2n?k。
产生的贡献为
w
=
{
2
i
?
1
?
(
C
k
1
+
C
k
3
+
.
.
.
+
C
k
k
?
1
)
?
2
n
?
k
,
k
为
偶
数
2
i
?
1
?
(
C
k
1
+
C
k
3
+
.
.
.
+
C
k
k
?
1
)
?
2
n
?
k
，
k
为
奇
数
w =\begin{cases}2^{i-1}*(C^1_k+C^3_k+...+C^{k-1}_k)*2^{n-k},k为偶数\\2^{i-1}*(C^1_k+C^3_k+...+C^{k-1}_k)*2^{n-k} ，k为奇数\end{cases}
w={2i?1?(Ck1?+Ck3?+...+Ckk?1?)?2n?k,k为偶数2i?1?(Ck1?+Ck3?+...+Ckk?1?)?2n?k，k为奇数?
根据二项式定理得：
w
=
2
i
?
1
?
2
k
?
1
?
2
n
?
k
=
2
i
?
1
?
2
n
?
1
w=2^{i-1}*2^{k-1}*2^{n-k}=2^{i-1}*2^{n-1}
w=2i?1?2k?1?2n?k=2i?1?2n?1
可见： 只要该位中至少有一个数为1，就会产生贡献，而且产生的贡献相同（只有对应的i不同） - 所以构造序列就没有必要了。只需要对所有的区间或值或起来，得到最终的一个值，如果对应位为1，那么该位必然至少有一个
1,就可以产生贡献。 - 计算：相同项保留，只有
i不同，这一项所有的相加，就是该位为1时对应的二进制值相加，这一个项所有相加的结果为 所有值的或。
#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9+7,N = 2e5+5;
typedef long long ll;
int n,m;
ll fact[N];
void solve()
{
int l,r,x;
cin>>n>>m;
ll res = 0;
while(m--)
{
cin>>l>>r>>x;
res |= x;
}
cout<<res * fact[n-1] % mod<<endl;
}
int main()
{
int t;
cin>>t;
fact[0] = 1;
for(int i=1;i<N;i++) fact[i] = fact[i-1]*2%mod;
while(t--) solve();
return 0;
}
|