夢に僕らで帆を張って
来るべき日のために夜を超え

标签 容斥 下的文章

November 6, 2019

洛谷P4318 完全平方数

题意求第$k$个不含完全平方数因子的数数据范围:$k \le 10^9$题解二分这个数,然后验证其排名是否$\ge k$对于计算$n$以内的无平方因子数的个数,可以用到容斥原理$$ans=含0个质数的平方因子的个数-含1个质数的平方因子的个数+含2个质数的平方因子的个数 \dots$$注意到每个数的容斥系数恰好为莫比乌斯函数$\mu(i)$,上式即为$$\sum_{i=1}^{\lfloor...
November 4, 2019

洛谷P1450/HAOI2008 硬币购物

题意硬币购物一共有$4$种硬币。面值分别为$c_1,c_2,c_3,c_4$某人去商店买东西,去了$t$次。每次带$d_i$枚$c_i$硬币,买$s$的价值的东西,请问每次有多少种付款方法数据范围:$d_i,s \le 100000$题解显然不能直接多重背包,会TLE若不考虑限制条件,先当作完全背包处理,再在每次询问的时候将超出部分的情况减去需要减去的部分也是一个完全背包,容量为$s-c_i...
October 21, 2019

CF1228E Another Filling the Grid

题意一个$n \times n$的矩形,每个格子里可以填$[1,k]$内的整数,求保证每行每列的最小值为$1$的方案数数据范围:$1 \le n \le 250,1 \le k \le 10^9$题解直接计算难以解决,考虑容斥原理枚举有$i$行$j$列的最小值$> 1$,选择方案有$$\sum_{i=0}^n \sum_{j=0}^n (-1)^{i+j} C_n^i C_n^j$$乘...
September 26, 2019

洛谷P2260/清华集训2012 模积和

题意求$$\sum_{i=1}^n\sum_{j=1}^m (n\%i) \cdot (m\%j),i \neq j$$$\bmod \ 19940417$的值数据范围:$n,m \le 10^9$题解算法:数论分块先不考虑条件$i \neq j$,化简原式$$ \begin{aligned} \sum_{i=1}^n\sum_{j=1}^m (n\%i) \cdot (m\%j) &...