[luoguP3172] [CQOI2015]选数(递推+容斥原理)
传送门
不会莫比乌斯反演,不会递推。
但是我会看题解。
先将区间[L,H]变成(L1,H],这样方便处理
然后求这个区间内gcd为k的方案数
就是求区间((L1)/k,H/k]中gcd为1的方案数
有个重要的性质:如果有一些不相同的数,最大的为a,最小的为b,任意选取其中的一些数,则他们的gcd<=ab
设f[i]表示gcd为i且所选的数不相同的方案数,但是不好求,只容易求出gcd为i的倍数g[i]的方案数
考虑容斥原理,f[i] = g[i] f[2i] f[3i] ……
计算g[i]的时候要把相同的数的方案数减去,因为我们有个前提,只有数都不相同时gcd的大小才能保证
倒着递推便可以省略g数组
#include <cstdio>#define N 100001#define p 1000000007#define LL long longusing namespace std;LL f[N];int n, k, l, r, flag, len;inline LL ksm(LL x, int y)return ret;}int main()printf("%lld\n", (f[1] + flag + p) % p);return 0;}
上一篇:[luoguP4035] [JSOI2008]球形空间产生器(高斯消元)
下一篇:[luoguP1053] 篝火晚会(贪心 + 乱搞)
DP 容斥原理
spc文件怎么看,spc文件用什么打开?
0文件怎么看,0文件用什么打开?
sparseimage文件怎么看,sparseimage文件用什么打开?
sp文件怎么看,sp文件用什么打开?
dv文件怎么看,dv文件用什么打开?
soundpack文件怎么看,soundpack文件用什么打开?
dus文件怎么看,dus文件用什么打开?
dtw文件怎么看,dtw文件用什么打开?
spdf文件怎么看,spdf文件用什么打开?
0文件怎么看,0文件用什么打开?