AT_sumitb2019_e Colorful Hats 2 题解

_zhx · 2023-06-13 20:44:45 · 题解

题目大意

有 N 个人站成一列，每个人都戴着一顶帽子，颜色为红、黄、绿的一种，第 i 个人前面有 a_i 个人戴着和他颜色相同的帽子。求出 N 个人帽子颜色的所有组合方案。

题目做法

其实这就是一道小学奥数题，代码上没有什么难点，主要是思路上的问题。只要把每次输入的数 x 和三个数组对比，只要一样就把 y 加一，z 变成对应数组的下标，最后把 s 和 y 相乘，把 a_z 加一，然后再把 s 和 10^9+7 取模。循环结束后，再输出 s。

题目代码

AC code

#include <bits/stdc++.h>
using namespace std;
const long long N=1e9+7;
long long n,s=1,a[4];
int read()
{
    int f=1,x=0;
    char c=getchar();
    while(c<'0'||c>'9')
    {
        if(c=='-')f=-f;
        c=getchar();
    }
    while(c>='0'&&c<='9')
     {
        x=x*10+c-'0';
        c=getchar();
    }
    return f*x;
}
int main()
{
    n=read();
    for(long long i=1;i<=n;i++)
    {
        long long x,y=0,z=0;
        x=read();
        if(x==a[0]) y++,z=0;
        if(x==a[1]) y++,z=1;
        if(x==a[2]) y++,z=2;
        s*=y;s=s%N;a[z]++;
    }
    cout<<s<<'\n';
    return 0;
}