hihocoder 1579(排列组合)

题意

　　给出一个长度为n的字符串的sa数组，n<=1e5，问有多少种不同的字符串的sa数组正好是输入的sa数组（字符串每个位置都是小写字母）

分析

　　sa数组描述的是字符的大小关系，而不是确切的字符，所以我们考虑位置的逻辑关系

　　首先一定有$s[sa[i-1]]<=s[sa[i]]$

　　但是对于那些$rank[sa[i-1]+1]>rank[sa[i]+1]$的位置，必须有$s[sa[i-1]]<s[sa[i]]$

　　于是我们就知道输入的位置彼此间的大小关系，要么是<=，要么是<

　　问题就是求方案数了

　　设第一个数是$x_1$，以后每个数比前面数多加$x_i$，小于号位置的$x_i>=1$，小于等于号位置的$x_i>=0$，不妨设小于等于号有m个

　　那么利用隔板法有$x_1+x_2+...+x_n<=26+m$

　　但是这个不是等号，是小于等于号，我们要把它变成等于号

　　做法就是再补一个$x_(n+1)$，把不等号变成等号

　　最后的结果就是$C_{26+m}^n$

巴特西