【BZOJ 3930】[CQOI2015] 选数

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3930
神犇题解:http://www.cnblogs.com/iwtwiioi/p/4986316.html

解题报告

这题,仔细想一想,岂不是跟这个题一样:https://oi.qizy.tech/?p=498
于是答案就是这个东西:$ \sum\limits_{i = 1}^m {\sum\limits_{j = 1}^m { \cdots \sum\limits_{k = 1}^m {[gcd(i,j, \cdots ,k) = K]} } } = \sum\limits_{i = 1}^{\left\lfloor {\frac{m}{K}} \right\rfloor } {\sum\limits_{j = 1}^{\left\lfloor {\frac{m}{K}} \right\rfloor } { \cdots \sum\limits_{k = 1}^{\left\lfloor {\frac{m}{K}} \right\rfloor } {[gcd(i,j, \cdots ,k) = 1]} } } = \sum\limits_{d = 1}^{\left\lfloor {\frac{m}{K}} \right\rfloor } {\mu (d) \cdot {{\left\lfloor {\frac{m}{{Kd}}} \right\rfloor }^n}}$
于是剩下的锅就是预处理莫比乌斯函数的前缀和了!
然而我只会 $ O(n)$ 的做法,于是就跪了

PoPoQQQ大爷给了一种神奇的做法:http://blog.csdn.net/popoqqq/article/details/44917831
大概就是说,莫比乌斯函数的前缀和可以进行如下变换:
$ \sum\limits_{i = 1}^n {\mu (i) = 1 – \sum\limits_{i = 2}^n {(0 – \mu (i)) = } 1 – \sum\limits_{i = 2}^n {(\sum\limits_{j|i} {\mu (j)} – \mu (i))} = 1 – \sum\limits_{i = 2}^n {\sum\limits_{j|i,i \ne j} {\mu (j)} } } = 1 – \sum\limits_{j = 1}^n {\mu (j) \cdot (\left\lfloor {\frac{n}{j}} \right\rfloor – 1)} = 1 – \sum\limits_{j = 1}^{\left\lfloor {\frac{n}{2}} \right\rfloor } {\mu (j) \cdot (\left\lfloor {\frac{n}{j}} \right\rfloor – 1)}$
换一句话说,莫比乌斯函数的前缀和可以做到 $ O(\sqrt n \log n)$
这样的话,感觉复杂度是 $ O(n \log n)$ 的
然而PoPoQQQ大爷说,预处理前 $ S$ 个值的话,复杂度就可以变成:$ O(\frac{n}{S}\sqrt n lo{g_2}\frac{n}{S})$
然而并不知道怎么证明,感觉很有道理的样子!

当然这题还有容斥的做法
首先有结论:$ gcd(i,j) \le (r – l),(i,j \in (l,r))$
证明的话,参见这里:https://blog.sengxian.com/solutions/bzoj-3930
于是考虑 $ f(i)$ 表示gcd为i的方案数,则 $ f(i) = {\left\lfloor {\frac{m}{{Ki}}} \right\rfloor ^n} – \sum\limits_{i|j} {f(j)}$
这样的话, $ f(1)$ 就是答案辣!

—————————— UPD 2017.2.20 ——————————
突然发现,莫比乌斯函数的前缀和不是杜教筛的模板题吗?
当然PoPoQQQ的做法也有可取之处:不用复杂度公式推导

【51NOD 1806】wangyurzee的树

题目传送门:https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1806
数据生成器:http://paste.ubuntu.com/23358513/

这题知道Prufer编码的同学都能一眼秒吧?
就是裸的Prufer加上容斥。
但这题细节比较多,我说说我被坑的两个地方吧:
1)可能有多个限制条件针对一个点,在容斥的时候要排除这种情况
2)容斥的时候,所有点的度都确定了,但度数不等于n-2的情况容斥也要排除掉

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

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

int POW[N],REV[N],lim[M],id[M],n,m,vout,vis[N];
set<pair<int,int> > S;

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;
}

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

inline int C(int x, int y) {
	int ret = (LL)POW[y] * REV[x] % MOD;
	return (LL)ret * REV[y-x] % MOD;
}

void DFS(int t, int tot, int cnt, int sol, int f) {
	if (tot < 0 || (tot > 0 && cnt == n)) return;
	else if (t >= m + 1) {
		if (!cnt) return;
		else {
			sol = (LL)sol * pow(n - cnt,tot) % MOD;
			vout = ((vout + f*sol) % MOD + MOD) % MOD; 
		}
	} else {
		DFS(t+1, tot, cnt, sol, f);
		if (!vis[id[t]]) {
			vis[id[t]] = 1;
			DFS(t+1, tot - lim[t], cnt + 1, (LL)sol * C(lim[t],tot) % MOD, -f);
			vis[id[t]] = 0;
		}
	} 
}

int main(){
	n = read(); m = read();
	for (int i=1;i<=m;i++) {
		id[i] = read(), lim[i] = read() - 1;
		if (S.count(make_pair(id[i],lim[i]))) {
			i--; m--;
		} else {
			S.insert(make_pair(id[i],lim[i]));
		}
	}
	POW[1] = REV[1] = POW[0] = REV[0] = 1;
	for (int i=2;i<=MX;i++) POW[i] = (LL)POW[i-1] * i % MOD;
	REV[MX] = pow(POW[MX], MOD - 2);
	for (int i=MX-1;i;i--) REV[i] = (LL)REV[i+1] * (i + 1) % MOD;
	
	vout = pow(n, n-2);
	DFS(1,n-2,0,1,1);
	printf("%d\n",vout);
	return 0;
}

