【Foreign】字串变化 [DP]-布布扣-bubuko.com

Description

　　定义一个（大写字母）字符串集合{S},初始时值包含一个给定的字符串S1，每次从中任意取出一个字符串，将它变换后再放入集合中。要求新的字符串在集合中没有出现过。
　　变换的规则：在变化前、后，字符串均有大写字母组成，每次只改动一个位置，使它的ASCLL加1。例如：‘A’ –> ‘B’。如果位置为‘Z’，则无法改动。
若干次操作后，该集合的元素个数一定会达到最大。
　　对最后的集合（已按字典序排列）中的Si（i >1），定义Sj=P[Si]（Si由Sj变化而来）。
　　求最大元素个数及{P}的方案数。（详情见样例。）

Input

Output

　　输出2行，每行包含一个数，第一行表示最大元素个数，第二行表示方案数，答案都模10007。

Sample Input

Sample Output

　　6
　　4

　　explain：
　　最终集合为{XYZ,XZZ,YYZ,YZZ,ZYZ,ZZZ}
　　{P}方案有{0,1,1,2,3,4},{0,1,1,3,3,4},{0,1,1,2,3,5},{0,1,1,3,3,5}

HINT

Solution

　　第一问乘一下就好了，这里讨论一下第二问。
　　用‘Z‘-ai得到一个数字串，那么操作就变成了：每次将一个数字-1，最后全部减成0。比如‘XYZ‘，我们将其变成‘012‘。
　　然后考虑状态是怎么变来的：
　　显然，有几位是不满的，就有几种转移来的方法（其中任意一位数字+1，即可得到一种父状态）。
　　记一个状态可以由k个状态转移过来，然后答案显然就是：πk。
　　我们考虑，
　　我们得到一个长度为n的01串vis，如果这一位是1表示这一位不满。
　　那么这个01串对答案的贡献就是：k ^ (π [vis_i=1]*a_i)。（k表示1的个数）
　　为什么呢？对于一个位置，当这一位是[0,ai-1]都是不满的，个数就是ai。
　　然后这样枚举每一位是否满，可以做到O(2^n)。
　　我们考虑优化：
　　把k相同的放在一起计算，记贡献为k^num[k]。num[k]即是各种1的个数为k情况的指数之和。
　　num怎么得到呢？
　　用f[i][j]表示到了第i位，有j个数不满的方案数，显然可以得到这样的递推式子：
　　f[i][j] = f[i-1][j] + f[i-1][j-1] * (‘Z‘-a[i])
　　然后Ans = π k^f[n][k]，就解决了这题qwq。

Code

 1 #include<iostream>    
 2 #include<string>    
 3 #include<algorithm>    
 4 #include<cstdio>    
 5 #include<cstring>    
 6 #include<cstdlib>
 7 #include<cmath>
 8 #include<bitset>
 9 using namespace std;  
10 typedef long long s64;
11 
12 const int ONE = 4005;
13 const int MOD = 10007;
14 
15 int n;
16 int a[ONE];
17 char ch[ONE];
18 int f[ONE][ONE];
19 int Ans;
20 
21 int get()
22 {    
23         int res=1,Q=1;char c;    
24         while( (c=getchar())<48 || c>57 ) 
25         if(c==‘-‘)Q=-1; 
26         res=c-48;     
27         while( (c=getchar())>=48 && c<=57 )    
28         res=res*10+c-48;    
29         return res*Q;
30 }
31 
32 int Quickpow(int a, int b)
33 {
34         int res = 1;
35         while(b)
36         {
37             if(b & 1) res = (s64)res * a % MOD;
38             a = (s64)a * a % MOD;
39             b >>= 1;
40         }
41         return res;
42 }
43 
44 int main()
45 {
46         scanf("%s", ch + 1);
47         n = strlen(ch + 1);
48     
49         for(int i=1; i<=n; i++)
50             a[i] = ‘Z‘ - ch[i];
51         
52         Ans = 1;
53         for(int i=1; i<=n; i++)
54             Ans = (s64)Ans * (a[i]+1) % MOD;
55         printf("%d\n", Ans);    Ans = 1;
56         
57         f[0][0] = 1;
58         for(int i=1; i<=n; i++)
59         {
60             f[i][0] = 1;
61             for(int j=1; j<=i; j++)
62                 f[i][j] = (f[i-1][j] + f[i-1][j-1] * a[i] % (MOD - 1)) % (MOD - 1);    
63         }
64         
65         for(int k=1; k<=n; k++)
66             Ans = (s64)Ans * Quickpow(k, f[n][k]) % MOD;
67             
68         printf("%d", Ans);
69 }

View Code

原文：http://www.cnblogs.com/BearChild/p/7073578.html