网站怎么做付费项目,建设档案员证书查询网站,自己做的网站怎么在局域网中访问,合肥网站快速排名提升890. 能被整除的数 - AcWing题库
在补牛客多校7的I题I-We Love Strings_2023牛客暑期多校训练营7 (nowcoder.com)时发现处理重复集合用了容斥原理来做#xff0c;感觉我对容斥原理不太熟悉#xff0c;因此上网学了学容斥原理。
n个集合的容斥原理的公式为#xff1a; ∪ …890. 能被整除的数 - AcWing题库
在补牛客多校7的I题I-We Love Strings_2023牛客暑期多校训练营7 (nowcoder.com)时发现处理重复集合用了容斥原理来做感觉我对容斥原理不太熟悉因此上网学了学容斥原理。
n个集合的容斥原理的公式为 ∪ i 1 m S i S 1 S 2 S 3 S 4 . . . S m − ( S 1 ∩ S 2 S 1 ∩ S 3 . . . S m − 1 ∩ S m ) S 1 ∩ S 2 ∩ S 3 S 1 ∩ S 2 ∩ S 4 . . . / − . . . \cup_{i1}^mS_i S_1 S_2 S_3 S_4 ...S_m - (S_1 \cap S_2 S_1 \cap S_3 ... S_m-1 \cap S_m) S_1 \cap S_2 \cap S_3 S_1 \cap S_2 \cap S_4 ... /- ... ∪i1mSiS1S2S3S4...Sm−(S1∩S2S1∩S3...Sm−1∩Sm)S1∩S2∩S3S1∩S2∩S4.../−... 实际上就是奇数项是加上这个集合的元素偶数项是减去这个集合的元素。
时间复杂度是 C n 1 C n 2 C n 3 . . . C n n C_n^1 C_n^2 C_n^3 ... C_n^n Cn1Cn2Cn3...Cnn 经过二项式化简为O(2^n - 1)因此是O(2^n)指数级别的时间复杂度。
对于容斥原理的大部分题而言枚举一定会超时的。但是可以用二进制进行优化。对于容斥原理的大部分题而言n比较小可以枚举2^n个在里面套个枚举长度的。
e.g.
for(int k 1; k (1 n); k) { // 枚举所有状态一共2^nfor(int i 0; i n; i) { if(k i 1) { // 第i个选的情况...}}// 选了奇数/偶数 再进行操作
}注意k i 1中的 练习题890. 能被整除的数 - AcWing题库
#include iostream
#include vector
#include string
#include cstring
#include set
#include map
#include queue
#include ctime
#include random
#include sstream
#include numeric
#include stdio.h
#include functional
#include bitset
#include algorithm
using namespace std;// #define Multiple_groups_of_examples
#define IOS std::cout.tie(0);std::cin.tie(0)-sync_with_stdio(false);
#define dbgnb(a) std::cout #a a \n;
#define dbgtt cout !!!test!!! endl;
#define rep(i,x,n) for(int i x; i n; i)#define all(x) (x).begin(),(x).end()
#define pb push_back
#define vf first
#define vs secondtypedef long long LL;
typedef pairint,int PII;const int INF 0x3f3f3f3f;
const int N 2e5 21;void inpfile();
void solve() {int n,m; cinnm;vectorint p(m);for(auto t: p) cint;int ans 0;for(int k 1; k ( 1 m); k) {int cnt 0; // 选了几个int t 1;for(int i 0; i m; i) {if(k i 1) { // 第i个是否可选if(1LL * t * p[i] n) { // 如果相乘大于n为0直接break因为可能有n^mLL也超需要大数运算t -1;break;}cnt;t * p[i];}}if(t -1) continue;// 容斥原理奇数相加偶数相减if(cnt % 2 ! 0) {ans n / t;} else ans - n / t;}coutans;
}
int main()
{#ifdef Multiple_groups_of_examplesint T; cinT;while(T--)#endifsolve();return 0;
}
void inpfile() {#define mytest#ifdef mytestfreopen(ANSWER.txt, w,stdout);#endif
}算法基础二十八数学基础 - 容斥原理 - 知乎 (zhihu.com)
