题面
问题描述
小 H 在上体育课，这节体育课的任务是做球类运动! 这节课一共有 $n$ 位同学参加，初始时每位同学手上都拿了一个球，第 $i$ 位同 学拿了编号为 $i$ 的球。 众所周知，体育课的开始阶段是热身运动，在这时，老师可以进行一系列的操作，每次操作中，老师会指定编号为 $u,v$ 的两个同学($u\neq v$)，让这两位同 学将当前自己手上的球抛给对方，下图便是一个 $n=5$ 的例子，此时老师指定了编号为 $2,4$ 的同学互相抛球。
输入格式
第一行一个正整数 $T$，表示数据组数。
接下来一共 $T$ 组数据，每组数据第一行一个正整数 $n$，表示参与的同学数量，接下来一行 $n$ 个用空格隔开的正整数，第 $i$ 个正整数表示 $t_i$，含义如题目中所示。
输出格式
对每组数据输出一行非负整数表示答案。
样例输入
3
2
1 1
5
1 2 2 1 2
8
1 2 2 1 2 1 1 2
样例输出
2
120
16800
题解
一开始拿到这个题毫无头绪，又有多个人，每个人的抛球次数还不同。
于是想到了 Camera 神仙的打表找规律方法。
先打出一个裸的暴力程序。
int n,t[11],a[11];
set<int> cnt;
inline int get(){
int res=0;
for(int i=1;i<=n;++i){
res=res*n+a[i]-1;
}
return res;
}
void dfs(int x){
cnt.insert(get());
for(int i=1;i<=n;++i){
if(i==x)continue;
if(t[i]){
t[x]--;
t[i]--;
swap(a[x],a[i]);
bool found=false;
for(int i=1;i<=n;++i){
if(t[i])dfs(i),found=1;
}
if(!found) cnt.insert(get());
swap(a[x],a[i]);
t[x]++;
t[i]++;
}
}
}
inline void solve(){
cnt.clear();
scanf("%d",&n);
for(int i=1;i<=n;++i)scanf("%d",t+i),a[i]=i;
for(int i=1;i<=n;++i)dfs(i);
printf("%d\n",(int)cnt.size());
}
然而找规律一般都是一维或二维的，我们的输入却有这么多个数据，所以要再处理一下。
可以很容易推测，其实这只和 1和2的个数有关，我们可以利用暴力程序验证这一点。
所以现在可以开始打一点表出来看看。
inline void solve(){
for(n=1;n<=6;n++){
for(int twocnt=0;twocnt<=n;++twocnt){
for(int i=1;i<=twocnt;++i)t[i]=2,a[i]=i;
for(int i=twocnt+1;i<=n;++i)t[i]=1,a[i]=i;
cnt.clear();
for(int i=1;i<=n;++i)dfs(i);
printf("%d ",(int)cnt.size());
}
puts("");
}
}
Output:
1 1
2 2 2
4 6 6 6
10 16 24 24 24
26 50 80 120 120 120
76 156 300 480 720 720 720
可以很容易看到，最后三个数据都是相同的，且为n的阶乘。一不小心就搞定了 7～8 测试点的 20pts。
那么其他数据怎么求出呢？我们尝试右对齐这些数据。
1 1
2 2 2
4 6 6 6
10 16 24 24 24
26 50 80 120 120 120
76 156 300 480 720 720 720
再次观察，发现除了每一行的第一个数据外，都符合这样的规律
\[f_{i,j} = i \times f_{i-1,j}\]所以，假设第 $i$ 行第一个数据为 $fir_i$，要求的数据中 $2$ 的个数为 $two$，那么答案可以表示为
\[ans=\left\{ \begin{aligned} & n! & (n-two \leq 2)\\ & \frac{fir_{n-two}\cdot n!}{(n-two)!} & (n-two > 2) \end{aligned} \right.\]现在我们想办法求出 $fir$ 数组。
先从题意出发，由于这波所有的人都只能抛 $1$ 次，所以我们容易得到以下式子（f_{i,j} 表示考虑前 $i$ 个人，目前还有 $j$ 个人没有抛过球的方案数）
\[f_{i,j} = f_{i-1,j-1}+f_{i-1,j+1}\times(j+1)\]所以此时
\[fir_i = \sum^i_{j=0} f_{i,j}\]这样一来，就可以得到 80pts 了，最后 20pts 就需要优化一下 $fir$ 数组的求法，这个 $\Theta (n^2)$ 的方法很显然无法通过 $5 \times 10^5$。
如何优化呢？OEIS A000085
我们发现，其实 $fir$ 数组间也有一些联系，我们可以通过其本身的定义来推出。
对于第 $i$ 个人，如果不抛球，我们可以理解为直接添加第 $i$ 个人到 $i-1$ 个人的末尾；如果抛球，可理解为与第 $i-1$ 个人抛球，我们固定前 $i-2$ 个人不动，因此第 $i-1$ 个人就有 $i$ 种可能。
\[fir_i = fir_{i-2} \times i + fir_{i-1}\]最终就可以得到 100pts 啦！
inline ll qpow(ll x,int p){
ll res=1;
while(p){
if(p&1)res=res*x%mod;
x=x*x%mod;
p>>=1;
}
return res;
}
inline ll inv(ll x){
return qpow(x,mod-2);
}
inline void pre(){
fir[1]=1;fir[2]=2;
for(int i=3;i<=500050;++i)fir[i]=(fir[i-2]*i%mod+fir[i-1])%mod;
fac[0]=1;
fac[1]=1;
for(ll i=2;i<=500050;++i){
fac[i]=fac[i-1]*i%mod;
invfac[i]=inv(fac[i]);
}
}
inline void getans(int x,int y){
if(x-y<3){
IO::putln(fac[x]);
return;
}
int pos=x-y;
IO::putln(fir[pos]*fac[x]%mod*invfac[pos]%mod);
}
int n,c2;
inline void solve(){
IO::read(n);
c2=0;
for(int i=1,tmp;i<=n;++i){
IO::read(tmp);
if(tmp==2)++c2;
}
getans(n,c2);
}