【BZOJ 4517】[SDOI2016] 排列计数

题目传送门: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; 
}

【BZOJ 4572】[SCOI2016] 围棋

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

这题的轮廓线DP的做法见:http://www.cnblogs.com/clrs97/p/5452790.html
然后,我们来说一说YJQ的神奇容斥:
首先大力感谢YJQ的支持!OI温暖满人间!
具体做法:枚举每一行的情况,搞一搞dp,顺便记录一下匹配次数的奇偶
然后因为是容斥,所以我们只需要管我们规定的匹配位置,其他位置都可以随意
于是可以预处理出转移,然后搞dp

代码方面,活生生把YJQ的5k+的代码压到了2k+
自己都觉得代码不可读 QAQ

#include<bits/stdc++.h>
#define LL long long
#define abs(x) ((x)<0?-(x):(x))
using namespace std;

const int MOD = 1000000007;
const int REV = 333333336;
const int MAXN = 1 << 10;

int f[2][MAXN][2],trans[MAXN][MAXN],MX,n,m,c,q,N;
bool leg[MAXN],nxt[20][20],vis1[20],vis2[20],bit_cnt[MAXN];
char pat[2][10];

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

inline void prework() {
	memset(trans,0,sizeof(trans));
	for (int w=0,sign;w<=MX;w++) {
		leg[w] = sign = 1; bit_cnt[w] = __builtin_popcount(w)&1;
		for (int i=1;i<=N&&sign;i++) if (w&(1<<(i-1))) for (int j=i+1;j<=N&&sign;j++) if (w&(1<<(j-1)) && j-i < c) 
			for (int t=0;t<2&&sign;t++) for (int k=1;k<=c-j+i&&sign;k++) if (pat[t][k] != pat[t][j-i+k]) sign = leg[w] = 0;
	} 
	for (int i=1,sign;i<=N;i++) for (int j=1;j<=N;j++) {
		nxt[i][j] = sign = 1; if (abs(i-j+1) > c) continue;
		if (i < j) {for (int k=1;k<=c-j+i&&sign;k++) if (pat[0][k] != pat[1][j-i+k]) nxt[i][j] = sign = 0;}
		else for (int k=1;k<=c+j-i&&sign;k++) if (pat[1][k] != pat[0][i-j+k]) nxt[i][j] = sign = 0;
	}
	for (int w1=0;w1<=MX;w1++) if (leg[w1]) {
		memset(vis1,0,sizeof(vis1));  
		for (int i=1;i<=N;i++) if (w1&(1<<(i-1))) for (int j=0;j<c;j++) vis1[i+j] = 1;
		for (int w2=0,sign;w2<=MX;w2++) if (sign=1, leg[w2]){ 
			for (int i=1;i<=N;i++) if (w1&(1<<(i-1))) for (int j=1;j<=N;j++) if (w2&(1<<(j-1)) && !nxt[i][j]) sign = 0;
			if (!sign) continue; int tmp = 1; memset(vis2,0,sizeof(vis2));
			for (int i=1;i<=N;i++) if (w2&(1<<(i-1))) for (int j=0;j<c;j++) vis2[i+j] = 1;
			for (int i=1;i<=n;i++) if (!vis2[i]) tmp = tmp*3LL % MOD; else if (!vis1[i]) tmp = (LL)tmp*REV % MOD;
			trans[w1][w2] = tmp;
		}
	}
}

inline void solve() {
	int cur = 0, p = 1, vout = pow(3,n*m); 
	memset(f[p],0,sizeof(f[p])); f[p][0][0] = pow(3,n);
	for (int stp=2;stp<=m;stp++,cur^=1,p^=1) {
		memset(f[cur],0,sizeof(f[cur]));
		for (int w1=0;w1<=MX;w1++) for (int t=0;t<2;t++) if (f[p][w1][t]) 
			for (int w2=0;w2<=MX;w2++) (f[cur][w2][t^bit_cnt[w2]] += (LL)f[p][w1][t] * trans[w1][w2] % MOD) %= MOD;
	}
	for (int w=0;w<=MX;w++) (vout -= f[p][w][0]) %= MOD, (vout += f[p][w][1]) %= MOD;
	printf("%d\n",(vout%MOD+MOD)%MOD);
}	

int main(){
	cin>>m>>n>>c>>q;
	MX = (1 << (n - c + 1)) - 1; N = n - c + 1;
	for (int i=1;i<=q;i++) {
		scanf("%s%s",pat[0]+1,pat[1]+1);
		prework(); solve();
	} 
	return 0;
}

再次感谢YJQ的支持!容斥的做法真的好神!

【BZOJ 1853】[Scoi2010] 幸运数字

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

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

就只有一个小问题:会不会爆long long
一开始我想,哼,怎么可能爆long long? 不是要中途除掉一个gcd吗?(¬︿¬)
于是我就在hzwer的程序上加了一个判断:如果爆了long long输出“fuck!!!”
然后效果大概是这样的:
↓↓↓↓↓↓这个是GIF,要点开才能感受到来自心灵的震撼!↓↓↓↓↓↓
1234567865432
大神我错了!!!/(ㄒ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;
} 

【BZOJ 2393】Cirno的完美算数教室

题目传送门: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;
}