Atcoder S M T B Programming Contest 2019 E Colorful Hats 2 组合数学

以为这场会很简单...害，只是我以为而已，榜一15分钟AK？？太强了吧。。

首先看一下题意： 

给你一组序列，这组序列Ai表示 在位置i之前有多少个 和Ai的颜色相同，问有多少种组合方法。

题目思路：

暴力找到了规律...原来是组合数学...

首先可以推出 几个性质 

1.每个数最多出现三次，因为只有三种颜色。

2.每个数x的状态必须要与数x-1的颜色相同。

所以说：

0 1

这个样例就是 :因为 0可能会出现3种颜色，那么随之而来的1跟随三种颜色3*1

0 0 1

这个样例：0 0 会有6种选择，而1可以选择与其任何一种颜色相同,所以3 * 2 *2

当前这个数x只与在这之前x-1出现了多少次有关系

0 0 1 2

1*3*2*2*1

因为2的颜色只能1出现过的颜色...这个好懂叭。

然后发现这样还不对...

具体是：0 0 1 1

1 * 3 * 2 *2 *1 最后一个就是 *1 了 因为，前面出现过一个1了，这个颜色就减少了一种选择，因为这个1与前面哪个1颜色相同的话，这个1就不可能是1，应该是2....

所以就可以得到答案，假设当前数为x:

ans*=（在此之前(x-1)出现的次数）- （在此之前 x 出现的次数 )

此时 问题也来了 需要特判一下0

0第一次出现有3种选择

0第二次出现有2种选择

所以再接一遍for：

AC

#pragma GCC optimize(2)
#include<bits/stdc++.h>
typedef long long ll;
const int maxn=1e6+5;
const ll mod=1000000007;
using namespace std;
ll n,m;
ll num[maxn];
ll pos[maxn];//记录num[i] 出现的次数
ll dp[maxn];
int main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
        scanf("%lld",&num[i]);
    ll ans=1;
    ll zero=3;
    for(int i=1;i<=n;i++)
    {
        if(num[i]==0)
        {
            ans*=zero;
            zero--;
        }
        else
            ans=(ans%mod*(pos[num[i]-1]-pos[num[i]])%mod)%mod;
        pos[num[i]]++;
    }
    printf("%lld\n",ans%mod);
    return 0;
}

/**

**/