【BZOJ 4599】[JLOI2016] 成绩比较

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4559
神犇题解:http://blog.lightning34.cn/?p=286

解题报告

仍然是广义容斥原理
可以推出$\alpha(x)={{n-1}\choose{x}} \prod\limits_{i=1}^{m}{{{n-1-x}\choose{R_i-1}}\sum\limits_{j=1}^{U_i}{(U_i-j)^{R_i-1}j^{n-R_i}}}$
我们发现唯一的瓶颈就是求$f(i)=\sum\limits_{j=1}^{U_i}{(U_i-j)^{R_i-1}j^{n-R_i}}$
但我们稍加观察不难发现$f(i)$是一个$n$次多项式,于是我们可以用拉格朗日插值来求解
于是总的时间复杂度:$O(mn^2)$

Code

这份代码是$O(mn^2 \log 10^9+7)$的
实现得精细一点就可以把$\log$去掉

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

const int N = 200;
const int MOD = 1000000007;

int n,m,K,r[N],u[N],f[N],g[N],h[N],alpha[N],C[N][N]; 

inline int read() {
	char c=getchar(); int f=1,ret=0;
	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) {
	int ret = 1;
	for (;t;t>>=1,w=(LL)w*w%MOD) {
		if (t & 1) {
			ret = (LL)ret * w % MOD;
		} 
	}
	return ret;
}

inline int LagrangePolynomial(int x, int len, int *ff, int *xx) {
	int ret = 0;
	for (int i=1;i<=len;i++) {
		int tmp = ff[i];
		for (int j=1;j<=len;j++) {
			if (i == j) continue;
			tmp = (LL)tmp * (x - xx[j]) % MOD;
			tmp = (LL)tmp * Pow(xx[i] - xx[j], MOD-2) % MOD;
		}
		ret = (ret + tmp) % MOD;
	}
	return (ret + MOD) % MOD;
} 

int main() {
	n = read(); m = read(); K = read();
	for (int i=1;i<=m;i++) {
		u[i] = read();
	}
	for (int i=1;i<=m;i++) {
		r[i] = read();
	}
	//预处理组合数 
	C[0][0] = 1;
	for (int i=1;i<=n;i++) {
		C[i][0] = 1;
		for (int j=1;j<=i;j++) {
			C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;
		}
	}
	//拉格朗日插值
	for (int w=1;w<=m;w++) {
		for (int i=1;i<=n+1;i++) {
			f[i] = 0; h[i] = i;
			for (int j=1;j<=i;j++) {
				f[i] = (f[i] + (LL)Pow(i-j, r[w]-1) * Pow(j, n-r[w])) % MOD;
			}
		}  
		g[w] = LagrangePolynomial(u[w], n+1, f, h);
	}
	//广义容斥原理 
	int ans = 0;
	for (int i=K,t=1;i<=n;i++,t*=-1) {
		alpha[i] = C[n-1][i];
		for (int j=1;j<=m;j++) {
			alpha[i] = (LL)alpha[i] * C[n-1-i][r[j]-1] % MOD * g[j] % MOD;
		}
		ans = (ans + t * (LL)C[i][K] * alpha[i]) % MOD;
	}
	printf("%d\n",(ans+MOD)%MOD);
	return 0;
}

【日常小测】最长路径

相关链接

题目传送门:http://oi.cyo.ng/wp-content/uploads/2017/06/claris_contest_4_day2-statements.pdf
官方题解:http://oi.cyo.ng/wp-content/uploads/2017/06/claris_contest_4_day2-solutions.pdf

解题报告

首先我们要熟悉竞赛图的两个结论:

  1. 任意一个竞赛图一定存在哈密尔顿路径
  2. 一个竞赛图存在哈密尔顿回路当且仅当这个竞赛图强连通

现在考虑把强连通分量缩成一个点,并把新点按照哈密尔顿路径排列
那么$1$号点可以到达的点数就是$1$号点所在的$SCC$的点数加上$1$号点可以到达的其他$SCC$点数和

设$f_i$为$i$个点带标号竞赛图的个数
设$g_i$为$i$个点带标号强连通竞赛图的个数
有$f_i = 2^{\frac{n(n-1)}{2}}$
又有$g_i = f_i – \sum\limits_{j = 1}^{i – 1}{{{i}\choose{j}} g_j f_{i – j}}$

于是我们枚举$1$号点所在$SCC$的点数$i$和$1$号点可到达的其他$SCC$的点数和$j$
$ans_{x} = \sum\limits_{i = 1}^{x}{{{n – 1}\choose{i – 1}} g_i {{n – i}\choose{x – i}} f_{x – i} f_{n – x}}$

Code

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

const int N = 2009;

int n, MOD, f[N], g[N], pw[N * N], C[N][N];

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

