组合计数与容斥

\(\newcommand \m \mathbf\)
\(\newcommand \c \dbinom\)
\(\newcommand \bel \subseteq\)

\(\text{By DaiRuiChen007}\)

I. [BZOJ2916] - Monochromatic Triangles

\(\text{Link}\)

思路分析

设点 \(x\) 共连接了 \(siz_x\) 条红边，那么反面考虑，考虑从 \(x\) 出两条异色边的异色三角形个数：\(siz_x\times (n-siz_x-1)\)，由于每个异色三角形的异色角恰两个，所以每个三角形仅被考虑了 \(2\) 次，故：

\[\text{Answer}=\c n3-\dfrac{1}{2}\sum_{i=1}^n [siz_{i}\times(n-siz_i-1)]
\]

当然我有另一种乱搞做法，但是不具备什么参考性，公式如下：

\[\text{Answer}=\c n 3-m\times(n-2)+\sum_{i=1}^{n} \c {siz_i}2
\]

证：

设 \(k_i,i\in\{0,1,2,3\}\) 表示恰好有 \(i\) 条红边的三角形个数，考虑 \(k_{0}\sim k_3\) 对每一项的贡献

由题可知：\(\text{LHS}=\text{Answer}=k_0+k_3\)

  • 对于 \(\c n 3\)，其意义为：计算每种三角形各一次，故 \(\c n 3=k_0+k_1+k_2+k_3\)
  • 对于 \(m\times (n-2)\)，其意义为：枚举某一条特定的红边，任取一个点与其构成三角形，不难发现某个三角形被计算的次数恰好等于其红边的数量，故 \(m\times(n-2)=k_1+2k_2+3k_3\)
  • 对于 \(\sum\limits_{i=1}^n \c {siz_i}2\)，其意义为：枚举某一个顶点，其顶点连出的两条边都是红边，则每个三角形被计算的次数恰好为其红色角的个数，故 \(\sum\limits_{i=1}^n \c {siz_i}2=k_2+3k_3\)

综上可知：

\[\begin{aligned}
\text{RHS}&=(k_0+k_1+k_2+k_3)-(k_1+2k_2+3k_3)+(k_2+k_3)\\
&=k_0+k_3\\
&=\text{LHS}
\end{aligned}
\]

证毕

这个式子其实纯属巧合的产物，但是它能跑，离谱。。。

时间复杂度 \(\Theta(n+m)\)

代码呈现

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=1001,MAXM=250001;
int siz[MAXN];
signed main() {
	int n,m,res=0;
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=m;++i) {
		int u,v;
		scanf("%lld%lld",&u,&v);
		++siz[u],++siz[v];
	}
	for(int i=1;i<=n;++i) res+=siz[i]*(n-siz[i]-1);
	printf("%lld\n",(n*(n-1)*(n-2)/3-res)/2);
	return 0;
}

II. [洛谷3166] - 数三角形

\(\text{Link}\)

思路分析

正难则反，考虑用总数减去所有三点共线的图形个数

求解总数以及竖直的三点共线或者水平的三点共线数量显然是非常 trivial 的，故重点研究斜三点共线的个数

考虑坐标系中一条连接原点和 \((x,y)\) 的直线与整点的交点个数，显然 \(\gcd(x,y)+1\) 即为所求

证：

考虑这条直线在原点之外第一次相交的整点 \((x_0,y_0)\)，满足 \(\dfrac{y_0}{x_0}=\dfrac y x\)，且不难得到该直线与整点共交 \(\dfrac {y}{y_0}=\dfrac{x}{x_0}\) 次，故 \(\dfrac{y}{y_0},\dfrac{x}{x_0}\in \mathbb{Z}^+\)

由于 \(x_0,y_0\) 要尽可能小，且 \(x_0|x,y_0|y\)，所以我们不难得到 \(x_0=\dfrac{x}{\gcd(x,y)},y_0=\dfrac{y}{\gcd(x,y)}\)

