Tag: 容斥原理

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4517

这个题目，唯一的问题在于求一个网上被称为错排的玩意
网上好像都是从实际含义来推的错排的公式
我来撸一发容斥的推法：
\(
\begin{array}{l}
f(n) = n! – C_n^1 \cdot (n – 1)! + C_n^2 \cdot (n – 2)! – \cdots – C_n^n \cdot 1!\\
f(n) = \frac{{n!}}{{2!}} – \cdots – \frac{{n!}}{{n!}}\\
f(n) = n! \cdot \sum\limits_{i = 2}^n {\frac{{{{( – 1)}^i}}}{{i!}}} \\
f(n) = f(n – 1) \cdot \frac{{n!}}{{(n – 1)!}} + {( – 1)^n}
\end{array}
\)

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 1000000+9;
const int MX = 1000000;
const int MOD = 1000000007;

int p[N],d[N],REV[N];

inline int pow(int w, int t){
	int ret = 1; while (t) {
		if (t & 1) ret = (LL)ret * w % MOD;
		w = (LL)w * w % MOD, t >>= 1;
	} return ret;
}

inline LL C(int a, int b) {
	return (((LL)p[a]*REV[b])%MOD)*REV[a-b] % MOD;
}

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

int main(){
	p[1] = p[0] = REV[0] = 1; d[1] = 0; d[0] = 1; 
	for (int i=2;i<=MX;i++) p[i] = (LL)p[i-1]*i % MOD;
	REV[MX] = pow(p[MX],MOD-2);
	for (int i=MX-1;i;i--) REV[i] = (LL)REV[i+1]*(i+1) % MOD;
	for (int i=2;i<=MX;i++) d[i] = ((d[i-1] + (i&1?-REV[i]:REV[i])) % MOD + MOD) % MOD;
	for (int i=0;i<=MX;i++) d[i] = (LL)d[i]*p[i] % MOD;
	for (int T=read(),n,m;T;T--) {
		n = read(); m = read(); 
		if (m > n) puts("0");
		else cout<<C(n,m)*d[n-m]%MOD<<endl;
	} return 0; 
}

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1853

这个题，乍一看，跟2393一样。
再一看，确实是一样的QAQ

就只有一个小问题：会不会爆long long
一开始我想，哼，怎么可能爆long long？ 不是要中途除掉一个gcd吗？(￢︿￢)
于是我就在hzwer的程序上加了一个判断：如果爆了long long输出“fuck！！！”
然后效果大概是这样的：
↓↓↓↓↓↓这个是GIF，要点开才能感受到来自心灵的震撼！↓↓↓↓↓↓

大神我错了！！！/(ㄒoㄒ)/~~

#include<iostream>
#include<cstdio>
#include<algorithm>
#define LL long long
using namespace std;

const int MAXN = 20000;

int cnt,tot;
LL arr[MAXN],buf[MAXN],l,r,vout;

void DFS(LL w){
	if (w > r) return;
	buf[++cnt] = w;
	DFS(w*10+6);
	DFS(w*10+8);
}

inline void prework(){
	DFS(6); DFS(8);
	sort(buf+1,buf+cnt);
	for (int i=1,tag=0;i<=cnt;i++,tag=0) {
		for (int j=i-1;j;j--) if (buf[i]%buf[j]==0) {tag=1;break;}
		if (!tag) arr[++tot] = buf[i];
	} 
	for (int i=1;i*2<=tot;i++) swap(arr[i],arr[tot-i+1]);
}

LL GCD(LL a, LL b){return b?GCD(b,a%b):a;}

void solve(int step, int sz, LL w){
	if (step == tot+1) {
		if (sz & 1) vout += r/w - (l-1)/w;
		else if (sz) vout -= r/w - (l-1)/w;
	} else {
		solve(step+1,sz,w);
		double tmp = (double)w*arr[step]/GCD(w,arr[step]);
		if (tmp <= r) solve(step+1,sz+1,w/GCD(w,arr[step])*arr[step]); 
	}
}

int main(){
	scanf("%lld%lld",&l,&r);
	prework();
	solve(1,0,1);
	printf("%lld\n",vout);
	return 0;
} 

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2393
数据生成器：http://paste.ubuntu.com/22548407/

额，容斥第一题，竟然成了乱搞…….
这题的时间复杂度是玄学……
就是搞出互质的baka数，然后容斥

#include<iostream>
#include<cstdio>
#include<algorithm>
#define LL long long 
using namespace std;

const int MAXN = 2000;

int l,r,arr[MAXN],tmp[MAXN],vout,cnt,tot;

void DFS(LL w){
	if (w > r) return;
	tmp[++cnt] = w;
	DFS(w*10+2);
	DFS(w*10+9);
}

inline void prework(){
	DFS(2); DFS(9);
	sort(tmp+1,tmp+cnt); 
	for (int i=1,tag=0;i<=cnt;i++,tag=0) {
		for (int j=i-1;j;j--) if (tmp[i] % tmp[j] == 0) {tag = 1; break;}
		if (!tag) arr[++tot] = tmp[i];
	}
	for (int i=1;i*2<=tot;i++) swap(arr[i],arr[tot-i+1]);
}

int GCD(int a, int b){return b?GCD(b,a%b):a;}

void solve(int step, int sz, int w){
	if (step == tot+1) {
		if (sz & 1) vout += r/w - (l-1)/w;
		else if (sz) vout -= r/w - (l-1)/w;
	} else {
		solve(step+1,sz,w);
		LL buf = (LL)w/GCD(w,arr[step])*arr[step];
		if (buf <= r) solve(step+1,sz+1,buf);
	}
}

int main(){
	scanf("%d%d",&l,&r);
	prework();
	solve(1,0,1);
	printf("%d\n",vout);
	return 0;
}