照看小猫

nowcoder 217602

题目大意

有n只小猫，对于第i只小猫，给它取一个以小写字母组成的名字（长度不大于），问你使所有小猫名字不同的方案数

解题思路

对于第k只小猫，名字有j位的方案数是
那么方案总数为：
对于，第j只小猫选的名字不一定在当前小猫的方案总数中
而对于，第j只小猫选的名字一定在当前小猫的方案总数中
所以可以按a从小到大排序
当计算第i只小猫的方案总数时，减去a值比i小的个数
因为这些猫选的方案已定会使i的方案总数-1
计算完所有小猫的种数后，乘在一起即可

代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define wyc 77797
using namespace std;
ll n, g, ans, a[10010], pw[15];
int main()
{
    scanf("%lld", &n);
    for (int i = 1; i <= n; ++i)
        scanf("%lld", &a[i]);
    sort(a + 1, a + 1 + n);//排序
    pw[1] = 26;
    for (int i = 2; i <= 10; ++i)
    {
        pw[i] = pw[i - 1] * 26;//预处理总方案数
        pw[i - 1] += pw[i - 2];
    }
    pw[10] += pw[9];
    ans = 1;
    for (int i = 1; i <= n; ++i)
    {
        g = pw[a[i]] - i + 1;//减去冲突的
        if (g < 0)//方案数小于0，说明没有可行的方案
        {
            printf("-1");
            return 0;
        }
        g %= wyc;
        ans = ans * g % wyc;
    }
    printf("%lld", ans);
    return 0;
}