故所求答案数应该为 \(\dfrac x {x_0}=\gcd(x,y)\)，加上原点即得所求

所以我们考虑一对点 \((i,j)\) 和 \((i+x,j+y)\)，考虑第三个点在这条直线上的情况吗，恰好有 \(\gcd(x,y)-1\) 种，因此我们可以枚举 \(x,y\)，则满足条件的 \(i,j\) 恰好有 \((n-x+1)\times(m-y+1)\) 对，结合其他水平竖直共线的情况有：

\[\text{Answer}=\c {(n+1)(m+1)}3-(n+1)\c{m+1}3-(m+1)\c {n+1} 3-\sum_{x=1}^{n}\sum_{y=1}^m(n-x+1)\times(m-y+1)\times(\gcd(x,y)-1)
\]

时间复杂度 \(\Theta(nm)\)

代码呈现

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int calc(int x) {
	return (x*(x-1)*(x-2)/6);
}
signed main() {
	int n,m;
	scanf("%lld%lld",&n,&m);
	int res=calc((n+1)*(m+1));
	res-=(n+1)*calc(m+1);
	res-=(m+1)*calc(n+1);
	for(int i=1;i<=m;++i) {
		for(int j=1;j<=n;++j) {
			int x=(m-i+1)*(n-j+1)*(__gcd(i,j)-1);
			res-=x*2;
		}
	}
	printf("%lld\n",res );
	return 0;
}

III. [洛谷5505] - 分特产

\(\text{Link}\)

思路分析

容斥，和上一题相当类似，设 \(\m{A_S}\) 表示 \(\forall i\in\m S\)，第 \(i\) 个人总共拿到 \(0\) 件礼物的方案集合

显然，\(|\m {A_S}|\) 只与 \(\m S\) 的大小有关，根据插板法可得：

\[|\m {A_S}|=\prod_{i=1}^m \c {a_i+n-|\m S|-1}{n-|\m S|-1}
\]

然后进行容斥原理，可得：

\[\begin{aligned}
\text{Answer}
&=|\m A_\varnothing|-\sum |\m A_{\{i\}}|+\sum |\m A_{\{i,j\}}|-\sum |\m A_{\{i,j,k\}}|+\cdots\\
&=\sum_{i=0}^{n} (-1)^i \c{m}{i}\prod_{j=1}^m\c{a_j+n-i-1}{n-i-1}
\end{aligned}
\]

时间复杂度 \(\Theta(nm)\)

代码呈现

#include<bits/stdc++.h>
using namespace std;
const int MAXV=2001,MAXN=1001,MOD=1e9+7;
#define int long long
inline int ksm(int a,int b=MOD-2,int m=MOD) {
	int res=1;
	while(b) {
		if(b&1) res=res*a%m;
		a=a*a%m;
		b=b>>1; 
	}
	return res;
}
int fac[MAXV],inv[MAXV];
inline void init() {
	fac[0]=inv[0]=1;
	for(int i=1;i<MAXV;++i) {
		fac[i]=fac[i-1]*i%MOD;
		inv[i]=ksm(fac[i]); 
	}
}
inline int C(int m,int n) {
	return fac[m]*inv[n]%MOD*inv[m-n]%MOD;
} 
int a[MAXN];
signed main() {
	init();
	int n,m,res=0;
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=m;++i) scanf("%lld",&a[i]);
	for(int i=0,op=1;i<n;++i,op*=-1) {
		int k=op*C(n,i);
		for(int j=1;j<=m;++j) k=k*C(a[j]+n-i-1,n-i-1)%MOD;
		res+=k;
		res=(res%MOD+MOD)%MOD;
	}
	printf("%lld\n",res);
	return 0;
}

IV. [洛谷2476] - 着色方案

\(\text{Link}\)

思路分析

