CF156C Cipher 题解

源码


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
># CF156C Cipher 题解
>题意  把 $sum$ 分解成长度为 $n$ 的自然数数列 $a$ ,且 $ \forall i\in[1,n], a_i \leq s=25$ ,求方案数
>
>$(T\leq 10^4,sum\leq 2.5×10^3,n\leq 100)$

$\ $

**sol1**

看起来很像一个计数题

于是有人想到了dp

dp就要设计状态,目前题目中直接出现了[sum,s,n,方案] 四个变量

可以理论推测一下,数组值表示方案,一维可以枚举,状态起码要两维,转移的时间复杂度是三维,预计的时间复杂度是$O(T*s*n*sum)$,原地起飞。

可以发现所有询问的形式一模一样,且s,n,sum难以从时间复杂度中舍去,所以可以预处理,询问时直接回答,把T给舍去。

```cpp
rep(i,0,25) dp[1][i]=1;
rep(i,2,N-1) rep(sum,0,25ll*i) rep(j,0,min(25ll,sum))
  add(dp[i][sum],dp[i-1][sum-j]);
while(t--){
    int n,sum=0;
    cin>>(s+1);
    n=strlen(s+1);
    rep(i,1,n) sum+=s[i]-'a';
    printf("%lld\n",dp[n][sum]-1);
}
```
可以通过本题

**sol2**

在初中的时候数学有一个简单的计数技巧:隔板法

把 $sum$ 分解成 $n$ 个正整数的方案为
$\dbinom{sum-1}{n-1}$

在一个上面那个计数题上有了 $a_i\leq s$ 的限制,可以采用容斥的想法

所以答案也可以用以下式子求出

$$
\sum_{i=0}^n (-1)^i \dbinom{n}{i} \dbinom{sum-26*i-1}{n-1}
$$