福州大学第十七届程序设计大赛 1009 排列小球 题解

题目大意

有三种颜色的球各n个，排成一行，求所有相邻小球颜色各不相同的排列方式种类。

解题思路

首先用第二种小球将第一种小球分为k段，相当于在$n-1$个位置中，插入$k-1$个挡板。

分法为$\Large C_{n-1}^{k-1}$。

在将第一种分类的同时，第二种小球也会分成$k-1$段（第一个和最后一个都是第一种小球）,$k$（第一个和最后一个小球，一个是第一种，一个是第二种）,$k+1$（第一个和最后一个都是第二种）。

设第二种小球被分成t段，由第一种小球的分法知，答案为$\Large C_{n-1}^{t-1}$。

对于前面两种小球的分法，当t为$k-1$的时候，答案为$\Large C_{n-1}^{k-1}\times \Large C_{n-1}^{t-1}$，当t为$k$的时候，第一种和第二种的分配存在两种可能，答案为$\Large 2\times C_{n-1}^{k-1}\times \Large C_{n-1}^{t-1}$，同理，当t为$k+1$的时候，答案为$\Large C_{n-1}^{k-1}\times \Large C_{n-1}^{t-1}$，总结答案为$\Large(1+(t==k))\times C_{n-1}^{k-1}\times \Large C_{n-1}^{t-1}$。

把第一种小球和第二种小球混在一起，存在相邻颜色不同的位置，也存在相邻颜色相同的位置，两种小球被分为$t+k$段，颜色不同的位置为$t+k-1$个，加上第一个和最后一个位置，颜色不同的位置就是$t+k+1$个，总共$2n$个小球，有$2n+1$个位置，那么就有剩下$2n+1-t-k-1=2n-t-k$个位置是必须要填入第三种颜色的小球的，

那么剩下的$n-2n+t+k=t+k-n$个小球就可以任意填入颜色不同的位置，答案为$\Large C_{t+k+1}^{t+k-n}=C_{t+k+1}^{(t+k+1)-(t+k-n)}=C_{t+k+1}^{n+1}$。

所以答案为$\Large(1+(t==k))\times C_{n-1}^{k-1}\times \Large C_{n-1}^{t-1}\times C_{t+k+1}^{n+1}$。

枚举k从1~n，t从$k-1$到$k+1$，注意预处理阶乘和逆元。

排列数$\Large C_n^m=\frac{n!}{m!(n-m)!}$。

本来是还应该乘上不同的颜色排列$\Large A_3^3$的，但是可以理解为3n个球分成n，n，n三组，存在重复情况，需要除上$\Large 3!=A_3^3$，相当于约掉了。

（这种题太考数学了。。欺负我数学渣。。

完整代码

//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <cmath>
#include <stack>
#include <map>
#include <list>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
//#include <unordered_map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

const int N = 3e6+5,maxn = 3e6+10, mod = 998244353;
ll frac[maxn], inv[maxn];

ll c(ll a, ll b) {
	if (a > b || a < 0)	return 0;
	return frac[b] * inv[b - a] % mod * inv[a] % mod;
}

ll qpow(ll a, ll b) {
	ll ans = 1;
	while (b) {
		if (b & 1)	ans = (ans * a) % mod;
		a = (a * a) % mod, b >>= 1;
	}
	return ans;
}

void init() {
	frac[0] = 1;
	for (int i = 1; i <= N; i++) frac[i] = (i * frac[i - 1]) % mod;
	inv[N] = qpow(frac[N], mod - 2);
	for (int i = N; i >= 1; i--)	inv[i - 1] = (i * inv[i]) % mod;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
    //freopen("D:\\测试用\\in.txt", "r", stdin);
    //freopen("D:\\测试用\\out.txt", "w+", stdout);
	init();
	ll n;
	while (cin >> n) {
		ll ans = 0;
		for (ll i = 1; i <= n; i++) {
			for (ll j = i - 1; j <= i + 1; j++) {
				ans = (ans + (1 + (i == j)) * c(i - 1, n - 1) % mod * c(j - 1, n - 1) % mod * c(n + 1, i + j + 1)) % mod;
			}
		}
		cout << ans << endl;
	}
	return 0;
}