考虑数数 dp，稍微修改一下对操作的理解，我们将对序列涂色的操作改为每次插入某种颜色的若干个元素，设 \(dp_{i,j}\) 表示考虑了前 \(i\) 种元素，且有 \(j\) 对相邻的元素颜色相等，对于 \(dp_{i,j}\) 的转移，我们可以考虑用刷表法，枚举第 \(i+1\) 种颜色，分成 \(a\) 段连续的球，其中 \(b\) 段放到同色的元素之间

考虑上述的方式共有多少种，分步计算：

  1. 将 \(c_{i+1}\) 个数分成 \(a\) 段，\(\c{c_{i+1}-1}{a-1}\) 种情况
  2. 在 \(j\) 对相邻的元素中选择 \(b\) 对插入新的一段元素，\(\c j b\) 种情况
  3. 之前的 \(s_i+1\)（\(c_i\) 的前缀和）的空（包括两端）除去 \(j\) 个同色的空隙之间选择 \(a-b\) 个空插入一段元素，
    \(\c{s_i-j+1}{a-b}\) 种情况

那么在原先 \(j\) 对同色相邻元素的基础上，新增了 \(c_{i+1}-a\) 对相邻同色，减少了 \(b\) 对相邻同色，所以有：

\[dp_{i+1,j-b+c_{i+1}-a}\gets \c{c_{i+1}-1}{a-1}\c j b\c{s_i-j+1}{a-b}\times dp_{i,j}
\]

时间复杂度 \(\Theta(k^4)\)

代码呈现

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXV=81,MOD=1e9+7;
int dp[16][81],c[16],s[16];
inline int ksm(int a,int b=MOD-2,int m=MOD) {
	int res=1;
	while(b) {
		if(b&1) res=res*a%m;
		a=a*a%m;
		b=b>>1; 
	}
	return res;
}
int fac[MAXV],inv[MAXV];
inline void init() {
	fac[0]=inv[0]=1;
	for(int i=1;i<MAXV;++i) {
		fac[i]=fac[i-1]*i%MOD;
		inv[i]=ksm(fac[i]); 
	}
}
inline int C(int m,int n) {
	if(n<0||n>m) return 0;
	return fac[m]*inv[n]%MOD*inv[m-n]%MOD;
} 
signed main() {
	init();
	int n;
	scanf("%lld",&n);
	for(int i=1;i<=n;++i) {
		scanf("%lld",&c[i]);
		s[i]=s[i-1]+c[i];
	}
	dp[1][c[1]-1]=1;
	for(int i=1;i<n;++i) {
		for(int j=0;j<s[i];++j) {
			for(int a=1;a<=c[i+1];++a) {
				for(int b=0;b<=a&&b<=j;++b) {
					dp[i+1][j-b+c[i+1]-a]+=dp[i][j]*C(c[i+1]-1,a-1)%MOD*C(j,b)%MOD*C(s[i]-j+1,a-b)%MOD;
					dp[i+1][j-b+c[i+1]-a]%=MOD;
				}
			}
		}
	}
	printf("%lld\n",dp[n][0]);
	return 0;
}

V. [洛谷1450] - 硬币购物

\(\text{Link}\)

思路分析

\(n\) 次完全背包显然会超时，考虑保留一些有效信息

首先预处理出每种硬币没有数量限制的情况下，可以获得价值 \(c\) 的方案总数 \(dp[c]\)

对于每次询问，考虑容斥原理，假设 \(f(\m S)\) 表示 \(\forall i\in \m S\)，第 \(i\) 枚硬币选择的次数超过 \(d_i\)，获得价值 \(s\) 的方案总数，显然，我们可以强制先选 \(d_i+1\) 枚 \(i\) 类硬币，然后再做完全背包，所以有：

\[f(\m S)=dp\left[s-\sum_{i\in\m S} (d_i+1)c_i\right]
\]

然后对答案进行一次容斥原理统计即可：

\[\text{Answer}=\sum_{\m S\subseteq\{1,2,3,4\}} (-1)^{|\m S|}f(\m S)
\]

