NOIP模拟赛three(3)

题目描述 Description###

很久很久以前，有两个长度为 $n$ 的排列 $a$ 和 $b$ 以及一个长度为 $n$ 的由 $1$ 和$2$ 组成的序列 c。对于 $1<=i<=n$，$a_i-b_i<=c_i$。

在岁月中这两个排列早已遗落，只留下了序列 $c$ 。现在你想要知道满足 $a_i-b_i<=c_i$ 的方案数，$a$ 或 $b$ 某一对应位不同即算不同方案。

由于答案较大，你需要 $mod 666623333$ 输出。

输入描述 Input Description###

第一行一个整数 $n$ 。

第二行 $n$ 个 $1$ 或 $2$ 的整数，表示 $c$ 序列。

输出描述 Output Description###

一个整数，满足条件的方案数 $mod 666623333$ 。

样例输入 Sample Input###

4

2 1 2 1

样例输出 Sample Output###

数据范围及提示 Data Size & Hint###

对于 20%的数据，$n<=6$ 。

对于 40%的数据，$n<=10$ 。

对于另外 10%的数据，c 全为 1。

对于另外 20%的数据，c 全为 2。

对于 80%的数据，$n<=100$ 。

对于 100%的数据，$1<=n<=2000$ 。

之前的一些废话###

题解###

首先我们可以发现$C$ 数组中$1，2$ 的顺序并不重要，重要的是$1,2$ 的个数。然后由于$A,B$ 两个都是属于$1-n$ 的序列，由于$C$ 数组是针对每一个$A$ ,$B $ 数的，所以我们不妨定一看一，固定$A$ 数组来看$B$ 数组的填法。假设$A$ 数组是从1到n，然后我们考虑依次往里填数。设$dp[i][j]$ 表示已经用了$i$ 个$1$ ，$j$ 个$2$ 的方案数，由于我们是从左到右依次处理的，所以到当前位置，所有B数组的上限已经小于等于当前的数，可以证明：$A_{i-1}=i-1,B_{i-1}=i$ 或$i+1$ ,而$A_i=i,B_i=i+1$ 或$i+2$，证明了$B_i \geq B_{i-1}$ ,证明完了这个我们就可以有序的填入B数组了，转移方程为

$dp[i+1][j]=dp[i+1][j]+dp[i][j]*(min(n,i+j+2)-i-j),
dp[i][j+1]=dp[i][j+1]+dp[i][j]*(min(n,i+j+3)-i-j))$ ，

注意最后答案要乘以$cnt[1]!*cnt[2]!$

代码###

#include<iostream>

#include<cmath>

#include<algorithm>

#include<cstdio>

#include<queue>

#include<cstring>

using namespace std;

typedef long long LL;

inline int read()

{

    int x=0,f=1;char c=getchar();

    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}

    while(isdigit(c)){x=x*10+c-'0';c=getchar();}

    return x*f;

}

const int maxn=2010,MOD=666623333;

int n,cnt[2],dp[maxn][maxn],fac[maxn];

int main()

{

    n=read();fac[0]=1;

    for(int i=1;i<=n;i++)cnt[read()-1]++;

    for(int i=1;i<=n;i++)fac[i]=((LL)fac[i-1]*(LL)i)%MOD;

    dp[0][0]=1;

    for(int i=0;i<=cnt[0];i++)

        for(int j=0;j<=cnt[1];j++)

        {

            dp[i+1][j]=(dp[i+1][j]+((LL)dp[i][j]*(LL)(min(n,i+j+2)-i-j))%MOD)%MOD;

            dp[i][j+1]=(dp[i][j+1]+((LL)dp[i][j]*(LL)(min(n,i+j+3)-i-j))%MOD)%MOD;

        }

    int t=((LL)fac[cnt[0]]*(LL)fac[cnt[1]])%MOD;

    printf("%d\n",((LL)dp[cnt[0]][cnt[1]]*(LL)t)%MOD);

    return 0;

}

总结###

像这种排列问题明显就是$DP$ ，但是关键在于有序的填数进去才能进行正常的$DP$ ，而且定一看一的思想也是非常重要的。

巴特西