C.照看小猫(乘法原理)

小猫(乘法原理)"/>

C.照看小猫(乘法原理)

C.照看小猫(乘法原理)

前言

菜死了，差这个一个题就AK了，卡了一个小时，然后溜了，后来看题解发现是个大水题。

思路

预处理一波长度 ≤ i \le i ≤i的名字数 p r e [ i ] pre[i] pre[i]，然后对这个 n n n的进行从小到大排，第 a [ i ] a[i] a[i]个可选择的字符串数就是 p r e [ a [ i ] − ( i − 1 ) pre[a[i]-(i-1) pre[a[i]−(i−1)个，如果 p r e [ a [ i ] − ( i − 1 ) ≤ 0 pre[a[i]-(i-1)\le 0 pre[a[i]−(i−1)≤0则说明不存在方案。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e4+5,M=2e4+5,inf=0x3f3f3f3f,mod=77797;
#define mst(a,b) memset(a,b,sizeof a)
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
int n,a[N];
ll pre[N];
int main(){pre[0]=1;for(int i=1;i<=10;i++) pre[i]=pre[i-1]*26%mod;for(int i=2;i<=10;i++) pre[i]=(pre[i]+pre[i-1])%mod;scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&a[i]);sort(a+1,a+n+1);ll s=1,x=0;for(int i=1;i<=n;i++){x=pre[a[i]]-(i-1);if(x<=0) return puts("-1"),0;s=s*x%mod;}printf("%lld\n",s);return 0;
}