时间复杂度 \(\Theta(2^4\times n+s)\)

总结：

看到物品有上下界限制的，都可以考虑容斥原理

其实这道题的思路和第三题相当类似，只不过第三题的统计是组合数插板，这题的统计是预处理背包

注意：抓本质

代码呈现

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=1e5+1;
int dp[MAXN],c[5],d[5];
signed main() {
	int n;
	scanf("%lld%lld%lld%lld%lld",&c[1],&c[2],&c[3],&c[4],&n);
	dp[0]=1;
	for(int i=1;i<=4;++i) {
		for(int j=c[i];j<MAXN;++j) {
			dp[j]+=dp[j-c[i]];
		}
	}
	while(n--) {
		int s,res=0;
		scanf("%lld%lld%lld%lld%lld",&d[1],&d[2],&d[3],&d[4],&s);
		for(int S=0;S<16;++S) {
			int op=1,tot=s;
			for(int i:{1,2,3,4}) {
				if(S&(1<<(i-1))) {
					op*=-1;
					tot-=(d[i]+1)*c[i];
				}
			}
			if(tot>=0) res+=op*dp[tot];
		}
		printf("%lld\n",res);
	}
	return 0;
}

VI. [洛谷4318] - 完全平方数

\(\text{Link}\)

思路分析

求第 \(K\) 大数，显然考虑二分，将问题转化成：对于某个 \(k\)，求出 \(1\sim k\) 中有多少个满足条件的数

考虑容斥，设 \(\m B_x\) 表示 $1\sim $k 所有满足 \(x^2|u\) 的所有 \(u\) 构成的集合

从定义出发，不难得到 \(|\m B_x|=\left\lfloor\dfrac{k}{x^2}\right\rfloor\)

设 \(p_1\sim p_m\) 表示 \(1\sim k\) 中的全部质数，对答案进行容斥可得：

\[\begin{aligned}
\text{Answer}
&=|\m B_1|-\sum|\m B_{p_i}|+\sum|\m B_{p_i}\cap \m B_{p_j}|-\sum|\m B_{p_i}\cap\m B_{p_j}\cap \m B_{p_k}|+\cdots\\
&=|\m B_1|-\sum|\m B_{p_i}|+\sum|\m B_{p_i\times p_j}|-\sum|\m B_{p_i\times p_j\times p_k}|+\cdots\\
\end{aligned}
\]

考虑用另一种形式表示 \(\text{Answer}\)，设 \(\lambda(x)\) 为一个数论函数，表示上式中 \(|\m B_x|\) 的贡献，则有：

\[\text{Answer}=\sum_{x=1}^k \lambda(x)|\m B_x|
\]

比较一下上下两式的系数可得：

  • 若 \(x=1\)，则 \(\lambda(x)=1\)
  • 若 \(x\) 中含有两个相同的质因子，则 \(\lambda(x)=0\)
  • 若 \(x\) 中仅含有 \(k\) 个互不相同的质因子，则 \(\lambda(x)=(-1)^k\)

通过比对，可以发现 \(\lambda(x)=\mu(x)\)

所以：

\[\begin{aligned}
\text{Answer}
&=\sum_{x=1}^k \mu(x)|\m B_x|\\
&=\sum_{x=1}^k \mu(x)\left\lfloor\dfrac{k}{x^2}\right\rfloor
\end{aligned}
\]

注意到当且仅当 \(x\le \sqrt k\) 时右式 \(\neq0\)，所以可以优化求和：

\[\text{Answer}=\sum_{x=1}^{\left\lfloor\sqrt k\right\rfloor} \mu(x)\left\lfloor\dfrac k{x^2}\right\rfloor
\]

直接爆算即可，设 \(n\) 为最大答案，时间复杂度 \(\Theta(T\sqrt n\log n )\)，当然也可以用整除分块优化到 \(\Theta(T\sqrt[4]n\log n)\)，不过显然多此一举

