CF316D2 PE Lesson

· · 题解

题意描述

翻译的有些歧义......

给定 n 个人，每个人有一个球，每个人的球互不相同，每个人可以交换 a_i 次球（也可以不交换），求最终球的排列方案数。

做法思路

首先，将两个人交换不会影响最终的答案。故将所有只能交换一次的全部放到最左边不会影响答案。设其共有 cnt 人。

首先考虑 cnt=n 的情况，即每个人只能交换一次的情况。

每个人的交换有两种可能：

  1. 不交换（自己和自己交换）
  2. 和之前的一个人交换。

放到式子上来，设 f_n 表示有 n 个人，每个人都只能交换一次的方案数。不难得到递推公式为

f_n=f_{n-1}+f_{n-2}\times (n-1)

考虑加上 cnt\not= n 的情况。

由于可以交换两次的人不好处理，考虑让他们先交换。

那么第一个人可以与 n 个人交换（包括不换），第二个人可以与 n-1 个人交换（去除的一种是和第一个人做一个区分，因为这两个交换方式最终的结果是相同的），第 i 个人可以和 n-i+1 个人交换。

考虑这样交换后还有多少个人能交换。

通过统计贡献的方式可以轻松得到：

原来共可以交换 (n-cnt)\times 2+cnt 次，现在 n-cnt 个人交换了 (n-cnt)\times 2 次，还剩下 (n-cnt)\times 2+cnt-(n-cnt)\times 2=cnt 次。

那么可以轻松得到答案为

ans=f_{cnt}\times (\prod_{i=n-cnt+1}^n i)=f_{cnt}\times \frac{n!}{(n-cnt+1)!}

代码实现

代码就非常简单了......

#include<bits/stdc++.h>
using namespace std;
template<typename T>inline void read(T &x){
    x=0;
    char ch=getchar();
    bool fl=0;
    while(ch<'0'||ch>'9') fl=(fl||ch=='-'),ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+(ch^'0'),ch=getchar();
    x=fl?-x:x;
}
template<typename T>void prt(T x){
    if(x>9) prt(x/10);
    putchar(x%10+'0');
}
template<typename T>inline void put(char ch,T x){
    if(x<0) putchar('-'),x=-x;
    prt(x);
    putchar(ch);
}
inline void putstr(string s){
    for(int i=0;i<(int)s.length();i++) putchar(s[i]);
}
#define mod 1000000007
int n,s,f[2],ans;
inline int add(int a,int b){
    if(a+b>=mod) return a+b-mod;
    return a+b;
}
inline int mul(int a,int b){
    return (long long)a*b%mod;
}
int main(){
    read(n);
    for(int i=1,x;i<=n;i++) read(x),s+=x==1;
    f[0]=f[1]=1;
    for(int i=2;i<=s;i++)
        f[i&1]=add(mul(f[i&1],i-1),f[(i&1)^1]);
    ans=f[s&1];
    for(int i=n;i>s;i--) ans=mul(ans,i);
    put('\n',ans);
    return 0;
}