原题链接

题目原文

Vasily Tadokorov is a stringologist. He thinks a string is fragrant if it can be divided into two parts: nunhehheh as the prefix and a number of (excluding 0) a as the suffix. For example, nunhehhehaaaaaa is fragrant, but nunhehheh and nunhehhehoooaaa are not fragrant.

Today Vasily Tadokorov has some strings consisting of lowercase English letters. For each string, he wants to know how many subsequences of this string are fragrant. A string a is a subsequence of a string b if a can be obtained from b by deletion of several (including 0) characters.

The above is a problem of string that Vasily came up with. As we know, a problem usually has several examples for better understanding. However, Vasily gets buried in making some fragrant examples. After 2000 years, he finally makes two perfect examples as follows.

Example 1:

  • Input: nunhehhehahaahahahahahahaahaahahahahha
  • Output: 114514

Example 2:

  • Input: nunhehhehhehhahaahahahaahaahahaaaahaa
  • Output: 1919810

Vasily is not clever enough. He doesn’t want to work for another 2000 years, so he asks you for help. He gives you T tasks, each of which contains an integer n, and you should construct a string consisting of only lowercase English letters that has exactly n fragrant subsequences.

Input

  • The first line contains an integer T (1≤T≤1000), denoting the number of tasks.

  • Each of the next T lines contains an integer n (0≤n≤1e9).

Output

  • For each test case, output one string consisting of only lowercase English letters in a single line indicating the answer. You need to ensure that the sum of the length over all the output strings does not exceed 1e6. It can be proved that a solution always exists. If there are multiple solutions, print any.
1
2
3
4
5
6
7
8
9
10
11
12
Example

input:

2
114514
1919810

output:

nunhehhehahaahahahahahahaahaahahahahha
nunhehhehhehhahaahahahaahaahahaaaahaa

题目大意

给定t组数据, 每组一个数n, 要求生成一个恰好有n个合法子串的母串, 当且仅当子串是”nunhehheh”后面跟着至少一个‘a’的字符串时合法, 如”nunhehhehaaaaaa”合法, “nunhehheh”不合法, 生成的母串长度不能超过1e6.

注意子串的定义, 就算两个子串字母和排列完全一致但某位置上保留了原串不同位置上的相同字母也算两个不同的子串.

题解

这道题不难, 让人印象深刻的是其富有inm特色的原文题意(大喜)

考虑以下情况:

  1. 将合法子串前缀拆成”nunhehhe”和最后一个字母”h”, 只考虑”h”后面的a的数量x, 由子串产生规则及二项式定理可知所能产生的子串数量为( 2^x-1 )
  2. 在”nunhehhehaaaaaa”倒数第三个’a’前插入一个’h’变为”nunhehhehaaahaaa”, 原先合法子串数量( 2^6-1 )变为( ( 2^6-1 ) + ( 2^3-1 ) )
  3. 在”nunhehhehaaaaaa”倒数第三个’a’前插入两个’h’变为”nunhehhehaaahhaaa”, 原先合法子串数量( 2^6-1 )变为( ( 2^6-1 ) + 2*( 2^3-1 ) )

不难发现, 由于可选择”nunhehhe”后任意一个h开始子串, 在适当的位置插入’h’可增加合法子串数量, 可以用一种类似二进制拼凑的方法在凑齐n个子串同时尽量减少子串长度, 但要注意这里不是真正的二进制拼凑(拼凑块不符合2^k大小, 且拼凑过程中可能产生需要二倍的情况).

具体实现见代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
typedef long long LL;

int t;
vector<LL> v;
LL n;

void init(){ // 初始化各个拼凑块大小
    LL x=2;
    for(int i=1;i<=36;i++,x*=2){
        v.push_back(x-1); // 由二项式定理可知, 末尾的k个"a"能够提供(2^k-1)个合法子串
    }
}

int main(){
    init();
    cin>>t;
    while(t--){
        cin>>n;
        int x=(upper_bound(v.begin(),v.end(),n)-v.begin())-1; // 找最大的拼凑块位置, 然后从大到小拼凑来减少母串长度(若从小到大会导致h过多进而母串过长, 这与二进制拼凑每块最多拼凑一次不同), 注意是upper_bound -1
        string ans="nunhehhe";
        for(int i=x;i>=0;i--){
            int s=n/v[i];
            for(int j=0;j<s;j++) ans+="h";
            // 可选择"nunhehhe"后任意一个h开始子串, 因此h的插入可用于分割产生各个拼凑块
            // 因为不是真正的二进制拼凑, 只是借用其思想(实际是2^k-1在拼凑), 所以可能出现这一拼凑块需要*2的情况, 此时接两个h
            ans+="a"; // 从找到最大拼凑块位置开始, a的数量就已经确定了, 不同之处在于h的分布
            n%=v[i];
        }
        cout<<ans<<endl;
    }
}