事实上，\(n\) 大概为 \(1.6\times 10^9\)，因此可以通过本题

总结：

又是熟悉的莫比乌斯函数作容斥系数的题目，可是我又没做出来。。。

好像这一类的题目都和数论计数有关？而且好像都只用考虑质数乘积之间的容斥关系

代码呈现

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=40561,INF=1644934090;
int mu[MAXN],k;
bool vis[MAXN];
inline void init() {
	for(int i=1;i<MAXN;++i) mu[i]=1;
	for(int i=2;i<MAXN;++i) {
		if(vis[i]) continue;
		for(int j=i;j<MAXN;j+=i) {
			vis[j]=true;
			if(j%(i*i)) mu[j]*=-1;
			else mu[j]=0;
		}
	}
}
inline int calc(int x) {
	int res=0;
	for(int i=1;i*i<=x;++i) res+=mu[i]*(x/(i*i));
	return res;
}
inline bool check(int x) {
	return calc(x)>=k;
}
signed main() {
	init();
	int T;
	scanf("%lld",&T);
	while(T--) {
		scanf("%lld",&k);
		int l=0,r=INF,res=-1;
		while(l<=r) {
			int mid=(l+r)>>1;
			if(check(mid)) r=mid-1,res=mid;
			else l=mid+1;
		}
		printf("%lld\n",res);
	}
	return 0;
}

VII. [洛谷5933] - 串珠子

\(\text{Link}\)

思路分析

简化问题，考虑每条边只有一种连接方式

那么我们可以设 \(f_n\) 表示 \(n\) 个点的连接方案，正难则反，考虑减去不连通的情况，设 \(g_n\) 表示 \(n\) 个点连接起来不一定联通的方案数，不难得到：

\[g_n=2^{\c n2}
\]

那么我们可以考虑枚举 \(1\) 所在的连通块，让这个连通块之外的数随便排列即可，得到：

\[f_n=g_n-\sum_{i=1}^{n-1}\c{n-1}{i-1}f_{i}\times g_{n-i}
\]

本题同理，不过由于每个点是不同的，所以我们应该进行状压，设 \(f(\m S)\) 表示 \(\m S\) 中的每个数都联通的方案总数，同理有 \(g(\m S)\) 的定义，枚举 \(\m S\) 中点两两连边的情况，不难得到：

\[g(\m S)=\prod_{i,j\in \m S} (c_{i,j}+1)
\]

然后类似刚才的思路，为了去掉 \(\m S\) 中不连通的情况，我们枚举 \(\m S\) 中最小元素 \(x\) 所在连通块的集合 \(\m T\)，设 \(\overline{\m T}\) 为 \(\m S\) 中 \(\m T\) 的补集，则有

\[f(\m S)=g(\m S)-\sum_{\m T\bel \m S}^{x\in\m T} f(\m T)\times g\left(\overline{\m T}\right)
\]

时间复杂度 \(\Theta(3^n)\)

代码呈现

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=16,MOD=1e9+7;
int f[1<<MAXN],g[1<<MAXN],c[MAXN][MAXN];
inline int lowbit(int x) {
	return x&-x;
}
signed main() {
	int n;
	scanf("%lld",&n);
	for(int i=0;i<n;++i) for(int j=0;j<n;++j) scanf("%lld",&c[i][j]);
	int S=(1<<n);
	for(int s=0;s<S;++s) {
		g[s]=1;
		for(int i=0;i<n;++i) {
			if(!((s>>i)&1)) continue;
			for(int j=i+1;j<n;++j) {
				if(!((s>>j)&1)) continue;
				g[s]=g[s]*(c[i][j]+1)%MOD;
			}
		}
	} 
	for(int s=0;s<S;++s) {
		f[s]=g[s];
		for(int t=s;t;t=(t-1)&s) {
			if(t==s||!(t&lowbit(s))) continue;
			f[s]-=g[s^t]*f[t]%MOD;
			f[s]=(f[s]%MOD+MOD)%MOD;
		}
	}
	printf("%lld\n",f[S-1]);
	return 0;
}

