照看小貓

nowcoder 217602

題目大意

有n只小貓，對于第i只小貓，給它取一個以小寫字母組成的名字（長度不大于$a_i$），問你使所有小貓名字不同的方案數

樣例#1

輸入樣例#1

1 1

輸出樣例#1

26

樣例解釋#1

貓咪的名字可以為 a-z 間的任意一個字母，所以方案數為 26。

樣例#2

輸入樣例#2

1 2

輸出樣例#2

702

樣例解釋#2

貓咪的名字的長度可以為 1，也可以為 2。
長度為 1 時，名字可以為 a-z 中任意一個，方案數 26 種。
長度為 2 時，名字可以為 aa-az, ba-bz ，…，za-zz 中任意一個，方案數 26×26=676種。
所以總方案數為 26+676=702 種。

樣例#3

輸入樣例#3

5 7 5 8 4 3

輸出樣例#3

9416

數據范圍

$1?N?10^4,q?10$

解題思路

對于第k只小貓，名字有j位的方案數是$26^k$
那么方案總數為：${\sum }_{k=1}^{a_i}26^k$
對于$a_j>a_i$，第j只小貓選的名字不一定在當前小貓的方案總數中
而對于$a_j<a_i$，第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; } 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的照看小猫（nowcoder 217602）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。