庞果英雄会-合法字符串 复杂度 O(log(n)*log(n)*log(m))(一)

合法字符串

· 有 效 期：

· 庞果网

· 2013-07-24至2014-01-25

· 难 度 等 级：

· 答 题 时 长：

· 编程语言要求：

·

· 180分钟

· C++Java C#

题目详情

用n个不同的字符（编号1 - n），组成一个字符串，有如下2点要求：

1、对于编号为i的字符，如果2 * i > n，则该字符可以作为最后一个字符，但如果该字符不是作为最后一个字符的话，则该字符后面可以接任意字符；
2、对于编号为i的字符，如果2 *i <= n，则该字符不可以作为最后一个字符，且该字符后面所紧接着的下一个字符的编号一定要 >=2 * i。

问有多少长度为M且符合条件的字符串。

例如：N = 2，M = 3。则abb,bab, bbb是符合条件的字符串，剩下的均为不符合条件的字符串。

输入：n,m (2<=n,m<=1000000000)；

输出：满足条件的字符串的个数，由于数据很大，输出该数Mod 10^9 + 7的结果。

函数头部

int validstring(int n,int m) {

}

答题说明

1、main函数可不用完成

2、对于英雄会或本题有任何反馈或意见，欢迎加入英雄会编程挑战交流QQ群：216133772，验证信息为你的CSDN昵称。

思路分析：

题目数据规模非常大，出看貌似传统的优化算法都不能用，做一次运算复杂度就是10^9 超时。然而，这只是表面的。这道题真正的难点在于模型构造和发现规律。

模型1：动态规划模型

dp[j][i]：表示以字符i (0

由此就有递推方程：

dp[j][i] =

① dp[j-1][1]+…+dp[j-1][n] (若i+i>n，即i是[1类]字符)

② dp[j-1][1]+…+dp[j-1][t] ,t+t<=I (若i+i<=n，即i是[2类]字符)

初始状态dp[1][i]=1 (0

最终结果，dp[m][n-n/2]+…dp[m][n]，真正的合法字符一定以[1类]字符结尾.

复杂度O(m*n*n) 【空间=m*n, 转移=n】

动态规划不能解决这个问题，但是是必经之路

模型2：数列递推模型

描述：通过把数列递推公式转换为矩阵来计算数列的第n项

例 f(n)=2*f(n-1)+f(n-2)，f(1)=f(0)=1

则递推公式可以转化为递推矩阵：

[f(n-2),f(n-1)] * A = [f(n-1), f(n)]，A=[0 1;1 2]

即[f(n-1), f(n)] = [f(0), f(1)]*A^(n-1)

数列递推模型把求解数列的第n项转化为求解矩阵的n次幂

结合模型1和模型2 ，可以把动态规划的递推方程转换成矩阵的形式：

[dp(m-1,1),… , dp(m-1,n-1) dp(m-1,n)] * A = [dp(m,1), …, dp(m,n-1), dp(m,n)]

A为n*n的矩阵，当n=6时，A=

0 11 1 1 1

0 00 1 1 1

0 00 0 0 1

1 11 1 1 1

1 11 1 1 1

1 11 1 1 1

模型3：快速幂模型

描述，用快速幂模型可以把求解n次幂的问题转化为求解log(n)次幂的问题

例：若要求解a^9

s= a^9 = a*(a^8) = a* (a^2)^4 //把规模为9的问题，通过一次操作转化为规模为4的问题

即，若n=2*k，则s= a^n = (a^2)^k //先把a自乘，然后求k次幂

若n=2*k+1，则s= a^n =a *a^(2*k) //先拿出一个a，转化到n为偶数的情况

伪代码如下

int fastmult(a ,n){

int ans =1;

while(n>0){

if(n is odd) ans=a*ans;

a=a*a;

n>>=1;

}

return ans;

}

快速幂的指数每次都会减半，因此算法复杂度由n缩减到log(n)

快速幂模型，求解矩阵的n次幂，同样有效。

模型4：同余定理

(A+B)% M = (A%M+ B%M ) % M

(A*B)% M = (A%M* B%M ) % M

(A- B) % M = (A%M - B%M) % M

同余的核心要素：取模不分先后

根据同余定理，结合题目的Mod 10^9 + 7，可以在计算过程中先取模，再进行加减乘运算。

规律：

接着模型2说，(其余的模型在解题过程中需领悟)

[dp(m-1,1), … , dp(m-1,n-1) dp(m-1,n)] * A =[dp(m,1), …, dp(m,n-1), dp(m,n)]

初始状态dp[1][i]=1 (0

最终结果，dp[m][n-n/2]+…dp[m][n]，真正的合法字符一定以[1类]字符结尾.

A为n*n的矩阵，当n=6时，A=

0 11 1 1 1

0 00 1 1 1

0 00 0 0 1

1 11 1 1 1

1 11 1 1 1

1 11 1 1 1

对于任意的n，矩阵A仅由0和1构成，且满足一个规律：

第1行1个0，

第2行3个0，

第3行5个0，

…

第r行2*r+1个0， 0< r <= n/2

。。。等差数列

第r行没有0， n/2 < r<=n

下面以n=6继续发现规律：

dp[1]=[1 1 1 1 1 1]

S=[0 0 0 1 1 1]^T (转置)

T= dp[m] *S, (T就是最终的求解目标)

T= dp[1]*A^(m-1)*S

其中dp[1]是矩阵A的第n行，S是矩阵A的第1列

因此T=AA(n,1)，(第n行第1列)，其中 AA=A^(m+1)【重要规律】

以下重点目标是发现矩阵A^m的规律，重点关注第一列

令 f(m)表示矩阵A^m的第一列，

f(m,i)表示矩阵A^m的第i行的第一个元素 【f(m+1,n)为目标】

则

[1]. f(m,i)=f(m-1,2*i) +f(m-1,2*i+1)+…+f(m-1,n) (0< i <= n/2)

[2]. f(m,i)=f(m,n) (n/2 < i <=n)

[3]. f(m,n)=f(m,1)+f(m-1,1)

根据以上三个递推公式，尝试构造f(m,n)的递推公式，即构造

f(m,n) = f(m-1,n)*k1 + f(m-2,n)*k2+ … + f(m-r,n)*kr

其中递推长度是r，且规模上r=log(n)

如果找到了这r个系数，那么求解f(m,n)就可以转换到数列递推模型和快速幂模型，从而解决该问题。求解这r个系数是此问题的核心问题。

核心：r个系数的求解

根据公式[1].和公式[2]. 合并相同的项

a) f(m,i)=f(m-1,2*i) +f(m-1,2*i+1)+…+f(m-1,n/2)+(n-n/2)*f(m-1,n) (0< i <= n/4)

b) f(m,i)= (n-2*i)*f(m-1,n) (n/4< i<= n/2)

[边界为概数]

对于a)类情况，f(m,i)对递推项f(m-1,n)的系数有贡献，对f(m-r,n)也有贡献(r>1)

对于b)类情况，f(m,i)只对递推项f(m-1,n)的系数有贡献

引入贡献向量，和贡献递推矩阵，以n=22为例：

贡献矩阵意义

第一行[20 114 80 11] 表示：

f(m,1)= f(m-1,n)*11+ f(m-2,n)*80+ f(m-3,n)*114+f(m-4,n)*20

第二行[20 58 11] 表示：

f(m,2)= f(m-1,n)*1