有时候，我们在做背包问题时会遇到如下情况，给你一大堆询问，要你求出满足某种限制，填满背包的方法数。 先来一道例题： 例题1： P1450 [HAOI2008]硬币购物 乍眼一看似乎是一个裸的完全背包，但是注意到询问组数较多，每次跑一遍完全背包绝对会炸掉，考虑预处理出不带限制的方法数，然后用容斥除去不满足限制的方法。 预处理，用题目的四种硬币凑出xxx元的钱共有f(x)f(x)f(x)种方法...

传送门 给你一个序列{ai}\{a_i\}{ai​}，和四个数l1,r1,l2,r2l1,r1,l2,r2l1,r1,l2,r2，求区间[l1,r1]，[l2,r2][l1,r1]，[l2,r2][l1,r1]，[l2,r2]中相同的数有多少对。 当然你不能维护四个指针，考虑容斥原理，我们不妨设f(x,y)f(x,y)f(x,y)为下标为[1,x][1,x][1,x]和下标为[1,y][1,...