二项式定理前置知识
二项式系数相关性质：
- 对称性： 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={ Cn2nCn2n−1=Cn2n+1 - 二项式系数之和： C n 0 + C n 1 + C n 2 + C n 3 + . . . + C n n − 1 + C n n = 2 n C_n^0+C_n^1+C_n^2+C_n^3+...+C_n^{n-1}+C_n^n=2^n Cn0+Cn1+Cn2+Cn3+...+Cnn−1+Cnn=2n
- 二项式奇数项系数之和等于偶数项系数之和，即
C n 1 + C n 3 + C n 5 + . . . = C n 0 + C n 2 + C n 4 + C n 6 + . . . = 2 n − 1 C_n^1+C_n^3+C_n^5+...=C_n^0+C_n^2+C_n^4+C_n^6+...=2^{n-1} Cn1+Cn3+Cn5+...=Cn0+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; } 讯享网
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/19521.html