【日常小测】最长路径

相关链接

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

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

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

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

【UOJ 137】[UER #3] 开学前的日历

题目传送门:http://uoj.ac/problem/137
官方题解:http://vfleaking.blog.uoj.ac/blog/714

这个题,考试的时候想到了50分的算法,但没写出来QAQ
都搞到这个程度了:
45648645
还是没有想出来,可惜啊!

70分算法的关键:\(\left( \begin{array}{l}
x\\
y
\end{array} \right) = \left( \begin{array}{l}
x – 1\\
y
\end{array} \right) + \left( \begin{array}{l}
x – 1\\
y – 1
\end{array} \right)\)

100分的关键:
看一看上面那个图,组合数实际的意义是从(u,v)走到每个点的路径的个数
于是搞一搞dp即可

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

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

int f[N][N][N*2],n,m,q,X;

inline int read(){
	X = (100000005*(LL)X+20150823) % MOD;
	return X / 100;
}

int main(){
	cin>>m>>n>>q>>X;
	for (int i=1,u,v,k;i<=q;i++) {
		v = read()%m+1, u = read()%n+1, k = read()%(n+m-v-u+1);
		f[u][v][k]++;
	} 
	for (int j=1;j<=m;j++) for (int i=1;i<=n;i++) {
		for (int k=0;k<=n+m;k++) (f[i][j][k] += (f[i-1][j][k+1] + f[i][j-1][k+1]) % MOD) %= MOD;
		(f[i][j][0] += (f[i-1][j][0] + f[i][j-1][0]) % MOD) %= MOD;
	}
	for (int j=1;j<=m;j++) for (int i=1;i<=n;i++) 
		printf("%d%c",f[i][j][0],(i==n?'\n':' '));
	return 0;
}

【UOJ 241】破坏发射台

题目传送门:http://uoj.ac/problem/241
官方题解:http://c-sunshine.blog.uoj.ac/blog/2026

考试的时候,推这个题推了两个半小时QAQ
一直觉得马上就可以推出来辣!结果一直没有推出来
不过最后还是成功把奇数的式子推出来了(虽然和std不同,但是正确的)
至于偶数的式子嘛,感觉题解说的不是很清楚,我也就来哔哔两句:
不难发现,如果我们仍然按位来递推,不方便处理穿过发射台的情况
于是我们定义二元组(f,g)表示第i位与i+n/2位的颜色情况
于是我们发现这样的定义就可以按二元组为阶段来递推了,因为这货就无后效性了
于是搞一搞矩阵乘法即可
ps:为什么我做这题的时候老想着数位DP
V5[YANBJ`4%A2`%PIH$BH_F

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#define LL long long
#define abs(x) ((x)>0?(x):-(x))
#define S(x,y) ((x)*3+(y)+1)
using namespace std;

const int MOD = 998244353;
const int N = 100000;
const int M = 9;

int n,m,vout;

struct Matrix{
	int a[M][M];
	inline Matrix() {}
	inline Matrix(int v) {memset(a,0,sizeof(a));for(int i=1;i<M;i++) a[i][i]=v;}
	inline Matrix operator = (const Matrix &B) {memcpy(&(*this),&B,sizeof(a));}
	inline Matrix operator * (const Matrix &B) {
		Matrix ret(0);
		for (int i=1;i<M;i++) for (int j=1;j<M;j++) for (int k=1;k<M;k++) 
			ret.a[i][j] = ((LL)a[k][j]*B.a[i][k] + ret.a[i][j]) % MOD;
		return ret;
	}
	inline Matrix operator ^ (int t) {
		Matrix ret(1),w=*this;
		while (t) {
			if (t & 1) ret = ret*w;
			w = w*w; t >>= 1;	
		}
		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;
}

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

int main(){
	n = read(), m = read();
	if (n%2 == 0) {
		Matrix ori(0),tra(0); ori.a[S(1,2)][1]=1;
		if (m > 3) tra.a[S(0,0)][S(1,2)] = tra.a[S(0,0)][S(2,1)] = (LL)(m - 2) * (m - 3) % MOD;
		if (m > 3) tra.a[S(0,0)][S(1,0)] = tra.a[S(0,0)][S(0,1)] = (LL)(m - 3) * (m - 3) % MOD;
		if (m > 3) tra.a[S(0,0)][S(2,0)] = tra.a[S(0,0)][S(0,2)] = (LL)(m - 3) * (m - 3) % MOD;
		if (m > 3) tra.a[S(0,0)][S(0,0)] = ((LL)(m-4) * (m-4) + m - 3) % MOD;
		
		if (m > 2) tra.a[S(1,0)][S(2,1)] = tra.a[S(0,1)][S(1,2)] = m - 2;
		if (m > 2) tra.a[S(1,0)][S(0,1)] = tra.a[S(0,1)][S(1,0)] = m - 2;
		if (m > 2) tra.a[S(1,0)][S(0,2)] = tra.a[S(0,1)][S(2,0)] = m - 2;
		if (m > 3) tra.a[S(1,0)][S(2,0)] = tra.a[S(0,1)][S(0,2)] = m - 3;
		if (m > 3) tra.a[S(1,0)][S(0,0)] = tra.a[S(0,1)][S(0,0)] = m - 3;
		
		if (m > 2) tra.a[S(2,0)][S(1,2)] = tra.a[S(0,2)][S(2,1)] = m - 2;
		if (m > 2) tra.a[S(2,0)][S(0,2)] = tra.a[S(0,2)][S(2,0)] = m - 2;
		if (m > 2) tra.a[S(2,0)][S(0,1)] = tra.a[S(0,2)][S(1,0)] = m - 2;
		if (m > 3) tra.a[S(2,0)][S(1,0)] = tra.a[S(0,2)][S(0,1)] = m - 3;
		if (m > 3) tra.a[S(2,0)][S(0,0)] = tra.a[S(0,2)][S(0,0)] = m - 3;
		
		tra.a[S(1,2)][S(0,1)] = tra.a[S(2,1)][S(1,0)] = 1;
		tra.a[S(1,2)][S(2,0)] = tra.a[S(2,1)][S(0,2)] = 1;
		tra.a[S(1,2)][S(2,1)] = tra.a[S(2,1)][S(1,2)] = 1;
		tra.a[S(1,2)][S(0,0)] = tra.a[S(2,1)][S(0,0)] = 1;
		
		tra = tra^(n/2-1); ori = ori * tra;
		vout = ((LL)ori.a[S(0,2)][1] + ori.a[S(1,0)][1] + ori.a[S(1,2)][1] + ori.a[S(0,0)][1]) % MOD;
		vout = ((LL)vout * m % MOD) * (m-1) % MOD;
		printf("%d\n",vout);
	}
	else {
		if (n == 3) printf("%d\n",((LL)(pow(m-1,n-1)-(m-1))*m % MOD + MOD) % MOD);
		else {
			Matrix ori(0); ori.a[1][1] = 1; ori.a[2][1] = m-2;
			Matrix tra(0); tra.a[1][2] = 1; tra.a[2][1] = m-1; tra.a[2][2] = m-2; 
			tra = tra^(n-5); ori = ori * tra; ori.a[1][1] = (LL)ori.a[1][1]*(m-1)%MOD;
			vout = (((LL)(m-1)*(m-2)%MOD)*ori.a[2][1]%MOD + (LL)ori.a[1][1]*(m-1)%MOD) % MOD;
			vout = (LL)(pow(m-1,n-1)-vout)*m % MOD;
			printf("%d\n",(vout+MOD)%MOD);
		}
	}
	return 0;
}

—– UPD 2017.1.12 —–
今天听毛爷爷讲这个题
居然感觉自己只会做奇数情况 QwQ
其实重点是,这货偶数情况的转移似乎非常神奇的样子
定义状态的方式,非常值得借鉴

【HDU 3037】Saving Beans

题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=3037
数据生成器:http://paste.ubuntu.com/22886753/

lucas定理 + 插板法

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

const int MAXN = 100000+9;

int f[MAXN];

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

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

inline int C(int m,int n, int p) {
	if (n > m) return 0;
	else return (LL)f[m]*quick_pow(f[m-n],p-2,p)*quick_pow(f[n],p-2,p)%p;
}

int lucas(int m, int n, int p) {
	if (n == 0) return 1;
	else return ((LL)lucas(m/p,n/p,p) * C(m%p,n%p,p)) % p;
}

int main(){
	int T = read(); while (T--) {
		int n = read(),m = read(),p = read(); 
		f[0] = 1; for (int i=1;i<=p;i++) f[i] = (LL)f[i-1]*i % p;
		printf("%d\n",lucas(n+m,n,p));
	}
	return 0;
}

另外,lucas定理可以推广到整数域上,参见:
http://www.cnblogs.com/jianglangcaijin/p/3446839.html