首页 > ACM题库 > HDU-杭电 > HDU 3658-How many words-动态规划-[解题报告]HOJ
2014
11-30

HDU 3658-How many words-动态规划-[解题报告]HOJ

How many words

问题描述 :

In order to make a new word, we will pick out m letters from all the upper case letters and lower case letters(from `a’ to `Z’). Therefore, that means you can pick some same letters. But here are two rules:
● as to all the neighbour letters, the absolute value of their ASCII code must be not greater than 32.
● there must be at least one pair of neighbour letters whose absolute value of ASCII code is exactly equal to 32. For example, considering the word in the form like "Xx" or "xX", the neighbour letters have an absolute value of ASCII code exactly equal to 32.
Now how many di erent words can we get?

输入:

The first line of input is the number of test case. For each test case, there is only one line contains one integer m(2 ≤ m ≤ 109).

输出:

The first line of input is the number of test case. For each test case, there is only one line contains one integer m(2 ≤ m ≤ 109).

样例输入:

4
2
3
100
7926778

样例输出:

52
4056
533550434
773908369

题意:给定一个整数n(2<=n<=10^9),求符合以下规则的字符串有多少种?

规则如下:1)字符串长度为n,且字符由大写字母和小写字母组成

2)任意两个相邻字符,在ASCII表中的差值不大于32

3)至少存在一对相邻字符,其在ASCII表中的差值正好等于32

题解:

这道题需要先dp,定义f[i][j]为长度为i,结尾为j的符合(1)条件的字符串个数。g[i][j]同理,符合(2)条件。其中j是大小写字母转换的0~51数字。

(1)条件:不存在题意中的3)条件,其余题意条件相同

(2)条件:任意两个相邻字符,在ASCII表中的差值小于32,其余与(1)条件相同

这样结果就可以转换成ans=∑(f[n][j]-g[n][j])

dp方法:f[i][j]=f[i-1][j]*(与j差值小于等于32的字符的个数),g[i][j]=g[i-1][j]*(与j差值小于32的字符的个数).

由于n值过大,不能直接dp,需要用矩阵连乘来加速。

得到公式:|dp[i][j]|*|matrxi[][]|=|dp[i+1][j]|,其中matrix[a][b](0<=a<52,0<=b<52)在字符a和b差值小于等于32时值为1,其余为0(对于f[i][j]而言,对于g[i][j]就是小于32)。

代码:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
using namespace std;
#define LL __int64
const int mod=1000000007;
struct matrix{
    LL f[52][52];
};
matrix mul(matrix a,matrix b)//矩阵乘法
{
    int i,j,k;
    matrix c;
    memset(c.f,0,sizeof(c.f));
    for(i=0;i<52;i++)
    {
        for(j=0;j<52;j++)
        {
            for(k=0;k<52;k++)
            {
                c.f[i][j]+=a.f[i][k]*b.f[k][j]%mod;
            }
            c.f[i][j]%=mod;
        }
    }
    return c;
}
matrix pow_mod(matrix a,int b)//矩阵连乘
{
    matrix s;
    int i,j;
    memset(s.f,0,sizeof(s.f));
    for(i=0;i<52;i++)
        s.f[i][i]=1;
    while(b)
    {
        if(b&1)
            s=mul(s,a);
        a=mul(a,a);
        b=b>>1;
    }
    return s;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int i,j,k,n,a[100];
        scanf("%d",&n);
        for(i=0;i<26;i++)
        {
            a[i]=i;
            a[i+26]=32+i;
        }
        matrix e,ee;
        memset(e.f,0,sizeof(e.f));
        memset(ee.f,0,sizeof(ee.f));
        for(j=0;j<52;j++)
        {
            for(i=0;i<52;i++)
            {
                if(abs(a[j]-a[i])<32)e.f[i][j]=1;//任意两个连续字母差小于32的种数
                if(abs(a[j]-a[i])<=32)ee.f[i][j]=1;//任意两个连续字母差小于等于32的种数
            }
        }
        e=pow_mod(e,n-1);
        ee=pow_mod(ee,n-1);
        LL ans=0;
        for(i=0;i<52;i++)
        {
            for(j=0;j<52;j++)
            {
                ans+=ee.f[i][j]-e.f[i][j];
            }
        }

        printf("%I64d\n",(ans%mod+mod)%mod);
    }
}

How many words

参考:http://blog.csdn.net/a601025382s/article/details/37742185


  1. 我没看懂题目
    2
    5 6 -1 5 4 -7
    7 0 6 -1 1 -6 7 -5
    我觉得第一个应该是5 6 -1 5 4 输出是19 5 4
    第二个是7 0 6 -1 1 -6 7输出是14 7 7
    不知道题目例子是怎么得出来的

  2. #!/usr/bin/env python
    def cou(n):
    arr =
    i = 1
    while(i<n):
    arr.append(arr[i-1]+selfcount(i))
    i+=1
    return arr[n-1]

    def selfcount(n):
    count = 0
    while(n):
    if n%10 == 1:
    count += 1
    n /= 10
    return count

  3. 有一点问题。。后面动态规划的程序中
    int dp[n+1][W+1];
    会报错 提示表达式必须含有常量值。该怎么修改呢。。