2014-07-29

UVa 11828 - Palindrome Again

1. Problem
2. Input
3. Output
4. Sample Input
5. Output for Sample Input
6. Solution

Problem

You are given a string S of length N. Can you find a string P which satisfies the following conditions?

Length of P will be N
Distance between S and P will be less than or equal to K
P will be a palindrome.
P can contain only characters ‘a’, ‘b’, …, ‘z’

You have to calculate, in how many ways you can choose P. This number can be very large, so print the answer modulo 1000000000 (109).

Notes:

A string is a sequence of characters. For this problem consider that all strings can contain only ‘a’, ‘b’, …, ‘z’, i.e. 26 available characters.
The length of the string is defined by the number of characters in the string. For example, length of “abcba” is 5.
A string is called palindrome when it is the same string when written from forwards or backwards. For example – “abcba”, “abba”, “a” are palindrome but “abc” is not a palindrome.
Distance between two string of same length is the number of mismatches of corresponding characters. For example, distance between “abcb” and “bcba” is 4 because no character of first string matches to the character of the corresponding index of second string, but distance between “abc” and “cba” is 2.

Input

Input starts with an integer T (T is around 5000), the number of test cases.

Each test case consists of two lines. First line contains two integers N(1≤N≤1000) and K (0≤K≤1000). Second line contains a string S of length N. S contains only characters from ‘a’, ‘b’, …, ‘z’.

Output

For each test case output the number of test cases followed by the number of ways the string can be chosen modulo 1000000000 (109). See sample output for exact format.

Sample Input

3
3 2
kxk
4 1
addc
4 3
addc

Output for Sample Input

1
2
3

Case 1: 51
Case 2: 2
Case 3: 76

Solution

題目描述：

對一個 S 字串，修改最多 K 個字符的情況下，求最多有多少不同的字符串是迴文

題目解法：

最樸素的算法，對於每個字串 S，使用 O(NK) 的算法，利用 dp[N][K] 表示對於前綴長為 N，已經修改了 K 個字符的總數為何。

先來看最樸素的寫法，一定會拿 TLE，原因是詢問的次數過多。

// TLE
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <ctype.h>
using namespace std;
int main() {
    int testcase, cases = 0, N, K;
    char s[1024];
    long long dp[2][1024];
    long long mod = 1000000000LL;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d %d %s", &N, &K, s);
        memset(dp, 0, sizeof(dp));
        dp[0][0] = 1;
        int froll = 0, L = N/2 + N%2;
        for(int i = 0; i < N; i++)
            s[i] = tolower(s[i]);
        for(int i = 0; i < L; i++) {
            memset(dp[!froll], 0, sizeof(dp[!froll]));
            int diff, cos;
            diff = s[i] == s[N - i - 1] ? 0 : 1;
            cos = i == N - i - 1 ? 1 : 2;
            for(int j = 0; j <= K; j++) {
                if(diff) {
                    dp[!froll][j + 2] += dp[froll][j] * 24;
                    dp[!froll][j + 1] += dp[froll][j] * 2;
                } else {
                    dp[!froll][j + cos] += dp[froll][j] * 25; // using diff
                    dp[!froll][j] += dp[froll][j];
                }
                dp[!froll][j] %= mod;
            }
            froll = !froll;
        }
        long long ret = 0;
        for(int i = 0; i <= K; i++)
            ret = (ret + dp[froll][i])%mod;
        printf("Case %d: %lld\n", ++cases, ret);
    }
    return 0;
}

之後，仔細拆解之後，發現由於只會考慮字串的一半，並且條件分為兩種，原本就已經匹配還是沒有匹配，而事實上我們可以分成 P, Q 兩種形式。

P = number of characters where a[i] = a[n-i-1];
Q = number of characters where a[i] != a[n-i-1];

所以考慮預先建表，將這兩個事件獨立分開計算，最後乘積起來就可以了。

對於 P, Q 的情況，分別建立 dp(i, j) 為目前 i 個字符，恰好修改 j 次的迴文字串數量。但是題目要求為 最多修改 K 次，因此對 P, Q 其中一種進行調整為 dp(i, j) 為目前 i 個字符，修改最多 j 次的回文字串數量。

因此對於每次詢問，可以在 O(N) 時間內完成。

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <ctype.h>
using namespace std;
long long dp1[1024][1024], dp2[1024][1024];
long long mod = 1000000000LL;
/*
P= number of characters where a[i] = a[n-i-1];
Q= number of characters where a[i] != a[n-i-1];
*/
long long solve(int P, int Q, int K) {
    long long ret = 0;
    for(int i = 0; i <= K; i++)
        ret = (ret + dp1[P][i] * dp2[Q][K - i])%mod;
    return ret;
}
int main() {
    dp1[0][0] = dp2[0][0] = 1;
    // dp1(P, K), dp2(Q, K)
    for(int i = 1; i < 1024; i++) {
        for(int j = 0; j < 1024; j++) {
            if(j >= 2)
                dp1[i][j] += dp1[i - 1][j - 2] * 25;
            dp1[i][j] += dp1[i - 1][j];
            if(j >= 1)
                dp2[i][j] += dp2[i - 1][j - 1] * 2;
            if(j >= 2)
                dp2[i][j] += dp2[i - 1][j - 2] * 24;
            dp1[i][j] %= mod, dp2[i][j] %= mod;
        }
    }
    // 
    for(int i = 0; i < 1024; i++) {
        for(int j = 1; j < 1024; j++)
            dp2[i][j] = (dp2[i][j] + dp2[i][j-1])%mod;
    }
    
    int testcase, cases = 0, N, K;
    char s[1024];
    
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d %d %s", &N, &K, s);
        int P = 0, Q = 0;
        for(int i = 0; i < N/2; i++) {
            P += s[i] == s[N - i - 1];
            Q += s[i] != s[N - i - 1];
        }
        long long ret = 0;
        if(N&1)
            ret = (solve(P, Q, K) + solve(P, Q, K - 1) * 25) %mod;
        else
            ret = solve(P, Q, K);
        printf("Case %d: %lld\n", ++cases, ret);
    }
    return 0;
}

Morris' Blog