P7055

· · 题解

本题是 NWRRC 2015 Problem H。

本题在 CodeForces 上有提交通道：Gym 100801H。

首先，考虑下面的字符串：

cccccccccccccccccccccccccccccccccccccccccccccccccc

一共 50 个 c。

此处，为了表述方便，将这 50 个 c 从左往右依次记为第 49,48,\ldots,0 位。

接下来，将任意多个（0 \sim 25 个）互不重叠的 cc 改为 dD，即可构造哈希值相等的不同字符串。限制修改次数为 0 \sim 2 次，即可得到 1178 个字符串，通过本题。

证明：

设被修改的 cc 分别处于第 i+1 位和第 i 位（i=48,47,\ldots,0），则它们贡献的哈希值为：

\quad 99 \times 31^{i+1}+99 \times 31^i =99 \times 31 \times 31^i+99 \times 31^i =(99 \times 31 +99) \times 31^i =3168 \times 31^i.

改为 dD 后，它们贡献的哈希值为：

\quad 100 \times 31^{i+1}+68 \times 31^i =100 \times 31 \times 31^i+68 \times 31^i =(100 \times 31 +68) \times 31^i =3168 \times 31^i.

显然二者相等，因此修改后哈希值不变。

AC Code：

#include<iostream>
#include<string>
using namespace std;
const string stds="cccccccccccccccccccccccccccccccccccccccccccccccccc";//原字符串
const string rs="dD";//用于修改的字符串
int main()
{
    string s;
    int k,ans=1;
    cin>>k;
    cout<<stds<<'\n';//修改 0 次
    for(int i=0;i<=48;i++)//修改 1 次
    {
        if(ans==k) return 0;
        s=stds;
        s.replace(i,2,rs);
        cout<<s<<'\n';
        ans++;
    }
    for(int i=0;i<=46;i++)
        for(int j=i+2;j<=48;j++)//修改 2 次
        {
            if(ans==k) return 0;
            s=stds;
            s.replace(i,2,rs);
            s.replace(j,2,rs);
            cout<<s<<'\n';
            ans++;
        }
    return 0;
}