VIII. [CodeForces111D] - Petya and Coloring

\(\text{Link}\)

思路分析

独立切的第一道 CF2300 的题，好耶

设 \(\m S_i\) 表示第 \(i\) 列使用的颜色集合，\(\m L_i\) 表示第 \(1\) 列到第 \(i\) 列用的颜色集合，\(\m R_i\) 表示第 \(i\) 列到第 \(n\) 列用的颜色集合

考虑从 \(\m L_i\) 转移到 \(\m L_{i+1}\) 的过程，由定义我们知道 \(\m L_{i+1}=\m L_{i}\cup \m S_{i+1}\)，所以我们可以得到 \(\m L_i\bel \m L_{i+1}\)，因此得到 \(|\m L_i|\le |\m L_{i+1}|\)，因此，\(|\m L_{1}|\sim|\m L_m|\) 单调不降

同理，我们可以得到 \(|\m R_1|\sim|\m R_m|\) 单调不升

但是，我们有 \(|\m L_1|=|\m R_2|,|\m L_2|=|\m R_3|,\cdots,|\m L_{m-1}|=|\m R_m|\)

所以 \(|\m R_2|=|\m L_1|\leq |\m L_2|=|\m R_{3}|\)，又 \(|\m R_3|\le|\m R_2|\)，所以得到 \(|\m R_2|=|\m R_3|\)

类推可知，\(|\m L_1|=|\m L_2|=\cdots=|\m L_{m-1}|=|\m R_2|=|\m R_3|=\cdots=|\m R_m|\)

考虑 \(\m S_1\) 和 \(\m S_2\) 的关系，由定义可得 \(\m S_1=\m L_1,\m S_1\cup\m S_2=\m L_2\)，所以有 \(\m L_1\bel\m L_{2}\)，又因为 \(|\m L_1|=|\m L_2|\)，所以我们得到：\(\m L_1=\m L_2\)

所以有 \(\m S_1=\m S_1\cup \m S_2\) 因此 \(\m S_2\bel \m S_1\)

同理继续分析，考虑 \(\m L_2\) 和 \(\m L_3\) 的关系，注意到 \(\m L_2=\m L_1=\m S_1\)，所以类似上面的过程，也能得到 \(\m S_3\bel\m S_1\)

类推到 \(\m S_4\sim\m S_{m-1}\)，都有这个性质，最终我们得到 \(\m S_2\sim\m S_{m-1}\bel \m S_1\)

然后再看 \(\m R _m\) 和 \(\m R_{m-1}\) 的关系，观察到 \(\m R_m=\m S_m\)，然后用上面类似的方法同理可得：\(\m S_{2}\sim\m S_{m-1}\bel \m S_{m}\)

联立上下，可知 \(\m S_2\sim\m S_{m-1}\bel \m S_1\cap\m S_m\)

又因为 \(|\m L_1|=|\m R_m|\) 且 \(\m L_1=\m S_1,\m R_m=\m S_m\)，所以有 \(|\m S_1|=|\m S_m|\)

此时整理一下我们的得到的条件：

  1. \(|\m S_1|=|\m S_m|\)
  2. \(\forall i\in(1,m),\m S_i\in \m S_1\cap \m S_m\)