int main() {
	freopen("path.in", "r", stdin);
	freopen("path.out", "w", stdout);
	n = read(); MOD = read();
	pw[0] = 1;
	for (int i = 1; i < n * n; i++) {
		pw[i] = (pw[i - 1] << 1) % MOD;
	}
	C[0][0] = 1;
	for (int i = 1; i <= n; ++i) {
		C[i][0] = 1;
		for (int j = 1; j <= n; j++) {
			C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
		}
	}
	f[0] = g[0] = 1;
	for (int i = 1; i <= n; i++) {
		f[i] = g[i] = pw[i * (i - 1) >> 1];
		for (int j = 1; j < i; j++) {
			g[i] = (g[i] - (LL)C[i][j] * g[j] % MOD * f[i - j]) % MOD;
		}
	}
	for (int x = 1; x <= n; x++) {
		int ans = 0;
		for (int i = 1; i <= x; i++) {
			ans = (ans + (LL)C[n - 1][i - 1] * g[i] % MOD * C[n - i][x - i] % MOD * f[x - i] % MOD * f[n - x]) % MOD;
		}
		printf("%d\n", ans > 0? ans: ans + MOD);
	}
	return 0;
}

【TopCoder SRM714】ParenthesisRemoval

相关链接

题目传送门:https://community.topcoder.com/stat?c=problem_statement&pm=14595&rd=16883

解题报告

不难发现,这就是统计括号匹配的方案数
不会的同学可以先去切BZOJ 3622

Code

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

const int N = 3000;
const int MOD = 1000000007;

int n,ans;
char s[N]; 

class ParenthesisRemoval {
    public:
    	int countWays(string ss) {
			n = ss.size();
    		for (int i=0;i<ss.size();i++) {
				s[i] = ss[i];
			}
			ans = 1;
			for (int i=0,pfx=0;i<n;i++) {
				if (s[i] == '(') {
					++pfx;
				} else {
					ans = (LL)ans * (pfx--) % MOD;
				}
			}
    	    return ans;
   		}
   	private:
};

【BZOJ 3622】已经没有什么好害怕的了

相关链接

解题报告:http://www.lydsy.com/JudgeOnline/problem.php?id=3622

解题报告

恰好有$k$个条件满足,这不就是广义容斥原理吗?
不知道广义容斥原理的同学可以去找$sengxian$要他的$PDF$看哦!

知道广义容斥原理的同学,这题难点就是求$\alpha(i)$
设$f_{i,j}$表示考虑了前$i$个糖果,至少有$j$个糖果符合条件的方案数
那么$\alpha(i)=f_{n,i} \cdot (n-i)!$

于是先$O(n^2)$DP出$\alpha(i)$
然后根据广义容斥原理$O(n)$推出$\beta(k)$就可以了
总时间复杂度:$O(n^2)$

Code

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

const int N = 2009;
const int MOD = 1000000009;

int n,K,a[N],b[N],sum[N],fac[N],alpha[N],f[N][N],C[N][N]; 

