Category: 组合数学

题目传送门：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://codeforces.com/problemset/problem/711/E
官方题解：http://codeforces.com/blog/entry/46830
中文题面及题解：https://blog.sengxian.com/solutions/cf-711e

这个题重点不在推概率，而在Legendre’s formula
其实难点就是要求在取MOD之前就约分，这个就很麻烦了，只有用上面那个定理

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

const LL MOD = 1000003;

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

inline bool judge(LL n, LL k) {
	LL w = 1;
	for (int i=1;i<=n;i++) {
		w *= 2;
		if (w >= k) return false;
	} return true;
}

int main(){
	LL n = read(), k = read(), tn = pow(2,n);
	if (judge(n,k)) cout<<1<<' '<<1;
	else {
		LL t1, t2, cnt = (k-1) - __builtin_popcountll(k-1), gcd = pow(pow(2,cnt),MOD-2);
		if (k >= MOD) t1 = 0; else {t1 = 1; for (int i=1;i<k;i++) t1 = t1 * (tn - i) % MOD;}
		t2 = pow(pow(2,n),k-1); t2 = t2 * gcd % MOD; t1 = t1 * gcd % MOD; t1 = ((t2 - t1)% MOD + MOD) % MOD;
		cout<<t1<<' '<<t2;
	} 
	return 0;
}

ps:如果不知道上面的那个定理，貌似自己推也是可以推出来的？

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

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

#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
其实重点是，这货偶数情况的转移似乎非常神奇的样子
定义状态的方式，非常值得借鉴