求助可能关于容斥的问题，玄二关

学术版

ghy_jerami__ @ 2024-11-28 16:29:34

给定 n 个二元组，第 i 个表示为 {f_i,s_i}。

对于每个二元组，可以取 f_i-2^{s_i} 或 2^{s_i+1} 作为这个二元组的贡献，最后的总价值为所有贡献的乘积。

求所有取值方案的总价值之和，对 1e9 + 7 取模。

其中 0\le f_i< 1e9+7，0\le s_i \le 10^6。

by ghy_jerami__ @ 2024-11-28 16:32:57

补充一下，要求 O(n \log_{2}n) 以内的做法

by yukimianyan @ 2024-11-28 16:33:30

\prod_{i=1}^n(f_i+2^{s_i})

直接计算即可

by ghy_jerami__ @ 2024-11-28 16:34:44

@yukimianyan

已关，让我想想为什么

by MornStar @ 2024-11-28 16:39:32

考虑DP，设 dp_i 为选前 i 个二元组的总价值之和，则有 dp_i=(f_i-2^{s_i})\times dp_{i-1}+2^{s_i+1}\times dp_{i-1}

合并一下就是 dp_i=(f_i+2^{s_i})\times dp_{i-1}。也就是一个乘积的形式

by ghy_jerami__ @ 2024-11-28 16:39:46

qwq

by ghy_jerami__ @ 2024-11-28 16:41:29

@MornStar

谢谢,已关

by ghy_jerami__ @ 2024-11-28 16:43:55

我太菜了