然后我们可以考虑进行计数，首先枚举 \(|\m S_1|,|\m S_m|\)，设为 \(p\)，然后枚举 \(|\m S_1\cap\m S_m|\)，设为 \(i\)，然后考虑分步计数：

  1. 确定 \(\m S_1,\m S_m\)，首先求出 \(\m S_1\cap\m S_m\)，共有 \(\c ki\) 种情况，然后求出 \(\m S_1\) 的剩下部分，共有 \(\c{k-i}{p-i}\) 种情况，最后求出 \(\m S_m\) 的剩下部分，共有 \(\c {k-p}{p-i}\) 种情况，总数即三步情况数相乘，共有 \(\c ki\c{k-i}{p-i}\c{k-p}{p-i}\) 种

  2. 求出中间 \(m-2\) 列的具体涂色情况，每个格子都有 \(i\) 种涂色方式，没有其它的限制，故情况数为 \(i^{n(m-2)}\)

  3. 求出第 \(1\) 列和第 \(m\) 列的染色情况，不难发现这两列的染色情况数是相同的，且只与 \(p\) 有关，即恰好使用 \(p\) 种颜色染 \(n\) 个格子的方案数，不妨记为 \(f_n(p)\)，显然，我们可以通过容斥原理计算 \(f_n(p)\) 的值，考虑枚举强制让 \(x\) 个格子不选，其余列无限制的方案数，显然就是 \((n-x)^p\) 种，然后做一次简单容斥可得：

\[f_n(p)=\sum_{x=0}^n (-1)^x\c p x(n-x)^p
\]

综上所述，我们得到：

\[\text{Answer}=\sum_{p=1}^{\min(k,n)}\left[\sum_{x=0}^n (-1)^x\c px(n-x)^p\right]^2\left[\sum_{i=0}^p \c ki\c{k-i}{p-i}\c{k-p}{p-i}i^{n(m-2)}\right]
\]

直接计算，时间复杂度 \(\Theta(n^2)\)

代码呈现

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN=1e6+1,MOD=1e9+7;
int inv[MAXN],fac[MAXN];
inline int ksm(int a,int b=MOD-2,int m=MOD) {
	int res=1;
	while(b) {
		if(b&1) res=res*a%m;
		a=a*a%m;
		b=b>>1;
	}
	return res;
}
inline void init() {
	fac[0]=inv[0]=1;
	for(int i=1;i<MAXN;++i) fac[i]=fac[i-1]*i%MOD;
	inv[MAXN-1]=ksm(fac[MAXN-1]);
	for(int i=MAXN-2;i>0;--i) inv[i]=inv[i+1]*(i+1)%MOD;
}
inline int C(int m,int n) {
	if(n<0||n>m) return 0;
	return fac[m]*inv[n]%MOD*inv[m-n]%MOD;
}
signed main() {
	init();
	int n,m,k,res=0;
	scanf("%lld%lld%lld",&n,&m,&k);
	if(m==1) {
		printf("%lld\n",ksm(k,n));
		return 0;
	}
	for(int p=1;p<=k&&p<=n;++p) {
		int f=0;
		for(int i=0,op=1;i<=p;++i,op*=-1) {
			f+=op*C(p,i)*ksm(p-i,n)%MOD;
			f=(f%MOD+MOD)%MOD;
		}
		for(int i=0;i<=p;++i) {
			int t=f*f%MOD;
			t=t*C(k,i)%MOD;
			t=t*C(k-i,p-i)%MOD;
			t=t*C(k-p,p-i)%MOD;
			t=t*ksm(i,n*(m-2))%MOD;
			res=(res+t)%MOD;
		}
	}
	printf("%lld\n",res);
	return 0;
}

IX. [洛谷2481] - 代码拍卖会

\(\text{Link}\)

思路分析

记连续的 \(x\) 个数码 \(a\) 为 \((x\otimes a)\)，两段数 \(a,b\) 的拼接为 \(a\oplus b\)，即 \(\overline{ab}\)

对于某个上升数，可以考虑将其拆分为不超过 \(9\) 个全是 \(1\) 的串的和，即：

\[(c_1\otimes 1)\oplus(c_2\otimes2)\oplus\cdots\oplus(c_9\otimes 9)=((c1+c2+\cdots+c9)\otimes 1)+((c_2+c_3+\cdots+c_9)\otimes 1)+\cdots+(c_9\otimes1)
\]

然后我们可以预处理出长度为 \(1\sim n\) 的全 \(1\) 串在模 \(p\) 意义下每种余数共出现了几次，记为 \(cnt_0\sim cnt_{p-1}\)

