算法之计算贡献

文章目录

• 计算贡献介绍
• 例题
• • 题目解析
  • 解题代码

计算贡献介绍

计算贡献是一种数学思维，把要求所有方案数种每一个方案总和的总和 转换成每一个元素i的贡献值乘以总方案数的总和

例题

题目解析

∑ w = 方 案 ∑ i = 1 n 在 w 方 案 下 i 天 的 快 乐 值 \sum_{w=方案} {\sum_{i=1}^n在w方案下i天的快乐值 \quad}\quad w=方案∑​i=1∑n​在w方案下i天的快乐值
可以转化成
∑ i = 1 n i 天 的 贡 献 值 （ 每 一 种 方 案 的 快 乐 值 总 和 ） ∗ 总 方 案 数 \sum_{i=1}^n {i天的贡献值（每一种方案的快乐值总和）} *总方案数\quad i=1∑n​i天的贡献值（每一种方案的快乐值总和）∗总方案数

接下来可以分成三种情况
当$2\ast i>n$ 时在第i天只能是第i个人 所以贡献为0
当$2\ast i+1>n$ 时在第i天可以是第 i个人可以是第2i个人也可一是同时2个人，一个人不产生快乐值所以当天的快乐值为 a[i] ^ a[2*i] 当天的方案数 2 n − 2 2^{n-2} 2n−2
当 i 2i 2i+1都在n之内时候
当天的快乐值为
（a[i]^ a[2i])+(a[i]^ a[2i+1])+(a[2i]^ a[2i+1])+(a[2i+1]^ a[2i]^a[i]）
当天的方案数为 2 n − 3 2^{n-3} 2n−3

解题代码

#include #define pt2(x,y) cout <<(x)<<"--"<<(y)<<endl;
#define pt1(x) cout <<"#"<<(x)<<"#"<<endl;
#define rep(i,a,n) for(int i = (a); i <= int(n); i++) 
#define per(i,a,n) for(int i = (n); i >= int(a); i--) 
// #define x first;
// #define y second;
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef double DB;
const int N=1e5+10,M=1e6+10,INF=0x3f3f3f3f,MOD=1e9+7;int a[N];
LL p2[N];
int n;
int main()
{p2[0]=1;cin >> n;rep(i,1,n) cin >> a[i];rep(i,1,n) p2[i] = p2[i-1]*2ll%MOD; //预处理2的次方LL ans=0;rep(i,1,n) //计算贡献{if(2*i>n) break;else if(2*i+1>n) ans=(ans+p2[n-2]*(a[i]^a[2*i])%MOD)%MOD;else {//注意异或运算的优先级 记得加上括号ans=ans+p2[n-3]*((a[i]^a[2*i])+(a[i]^a[2*i+1])+(a[2*i]^a[2*i+1])+(a[2*i+1]^a[2*i]^a[i]))%MOD;ans%=MOD;}}cout << ans;}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！