inline int read() {
	char c=getchar(); int f=1,ret=0;
	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() {
	n = read(); K = read();
	if ((n + K) & 1) {
		puts("0");
		exit(0);
	} 
	K = n + K >> 1; 
	for (int i=1;i<=n;i++) {
		a[i] = read();
	}
	sort(a+1, a+1+n);
	for (int i=1;i<=n;i++) {
		b[i] = read();
	} 
	sort(b+1, b+1+n);
	for (int i=1,j=0;i<=n;i++) {
		for (;j < n && b[j+1] < a[i];++j);
		sum[i] = j;
	}
	C[0][0] = 1;
	for (int i=1;i<=n;i++) {
		C[i][0] = 1;
		for (int j=1;j<=i;j++) {
			C[i][j] = (C[i-1][j] + C[i-1][j-1]) % MOD;
		}
	}
	fac[0] = 1;
	for (int i=1;i<=n;i++) {
		fac[i] = fac[i-1] * (LL)i % MOD; 
	}
	f[0][0] = 1;
	for (int i=1;i<=n;i++) {
		for (int j=0;j<=i;j++) {
			f[i][j] = (f[i-1][j] + (j?f[i-1][j-1] * max(0ll, (sum[i] - j + 1ll)):0ll)) % MOD;
		}
	}
	for (int i=0;i<=n;i++) {
		alpha[i] = (LL)f[n][i] * fac[n - i] % MOD;
	}
	int ans = 0;
	for (int i=K,t=1;i<=n;i++,t*=-1) {
		ans = (ans + (LL)alpha[i] * C[i][K] * t) % MOD;
	}
	printf("%d\n",(ans+MOD)%MOD);
	return 0;
}

【BZOJ 4714】旋转排列

相关链接

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

题目大意

定义集合$A=\{1,2,\cdots,n\}$
对于$A$的任意一个排列$P$,其对于自然数$k$合法当且仅当:

  1. 对于$\forall i \in [1,n]$ 都有$a_i \ne i$
  2. 存在一个长度为$k$的序列$B$,使得$P_{B_i}=B_{i+1}$且$P_{B_k} = B_1$

定义$k=x$时$A$的合法排列数为$ans_x$,询问$\sum\limits_{i=1}^{n}{ans_i}$
由于答案可能很大,输出答案对$10^9 + 7$取模得到的结果

解题报告

我们发现,要求合法的第二个限制实际就是要求置换存在一个等于$k$的循环
于是我们对于每一个$k$,我们容斥一发,根据调和级数,这个复杂度是:$O(n \log n)$的

至于容斥的具体细节,假设我们当前钦定有$t$个长度为$k$的循环
设把$tk$个数分成$k$个循环的方案数为$g_{k,t}$
设$i$个数的错排的方案数为$d_i$
设$i$个数的环排列的方案数为$q_i$
那么这一部分的总方案数为:$g_{k,t} \cdot d_{n-kt} \cdot {{n} \choose {kt}}$

至于$q_i$怎么算?$q_i = (i-1)!$
至于$d_i$怎么算?我们可以$O(n)$预处理
至于$g_{k,t}$怎么算?我们考虑$1$所在的那个循环有哪些数,可以得到:$g_{k,t}=g_{k,t-1} \cdot d_k \cdot {{tk-1} \choose {k-1}}$

Code

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

const int N = 500009;
const int MOD = 1000000007;

int n,ans,fac[N],rev[N],q[N];

inline int C(int a, int b) {
	if (a > b || a < 0) return 0;
	else return ((LL)fac[b] * rev[a] % MOD) * rev[b-a] % MOD;
}

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

int main() {
	fac[0] = fac[1] = q[2] = q[0] = 1; 
	for (int i=2;i<N;i++) fac[i] = (LL)fac[i-1] * i % MOD;
	rev[N-1] = Pow(fac[N-1], MOD - 2);
	for (int i=N-2;~i;i--) rev[i] = rev[i+1] * (i + 1ll) % MOD; 
	for (int i=3;i<N;i++) q[i] = (i - 1ll) * (q[i-1] + q[i-2]) % MOD;
	cin>>n;
	for (int k=2,g;g=1,k<=n;k++) {
		for (int t=1;t*k<=n;t++) {
			g = ((LL)g * C(k-1, t*k-1) % MOD) * fac[k-1] % MOD;
			ans = (ans + ((t&1)?1:-1) * ((LL)g * C(k*t, n) % MOD) * q[n - k*t]) % MOD;
		} 
	}
	printf("%d\n",(ans+MOD)%MOD);
	return 0;
}

【BZOJ 4710】[JSOI2011] 分特产

相关链接

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

解题报告

先不考虑每个人至少一个的限制条件
那么我们可以将每一类物品分别考虑,用一个插板法就可以解决问题

现在考虑每一个人至少一个的限制
我们可以大力容斥一波!

于是总的时间复杂度就是:$O(nm)$

Code

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

const int N = 2009;
const int MOD = 1000000007;

int n,m,ans,a[N],C[N][N];

inline int read() {
	char c=getchar(); int f=1,ret=0;
	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 cal(int x) {
	int ret = C[x][n];
	for (int i=1;i<=m;i++) {
		ret = (LL)ret * C[n-x-1][a[i]+n-x-1] % MOD;
	}
	return ret;
}

int main() {
	n = read(); m = read(); 
	C[0][0] = 1;
	for (int i=1;i<N;i++) {
		C[0][i] = 1;
		for (int j=1;j<N;j++) {
			C[j][i] = (C[j-1][i-1] + C[j][i-1]) % MOD;
		}
	}
	for (int i=1;i<=m;i++) a[i] = read();
	for (int i=0;i<n;i++) {
		if (i&1) ans = (ans - cal(i)) % MOD;
		else ans = (ans + cal(i)) % MOD;
	} 
	printf("%d\n",(ans+MOD)%MOD);
	return 0;
}

【BZOJ 4735】你的生命已如风中残烛

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4735
神犇题解:http://blog.csdn.net/neither_nor/article/details/64919143

吐槽

我只会$O(mn2^n)$的暴力$DP$
然而正解长成这样,为什么$n$给这么小?
给人一种这题有妙妙的做法的错觉……

解题报告

我们把正常的牌看成$-1$的话,那么实际上就是要让每一个地方的前缀和$\ge 1$

现在考虑在末尾加上一个$-1$,那么是不是就是处末尾以外的地方$\ge 1$,而末尾的前缀和为$0$?
现在考虑把这$m+1$个元素拿出来做一个环排列
仔细观察可以发现:一种环排列能且仅能对应一种合法摆放
于是我们求出环排列的个数就可以了,最后再去一下多加的那个$-1$的影响
最终答案:$\frac{m!}{m-n+1}$

Code

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

const int MOD = 998244353;

inline int read() {
	char c=getchar(); int f=1,ret=0;
	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() {
	int n = read(), m = 0, ans = 1;
	for (int i=1;i<=n;i++) m += read();
	for (int i=2;i<=m;i++) ans = ((LL)ans * ((i!=m-n+1)?i :1)) % MOD;
	cout<<ans;
	return 0;
}

【HDU 4349】Xiao Ming’s Hope

相关链接

题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=4349
神犇题解:http://blog.csdn.net/u013486414/article/details/48130553

题目大意

求${n \choose i},i \in [1,n]$中有多少个奇数
其中$n \le 10^{18}$

解题报告

原题相当于求${n \choose i} \% 2$有多少个为$1$
考虑使用$Lucas$定理,将模数设为$2$
此时相当于把$n,i$都转成了二进制下,然后单独考虑每一位
因为${1 \choose 1} = {1 \choose 0} = {0 \choose 0} = 1,{0 \choose 1} = 0$
所以当$n$的那个二进制位为$1$的时候,$i$那一位可以为$0/1$,但当$n$那一位为$0$时,$i$只能为$0$
所以最终方案数为$2^{\sum\limits_{i=0}^{63}{(n>>i) \& 1}}$

Code

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

int main() {
	for (LL n,ans;~scanf("%I64d",&n);){
		ans = pow(2, __builtin_popcountll(n)) + 0.5;
		cout<<ans<<endl;
	}
	return 0;
}

【BZOJ 3925】[ZJOI2015] 地震后的幻想乡

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3925
神犇题解Ⅰ:http://blog.csdn.net/skywalkert/article/details/47792065
神犇题解Ⅱ:http://www.cnblogs.com/yousiki/p/6437155.html

解题报告

题目上说:

对于$n$个$[0,1]$之间的随机变量$x_1,x_2,\cdots ,x_n$,第$k$小的那个的期望值是$\frac{k}{n+1}$

即加入$k$条边后恰好有生成树的情况的最大边的期望权值为$\frac{k}{n+1}$
设$g_k$为加入$k$条边后恰好使所有点连通的方案数
于是原题的答案为$\frac{1}{m+1}\sum\limits_{i=1}^{m}{\frac{i \cdot g_i}{m \choose i}}$

设$f_k$为加入$k$条边后原图不连通的方案数
我们可以交换一下求和顺序可使答案变为:$\frac{1}{m+1}\sum\limits_{i=0}^{m}{\frac{f_i}{m \choose i}}$
于是问题变为求$f_k$与$g_k$

我们首先可以发现,$f_k$加$g_k$一定等于所有的方案
那么设点集$S$的诱导子图中的边数为$cnt_{S}$,仅对于点集$S$有效的$f_k,g_k$为$f_{S,k},g_{S,k}$
则有:$f_{S,k}+g_{S,k}={cnt_S \choose k}$,于是只需要求出$g_{S,k},f_{S,k}$中的任意一个

类比带标号的连通图计数,我们可以列出递推式:$f_{S,i+j} = \sum\limits_{T \subset S}{g_{T,i} {cnt_{S-T} \choose j}}$
又$g_{S,k}={cnt_S \choose k} – f_{S,k}$,所以这个递推式可以直接递推
于是这题就做完啦!时间复杂度:$O(m 4^n)$
又因为上述$T \subset S$所以我们直接枚举子集,复杂度优化到$O(m 3^n)$

【BZOJ 3028】食物

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3028
神犇题解:http://blog.csdn.net/regina8023/article/details/44995939

解题报告

这题看上去一眼不可做啊!第一反应:还要写高精?
但想一想似乎物品非常妙妙:

我们强行将其分为四组:{汉堡,可乐} {蜜桃多,土豆片炒肉} {包子,鸡块} {鸡腿,面包}
我们发现每一组都能凑出每一个自然数,且方案唯一
于是问题变为将$n$个球分为$4$组,每组可以为空的方案数

这是插板法的经典问题,于是搞一个组合数就可以了
什么组合数太大?
我们注意到答案实际是$\frac{n^{\bar 3}}{6}$,所以我们取个模就可以了

当然你也可以强行搞生成函数然后泰勒展开得到一样的结论
但我不会泰勒展开 QwQ

Code

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

const int MOD = 10007;
const int REV = 1668;

int main() {
	int n=0; char pat[600]; cin>>pat+1;
	for (int i=1;i<=strlen(pat+1);i++)
		n = (n * 10 + pat[i] - '0') % MOD;
	cout<<n*(n+1ll)*(n+2)*REV%MOD;
	return 0;
}

【日常小测】计数

相关链接

题目传送门:http://oi.cyo.ng/wp-content/uploads/2017/03/20170301145817_34363.png
官方题解:http://oi.cyo.ng/wp-content/uploads/2017/03/20170301150237_94661.png

一句话题意

给$n_1$个$A$,$n_2$个$B$,$n_3$个$C$,$n_4$个$D$
问有多少种排列方式,使得相邻两项全部不同
$n_1,n_2,n_3,n_4 \le 10^3$

吐槽

因为做过魔法的碰撞
所以这题卡在$O(n^3)$的复杂度上卡了三个半小时 QwQ
最后暴力还$MLE$了 QwQ

解题报告

假设我们知道了将$A,B$分成$i$段、每一段中相邻两项不同的方案数为$f_i$
知道了将$C,D$分成$i$段、每一段中相邻两项不同的方案数为$g_i$
那么答案显然为$\sum\limits_{i=1}^{n_1+n_2}{f_i \cdot (g_{i-1}+2g_i+g_{i+1})}$
至于中间那一项为什么要乘以2? 因为多出来那一段我们既可以放段首,也可以放段尾

现在唯一的问题就是如何求出$f_i,g_i$了
考虑仅由$A,B$组成的字符串,一定为以下四种情况之一

[1]ABAB…A
[2]BABA…B
[3]ABAB…B
[4]BABA…A

假如我们枚举第一种情况出现了$i$次
那么第二种情况的出现次数$j=i-(a-b)$
那剩下的$k$次,就是第三种和第四种了,不难发现我们乘上$2^k$之后他们就可以视为等价
于是我们先在第一种情况的位置上插入$A$,第二种情况插入$B$,第三、四种情况插入$AB(BA)$
之后我们相当于把剩下的$A,B$两两配对,然后分成$x$组,允许空集
那么这就是插板法的板题了

于是我们就用上述算法处理出$f_i,g_i$即可
时间复杂度:$O(n^2)$

Code

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

const int MOD = 1000000007;
const int N = 2009;

int vout,f[N],g[N],C[N][N],PW2[N];

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 solve(int a, int b, int c) {
	if (a < b) swap(a, b);
	if (!a && b) return b == c;
	int ret = 0;
	for (int i=a-b,j,k;i<=c;++i) {
		j = i - a + b; k = c - i - j;
		if (j >= 0 && k >= 0 && a >= i + k ) {
			(ret += (((LL)C[i] * C[j][c-i] % MOD) * PW2[k] % MOD) * C[c-1][a-i-k+c-1] % MOD) %= MOD;
		}
	}
	return ret;
}

int main() {
	PW2[0] = 1; for (int i=1;i<N;i++) PW2[i] = (PW2[i-1] << 1) % MOD;
	C[0][0] = 1; for (int i=1;i<N;i++) {
		C[0][i] = 1; for (int j=1;j<=i;j++) {
			C[j][i] = (C[j-1][i-1] + C[j][i-1]) % MOD;
		}
	} 
	int a=read(),b=read(),c=read(),d=read();
	if (a + b == 0) f[1] = 1;
	else for (int i=1;i<=a+b;i++) f[i] = solve(a, b, i);
	if (c + d == 0) g[1] = 1;
	else for (int i=1;i<=c+d;i++) g[i] = solve(c, d, i);
	for (int i=1;i<=a+b;i++) (vout += f[i] * (g[i-1] + 2ll * g[i] + g[i+1]) % MOD) %= MOD;
	printf("%d\n",vout);
	return 0;
}

【BZOJ 4455】[ZJOI2016] 小星星

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4455
神犇题解:http://www.cnblogs.com/DaD3zZ-Beyonder/p/5793086.html

解题报告

这题这个阶乘级别的状压DP大家都会吧?

$f(i,j,S)$ 表示树上第$i$个点,对应图中第$j$个点,子树中的对应状态状压后为$S$的方案数

然后我发现了两件事:
1. 这样会T
2. 我不会更优的算法了

正解的话,用了一个非常神奇的DP
考虑枚举有图中有哪些点被映射,然后 $O(n^3)$ 就可以求出满足边的限制的方案数(但点不一定是一一对应的)
然后我们加上点数刚好的情况,减去点数差一的情况,加上相差为2的情况…
于是我们就可以在 $O(2^n \cdot n^3)$ 的时间复杂度内解决这个问题啦!

【Codeforces 653G】Move by Prime

相关链接

题目传送门:http://codeforces.com/problemset/problem/653/G
官方题解:http://codeforces.com/blog/entry/43886
数学推导参考:http://codeforces.com/blog/entry/43886?#comment-285657
中文题面:http://www.cnblogs.com/AOQNRMGYXLMV/p/5441441.html
生成函数的做法:http://www.cnblogs.com/AOQNRMGYXLMV/p/5441441.html

解题报告

不难发现质因数之间相互独立
于是我们就可以将每一个质因数单独考虑
这样问题转化为:

给定一个序列 {$ { {a_i}}$} ,每一次操作可以选一个数加一或者减一
问:将序列中所有数变为相同至少需要多少次操作

这个经典的问题,我们都知道全部变到中位数是较优的策略
但如何考虑每一个子序列?似乎没有比较优雅的方法…

于是我们换一个角度考虑:

设序列排序后为 {\({ {b_i}}\)}, 中位数为 $ {b_{mid}}$
那么这个序列的花费为 $ \sum\limits_{i = 1}^{mid – 1} {({b_{mid}} – {b_i})} + \sum\limits_{i = mid + 1}^n {({b_i} – {b_{mid}})}$

打开∑之后发现 $ {b_{mid}}$ 全部抵消掉了!
于是我们统计一个数有有多少次是加上或是减去就好啦!

考虑当前处理 $ {b_k}$ 这样的话,枚举有i个数比他小
那么有 $ i+1 \sim n-k$ 个数比他大的情况全部是减去
有 $ 0 \sim i-1$ 个数比他大的情况全部是加上
写出来就是 $ \sum\limits_{i = 0}^{{\rm{k – 1}}} {(\sum\limits_{j = {\rm{0}}}^{i – 1} {C_{n – k}^j} – \sum\limits_{j = i + 1}^{n – k} {C_{n – k}^j} )} \cdot {b_k}$

但这样计算的话,复杂度不对,于是再化简一下:

考虑选法1:左边选 $ l$ 个,右边选 $ r$ 个,$ r-l=x$
这样的话,我们总共选了 $ r+l$ 个数
考虑将右边选的数反选(方案间仍然一一对应),此时我们选择了 $ n-k-x$ 个数

再考虑选法二:我们任选 $ n-k-x$ 个数
因为 $ r-l=x$, 所以一定可以构造出唯一一组 $ (l,r)$ 使得 $ l+r=n-k-x$

于是我们就证明了上述两种选法存在一种一一对应的映射
换一句话来说,我们可以直接统计第二种选法的方案数 $ C_{n – 1}^{n – k – x}$ 即可

这样的话,答案就成了 $ (\sum\limits_{i = – 1}^{ – (k – 1)} {C_{n – 1}^{n – k – i} – \sum\limits_{i = 1}^{n – k} {C_{n – 1}^{n – k – i}} ) \cdot {b_k} = } (\sum\limits_{i = n – k + 1}^{n – 1} {C_{n – 1}^i – \sum\limits_{i = 0}^{n – k – 1} {C_{n – 1}^i} ) \cdot {b_k}}$
这样的话,我们处理一下组合数的前缀和就可以 $ O(n)$ 处理完每一个质因数了
又因为 $ {b_k}$ 的值域很小,于是再预处理一下组合数的前缀和的前缀和
就可以得到 $ O(nlog(n))$ 的复杂度辣!

当然上面数学推导那一块还可以用生成函数来推导
然而我不会 QwQ

Code

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

const int N = 300000+9;
const int L = 22;
const int MOD = 1000000007;

int n,tot,vout,pri[N],vis[N],sur[N],cnt[N][L];
int POW[N],REV[N],sum[N],pre1[N],pre2[N];

inline int read() {
	char c=getchar(); int f=1,ret=0;
	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 C(int a, int b) {
	if (a > b || a < 0 || b < 0) return 0;
	else return ((LL)POW[b] * REV[a] % MOD) * REV[b-a] % MOD;
}

inline int pre_sum(int l, int r) {
	if (l > r) return 0;
	return (sum[r] - (l?sum[l-1]:0)) % MOD;
}

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 void prework() {
	n = read(); sur[1] = 1;
	for (int i=2;i<N;i++) {
		if (!vis[i]) pri[++tot] = i, sur[i] = tot;
		for (int j=1;j<=tot&&pri[j]*i<N;j++) {
			vis[i*pri[j]] = 1;
			sur[i*pri[j]] = j;
			if (i % pri[j] == 0) break;
		}
	}
	for (int i=1;i<=tot;i++)
		cnt[i][0] = n;
	
	POW[0] = REV[0] = 1;
	for (int i=1;i<N;i++)
		POW[i] = (LL)POW[i-1] * i % MOD;
	REV[N-1] = Pow(POW[N-1], MOD-2);
	for (int i=N-2;i;i--)
		REV[i] = (LL)REV[i+1] * (i+1) % MOD;
	sum[0] = 1;
	for (int i=1;i<N;i++) 
		sum[i] = (sum[i-1] + C(i, n-1)) % MOD;
	for (int i=1;i<=n;i++)
		pre1[i] = (pre_sum(n-i+1, n-1) - pre_sum(0, n-i-1)) % MOD;
	for (int i=1;i<=n;i++)
		pre2[i] = (pre2[i-1] + pre1[i]) % MOD;
}

int main() {
	prework();
	for (int i=1,w;i<=n;i++) {
		w = read();
		for (int j=sur[w],tmp;w>1;j=sur[w]) {
			for (tmp=0;w%pri[j]==0;tmp++,w/=pri[j]);
			cnt[j][tmp]++;
			cnt[j][0]--;
		}
	}
	for (int i=1;i<=tot;i++) {
		if (cnt[i][0] < n) {
			for (int j=0,l=0,r=0;j<L;j++) {
				if (cnt[i][j]) {
					r += cnt[i][j];
					(vout += (LL)(pre2[r] - pre2[l]) * j % MOD) %= MOD;
					l = r;
				}
			}
		}
	}
	printf("%d\n",(vout+MOD)%MOD);
	return 0;
}

【BZOJ 4403】序列统计

链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4403
神犇题解:https://oi.men.ci/bzoj-4403/

题解

因为数定了,其单调不降的序列也就定了
所以这题就是求\(\sum\limits_{L = 1}^n {C_{r – l + L}^{r – l}} \)
然后化简一下就得到最终答案为:C(r-l+1,n+r-l+1)-1
ps:因为懒到不想写latex,所以化简过程让我们去膜拜Menci
因为n,l,r都巨大,所以用lucas定理来求组合数

Code

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

const int N = 1000000+9;
const int MX = 1000000+2; 
const int MOD = 1000000+3;

int T,POW[N],REV[N];

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) {
	int ret = 1;
	while (t) {
		if (t & 1) ret = (LL)ret * w % MOD;
		w = (LL)w * w % MOD; t >>= 1;
	}
	return ret;
}

inline void prework() {
	POW[0] = REV[0] = 1;
	for (int i=1;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;
}

int C(int a, int b) {
	if (a > b) return 0;
	else if (b <= MX) {
		return (LL)POW[b] * REV[a] * REV[b-a] % MOD;
	} else {
		return (LL)C(a%MOD, b%MOD) * C(a/MOD, b/MOD) % MOD;
	}
}

int main(){
	prework();
	for (int T=read(),n,l,r;T;T--) {
		n = read(); l = read(); r = read();
		printf("%d\n",(C(r-l+1,n+r-l+1)-1+MOD)%MOD);
	}
	return 0;
}

【BZOJ 4361】isn

链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4361
数据传送门:http://oi.cyo.ng/?attachment_id=1898

题解

考虑一个长度为i的非下降子序列
如果忽略成为非下降子序列就停止的限制
那么其对于答案的贡献为g[i]*(n-i)!

现在考虑成为非下降子序列就停止的限制
对于长度为i的非下降子序列,非法的话,一定是从i+1的序列删掉一个数
所以减掉\(g[i + 1] \cdot (n – (i + 1))! \cdot (i + 1)\)即可

至于为什么这样会不重不漏、刚好删掉所有非法方案?
唯一的疑惑就在于有一些方案不在第一次非法时删除
但不难发现将第一段+第二段看成一个操作的话
每一个操作刚好不重不漏加上了所有的合法方案

代码

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

const int N = 2000+9;
const int MOD = 1000000007;

int tot,n,_hash[N],arr[N],f[N],POW[N]; 

namespace Fenwick_Tree{
	#define BIT Fenwick_Tree
	#define lowbit(x) ((x)&-(x))
	int cnt[N][N];
	
	inline void insert(int t, int p, int delta) {
		for (int i=p;i<=n;i+=lowbit(i)) 
			(cnt[t][i] += delta) %= MOD;
	}
	
	inline int query(int t, int p) {
		int ret = 0;
		for (int i=p;i;i-=lowbit(i))
			(ret += cnt[t][i]) %= MOD;
		return ret;
	} 
};

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(){
	n = read();
	for (int i=1;i<=n;i++) 
		_hash[i] = arr[i] = read();
	sort(_hash+1, _hash+1+n);
	tot = unique(_hash+1, _hash+1+n) - _hash - 1;
	for (int i=1;i<=n;i++) 
		arr[i] = lower_bound(_hash+1, _hash+1+tot, arr[i]) - _hash;
	POW[1] = POW[0] = 1;
	for (int i=2;i<=n;i++) 
		POW[i] = (LL)POW[i-1] * i % MOD;
	
	for (int i=1;i<=n;i++) {
		for (int j=n,tmp;j>1;j--) {
			tmp = BIT::query(j-1,arr[i]);
			(f[j] += tmp) %= MOD;
			BIT::insert(j,arr[i],tmp);
		}
		BIT::insert(1,arr[i],1);
		f[1]++;
	} 
	
	int vout = 0;
	for (int i=1;i<=n;i++) {
		(vout += (LL)f[i] * POW[n-i] % MOD) %= MOD;
		if (i < n) 
			(vout -= ((LL)f[i+1] * POW[n-i-1] % MOD) * (i+1) % MOD) %= MOD;
	}
	printf("%d\n",(vout+MOD)%MOD);
	return 0;
}

【NOIP十连测】[D3T2] 涂色游戏

题目传送门:http://oi.cyo.ng/wp-content/uploads/2016/10/test3_problem.pdf
官方题解:http://oi.cyo.ng/wp-content/uploads/2016/10/solution.pdf

这题做起来还是感觉很有意思的!
然而这™是NOIP模拟题! (╯‵□′)╯︵┻━┻

详细的看题解吧!
题解的式子枚举的是并集的大小,我枚举的是交集的大小
反正都一样,式子搞出来都差不多!

另外下一次如果组合数表较小的话还是先预处理出来吧
这一份代码是现场算的,超级蛋疼!

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

const int N = 100+9;
const int MOD = 998244353;

int n,m,p,q,POW[N],REV[N],g[N][N];
struct Matrix{
	int a[N][N];
	inline Matrix() {}
	inline Matrix(const Matrix &B) {
		memcpy(this,&B,sizeof(*this));
	} 
	inline Matrix(int x) {
		memset(a,0,sizeof(a));
		for (int i=1;i<=n;i++) {
			a[i][i] = x;
		}
	}
	inline Matrix operator * (const Matrix &B) {
		Matrix ret(0);
		for (int j=1;j<=n;j++) {
			for (int i=1;i<=n;i++) {
				for (int k=1;k<=n;k++) {
					ret.a[i][j] += (LL)a[k][j] * B.a[i][k] % MOD;
					ret.a[i][j] %= MOD;
				}
			}
		}
		return ret;
	}
	inline Matrix operator ^ (int t) {
		Matrix ret(1),tmp(*this);
		while (t) {
			if (t & 1) ret = ret * tmp;
			tmp = tmp * tmp; t >>= 1;
		}
		return ret;
	}
}trans,ans; 

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) {
	int ret = 1;
	while (t) {
		if (t&1) ret = (LL)ret * w % MOD;
		w = (LL)w * w % MOD; t >>= 1;
	}
	return ret;
}

inline int alph(int a, int b, int x) {
	if (x > a || x > b || p-a-b+x < 0) return 0;
	int ret = (LL)POW[a] * POW[p-a] % MOD;
	ret = (LL)ret * REV[x] % MOD;
	ret = (LL)ret * REV[a-x] % MOD;
	ret = (LL)ret * REV[b-x] % MOD;
	ret = (LL)ret * REV[p-a-b+x] % MOD;
	return ret;
}

int main(){
	n = read(); m = read();
	p = read(); q = read();
	POW[0] = REV[0] = 1;
	for (int i=1;i<=max(n,p);i++) {
		POW[i] = (LL)POW[i-1] * i % MOD;
	}
	REV[max(n,p)] = pow(POW[max(n,p)],MOD-2);
	for (int i=max(n,p)-1;i;i--) {
		REV[i] = (LL)REV[i+1] * (i+1) % MOD;
	}
	g[1][1] = p;
	for (int i=2;i<=n;i++) {
		for (int j=1;j<=p;j++) {
			g[i][j] = (LL)g[i-1][j-1] * (p - j + 1) % MOD + (LL)g[i-1][j] * j % MOD;
			g[i][j] %= MOD;
		}
	}
	for (int a=1;a<=n;a++) {
		for (int b=1;b<=n;b++) {
			if (a > p || b > p) continue;
			for (int x=0;x<=a+b-q;x++) {
				trans.a[b][a] += alph(a,b,x);
				trans.a[b][a] %= MOD;
			}
			trans.a[b][a] = ((LL)g[n][b]*REV[p]%MOD) * trans.a[b][a] % MOD;
			trans.a[b][a] = ((LL)POW[b]*POW[p-b]%MOD) * trans.a[b][a] % MOD;
		}
	}
	for (int i=1;i<=min(n,p);i++) {
		ans.a[i][1] = g[n][i];
	}
	trans = trans ^ (m-1);
	ans = ans * trans;
	int vout = 0;
	for (int i=1;i<=n;i++) {
		vout += ans.a[i][1];
		vout %= MOD;
	}
	printf("%d\n",vout);
	return 0;
}