Wow! Such String!

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 137    Accepted Submission(s): 42

Special Judge

Problem Description Recently, doge starts to get interested in a strange problem: whether there exists a string A following all the rules below:

1.The length of the string A is N .

2.The string A contains only lowercase English alphabet letters.

3.Each substring of A with length equal to or larger than 4 can appear in the string exactly once.

Doge cannot solve the problem, so he turns to his brother Yuege for help. However, Yuege is busy setting problems. Would you please help doge solve this problem?  

Input There are several test cases, please process till EOF.

For each test case, there will be one line containing one integer N (1 ≤ N ≤ 500000). 

Sum of all N will not exceed 5000000.  

Output For each case, please output one line consisting a valid string if such a string exists, or “Impossible” (without quotes) otherwise. You can output any string if there are multiple valid ones.  

Sample Input

5
3
11
10
6
17
8
        

Sample Output

pwned
wow
suchproblem
manystring
soeasy
muchlinearalgebra
abcdabch
        

Source 2014西安全國邀請賽

題目大意：

給你一個整數n，讓你輸出一個字元串。必須滿足以下條件：

          1.字元串的長度為n。

          2.這個字元串隻包含小寫字母。

          3.字元串中長度大于等于4的子串最多隻能出現一次。

          如果無解輸出Impossible。

        開始看見這題感覺沒什麼，隻是資料有點大而已，在比賽的時候沒得到正确的答案，也沒仔細去研究。

剛開始想就4個不一樣，我直接随機函數，讓系統去自己做，但由于機率問題，不好說。出現wa，這個方法是行不通的（對于本題）。（上次聽學長講他之前在參加一次比賽的過程中用随機函數過了一題）這個方法不深究了

       我之前想到過dfs等方法，但沒實作。今天看了一個大神的題解發先我昨天想過，就沒實作。我也想手動推導一下。思路就先打表，把每個序列存好，先按：aaaabbbbccccddddeeeeffffgggghhhhiiiijjjjkkkkllllmmmmnnnnooooppppqqqqrrrrss存，然後枚舉所有的字母......yyyyzzzz   abcdefghijklmnopqrstuvwxyz   abdefhijlmnpqrtuvxyz   bcdfghjklnoprstvwxz  abefgijkmnoqrsuvwyz    acdeghiklmopqstuwxy  abcefgjklopqtuvyz  adefijknopstuxyz

最後發現最大長度為：26*26*26*26+3 = 456979

看見那位大牛的猜想，好像很有道理：

       可以有x個不同字元的長度大于等于m(m <= x)的子串最多隻能出現一次的主串的最長長度可以達到(x ^ m) + m - 1。

#include<iostream>
#include<fstream>
#include<iomanip>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<string>
#include<vector>
#include<sstream>
#include<cassert>
using namespace std;
//#define LL __int64

#ifdef __int64
typedef __int64 LL;
#else
typedef long long LL;
#endif
#define M 500005
#define N 26
char a[M];

int b[M];
bool vis[N][N][N][N];
int l=0;

void init() {
    int ok=1;
    memset(vis,0,sizeof(vis));

    for(int i=0; i<N; i++) {
        b[l]=b[l+1]=b[l+2]=b[l+3]=i;
        l+=4;
    }
    for(int i=3; i<l; i++) {
        vis[b[i]][b[i-1]][b[i-2]][b[i-3]]=1;
    }
    while(ok) {
        ok=0;
        for(int i=0; i<N; i++) {
            if(!vis[i][b[l-1]][b[l-2]][b[l-3]]) {
                b[l]=i;
                vis[b[l]][b[l-1]][b[l-2]][b[l-3]]=1;
                ok=1;
                l++;
            }
        }
    }
}

int main() {
    init();
    int n;
    while(cin>>n){
        if(n>l){
            puts("Impossible");
        }
        else{
            for(int i=0;i<n;i++){
                printf("%c",b[i]+97);
            }
            printf("\n");
        }
    }
    return 0;
}

/*
void init() {
    for(int i=0; i<=456979; i++) {
        int t=rand()%26;
        int t1=rand()%26;
        char c=(t+t1)/2+'a';
        a[i]=c;
    }
}

int main() {
    init();
    int n;
    while(scanf("%d",&n)!=EOF) {
        if(n>456979) {
            puts("Impossible");
        } else {
            for(int i=0; i<n; i++) {
                printf("%c",a[i]);
            }
            printf("\n");
        }
    }
    return 0;
}
*/