显然，这步操作可以暴力判圈解决

由于原数长度给定，所以我们可以提前选出一个长度为 \(n\) 的全 \(1\) 串，然后问题就转化为了：

有 \(p\) 个价值，分别为 \(0\sim p-1\)，价值 \(i\) 对应了 \(cnt_i\) 个数，每个数可以选择的次数不限

现在选出不超过 \(9\)个数，使得这些数对应的价值之和模 \(p\) 为 \(0\)

其中要求某一个数至少选一次

显然我们可以考虑进行 dp，设 \(dp_{i,j,k}\) 表示考虑到价值 \([0,i)\) 的数，选择了其中的 \(j\) 个，总和余数为 \(k\) 的方案数

边界条件为 \(dp_{0,1,(n\otimes 1)\bmod p}=1\)

考虑枚举价值为 \(i\) 的物品选的次数有转移：

\[dp_{i+1,j+x,(k+x\times i)\bmod p}\gets dp_{i,j,k}\times f_{i,x}
\]

其中 \(f_{i,x}\) 表示从 \(cnt_i\) 个数（每个数可以重复选）中选 \(x\) 个的方案数，等价于将 \(x\) 拆成 \(cnt_i\) 个自然数之和，直接插板，答案为 \(\c {cnt_i+x-1}{x-1}\)，这里可以提前预处理出来参与计算

最终答案为 \(\sum\limits_{i=1}^p dp_{p,i,0}\)

时间复杂度 \(\Theta(p^2)\)

总结：

将上升数拆分是一个很高妙的 trick，剩下的 dp 比较 trivial

代码呈现

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=501,MOD=999911659;
int dp[MAXN][11][MAXN],f[MAXN][11],cnt[MAXN],lst[MAXN],inv[10];
inline int ksm(int a,int b=MOD-2,int m=MOD) {
	int res=1;
	while(b) {
		if(b&1) res=res*a%MOD;
		a=a*a%MOD;
		b=b>>1;
	}
	return res;
}
signed main() {
	int n,p,st=0;
	scanf("%lld%lld",&n,&p);
	if(n<=p) {
		int sum=1%p;
		for(int i=1;i<=n;++i) {
			++cnt[sum];
			if(i==n) st=sum;
			sum=(sum*10%p+1)%p;
		}
		st=sum;
	} else {
		int sum=1%p,len=0,cir=0;
		for(int i=1;i<=p+1;++i) {
			if(lst[sum]) {
				cir=lst[sum];
				len=i-cir;
				break;
			}
			lst[sum]=i;
			++cnt[sum];
			sum=(sum*10%p+1)%p;
		}
		for(int i=0;i<p;++i) {
			if(lst[i]>=cir) {
				cnt[i]+=(n-lst[i])/len;
				cnt[i]%=MOD;
				if(lst[i]%len==n%len) st=i;
			}
		}
	}
	for(int i=1;i<10;++i) inv[i]=ksm(i);
	dp[0][1][st]=1;
	for(int i=0;i<p;++i) {
		f[i][0]=1;
		for(int j=1;j<9;++j) {
			f[i][j]=f[i][j-1]*(cnt[i]+j-1)%MOD*inv[j]%MOD;
		}
	}
	for(int i=0;i<p;++i) {
		for(int j=0;j<p;++j) {
			for(int k=1;k<=9;++k) {
				if(!dp[i][k][j]) continue;
				for(int x=0;x+k<=9;++x) {
					dp[i+1][x+k][(j+x*i%p)%p]+=(dp[i][k][j]*f[i][x])%MOD;
					dp[i+1][x+k][(j+x*i%p)%p]%=MOD;
				}
			}
		}
	}
	int res=0;
	for(int i=1;i<=9;++i) {
		res+=dp[p][i][0];
		res%=MOD;
	}
	printf("%lld\n",res);
	return 0;
}