jzoj4673. 【NOIP2016提高A组模拟7.20】LCS again

时间:2022-09-10 08:18:50

Description

现在有一个长度为n的串S,其中每一个字母都是前m个小写字母
计算有多少个不同的长度为n的T(其中T也是由前m个小写字母组成),并且S与T的LCS为n-1
LCS就是同时存在于S和T的最长子序列

Input

第一行包含两个整数n和m表示S的长度和前m个小写字母
第二行是串S

Output

只要输出存在的T的数量

Sample Input

输入1:
3 3
aaa

输入2:
3 3
aab

输入3:
1 2
a

输入4:
10 9
abacadefgh

Sample Output

输出1:
6

输出2:
11

输出3:
1

输出3:
789

样例解释
第一个样例有6个可能的串T:aab,aac,aba,aca,baa,caa
第二个样例有11个可能的串T
Aaa,aac,aba,abb,abc,aca,acb,baa,bab,caa,cab
第三个样例只有b

Data Constraint

对于20%,n<=100
对于30%,n<=1000
对于40%,n<=10000
对于100%,n<=100000

题解

这题之前偷懒,不想打dp(不会),于是用了一个全新的方法(很简单)来做。
结果理解上一直出锅。

题解也写得有很多漏洞,于是在众大佬的帮助下成功找到一种理解方法:
第一步
我们要使新的串的lcs与原串相差1
那么我们考虑在原串中动手脚。
举个例子:
aaabacc
我们考虑把其中一个取出,再插入原串任意位置,然后改变字母,这样就可能得到一个合法的新串。
但是我们发现,取出第一个a与第二个a再放回是完全一样的。
那么意味着我们对于一段连续的字母,只能取出一个字母再放回。
那么就可以分分块:
|aaa|b|a|cc|
一共有4块。
考虑把第一块中取出一个a插入任意位置,并且更替位置:
假设放在b右边
变成aab"a"acc
然后把a变成不同的:aab"a"acc\aab"b"acc\aab"c"acc
显然有m种。
但是会有重复!
我们把a放在b的左边:aa"a"bcc\aa"b"bcc\aa"c"bcc
我们惊奇地发现,其中是有重复的情况的!
多画画就可以找到情况——对于每次插入,改变字母不能和左边的相同。
那么就可以有m-1种方案。
然而放在最开头时,可以放m种。
怎么办?但是我们发现,如果放在原来的块的最左边,(比如:"a"aabacc、aaaba"c"c)这样虽然与左边的不同,但是也是不符合的。
所以加起来只有m-1种
总方案为: K ( ) n ( m 1 ) K(块数)*n*(m-1)

第二步
我们考虑一个字符串——
n=8,m=3
aababacc
这个字符串我们可以求得方案为——
6 8 2 6*8*2
我们发现,原来的字符串变化可以取出第一块的一个a,放在第一个b后面——
ab"a"abacc
但是,把第一个b取出来放在第二个a左边,是一样的a"b"aabacc
然而这个在之前的情况是无法判断的。
具体怎么做?
对于ab这个字符串,会重复一次(把b放在a左边和a放在b右边一样)
对于ab"a"这个字符串,会重复三次(之前的一次,加上"a"放在b左边与b放在a右边,“a"放在a左边和b放在"a"左边)
对于ab"a”"b"这个字符串,会重复六次(之前三次,加上"b"放在"a"左边,"b"放在b左边,"b"放在a左边)
对于ababab……的情况,很好找规律吧?
所以,我们设一个P表示当前第i个位置,从当前位置往前的最长"abab……"的串长度为P。注意,这个字符串表示奇数位的字母相同,偶数位字母相同。
那么每次ans-P+1即可。

至于怎么证明这样就可以,感性理解理解。
如果你懂了怎么做,那么这个就是显然的。

var
        i,j,k,l,n,m:longint;
        ans:int64;
        s:ansistring;
        c1,c2:char;
begin
        //assign(input,'lcs.in');reset(input);
        //assign(output,'lcs.out');rewrite(output);
        readln(n,m);
        if n=1 then
        begin
                writeln(m-1);
                halt;
        end;
        readln(s);
        for i:=2 to n do
        begin
                if s[i-1]<>s[i] then
                begin
                       ans:=ans+n*(m-1);
                end;
        end;
        ans:=ans+n*(m-1);
        j:=1;
        for i:=2 to n do
        begin
                if j=1 then
                begin
                        if s[i]<>s[i-1] then
                        begin
                                inc(j);
                        end;
                end
                else
                begin
                        if (s[i]=s[i-2]) and (s[i]<>s[i-1]) then
                        begin
                                inc(j);
                        end
                        else
                        if (s[i]<>s[i-2]) and (s[i]<>s[i-1]) then
                        begin
                                j:=2;
                        end
                        else
                        if (s[i]=s[i-1]) then
                        begin
                                j:=1;
                        end;
                end;
                ans:=ans-j+1;
        end;
        writeln(ans);
end.