【Foreign】字串变化 [DP]
字串变化
Time Limit: 10 Sec Memory Limit: 128 MB
Description
定义一个(大写字母)字符串集合{S},初始时值包含一个给定的字符串S1,每次从中任意取出一个字符串,将它变换后再放入集合中。要求新的字符串在集合中没有出现过。
变换的规则:在变化前、后,字符串均有大写字母组成,每次只改动一个位置,使它的ASCLL加1。例如:‘A’ –> ‘B’。如果位置为‘Z’,则无法改动。
若干次操作后,该集合的元素个数一定会达到最大。
对最后的集合(已按字典序排列)中的Si(i >1),定义Sj=P[Si](Si由Sj变化而来)。
求最大元素个数及{P}的方案数。(详情见样例。)
Input
第1行有1个由大写字母组成的字符串。
Output
输出2行,每行包含一个数,第一行表示最大元素个数,第二行表示方案数,答案都模10007。
Sample Input
XYZ
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
初始字符串长度<=1000.
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
#include<iostream>
#include<string>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<bitset>
using namespace std;
typedef long long s64; const int ONE = ;
const int MOD = ; int n;
int a[ONE];
char ch[ONE];
int f[ONE][ONE];
int Ans; int get()
{
int res=,Q=;char c;
while( (c=getchar())< || c> )
if(c=='-')Q=-;
res=c-;
while( (c=getchar())>= && c<= )
res=res*+c-;
return res*Q;
} int Quickpow(int a, int b)
{
int res = ;
while(b)
{
if(b & ) res = (s64)res * a % MOD;
a = (s64)a * a % MOD;
b >>= ;
}
return res;
} int main()
{
scanf("%s", ch + );
n = strlen(ch + ); for(int i=; i<=n; i++)
a[i] = 'Z' - ch[i]; Ans = ;
for(int i=; i<=n; i++)
Ans = (s64)Ans * (a[i]+) % MOD;
printf("%d\n", Ans); Ans = ; f[][] = ;
for(int i=; i<=n; i++)
{
f[i][] = ;
for(int j=; j<=i; j++)
f[i][j] = (f[i-][j] + f[i-][j-] * a[i] % (MOD - )) % (MOD - );
} for(int k=; k<=n; k++)
Ans = (s64)Ans * Quickpow(k, f[n][k]) % MOD; printf("%d", Ans);
}
最新文章
- eCharts动态加载各省份的数据
- php每天一题:strlen()与mb_strlen()的作用分别是什么
- TypeScript Interface(接口)
- org.openqa.selenium.StaleElementReferenceException
- linux pidof
- BZOJ3476 : [Usaco2014 Mar]The Lazy Cow
- ZOJ-3720 Magnet Darts 计算几何,概率
- 举例说,Linux核心名单(两)
- 白帽子之路首章:Footprinting, TARGET ACQUISITION
- 【框架学习与探究之AOP--Castle DynamicProxy】
- Validator验证框架
- shell 不使用循环批量创建用户
- P Invoke struct结构
- 修改CKplayer.js 源码解决移动端浏览器全屏不能限制快进的问题
- 20165305 实验三 敏捷开发与XP实践
- Oracle性能优化3-sql优化一定要等价
- HGOI 20181030晚 题解
- Linux:安装mysql
- SVN —— 如何设置代理
- Flask 的馈赠
热门文章
- CSS基础小记
- JavaWeb基础 - 会话
- 数论的欧拉定理证明 &;amp; 欧拉函数公式(转载)
- (转)Linux NUMA引发的性能问题
- Linux下安装MySQL管理工具MySQL Administrator和MySQL Query Browser(转载)
- 浅述Try {} Catch{} 作用
- Python数据定义
- hdu 1851(A Simple Game)(sg博弈)
- [JSOI2010]缓存交换 贪心 &; 堆
- Android <;Android应用开发实战>; 资源类型<;一>;