• Solution \(1\): follow the definition to construct the carpet step-by-step

For \(k=0,1,\ldots,N\), we try to construct the strings corresponding to the level-\(i\) carpet.
We will denote the \(j\)-th character of \(S_i\) for the level-\(k\) carpet by \(S^k_{i,j}\) \((1\leq i,j\leq 3^k)\).

For the level-\(0\) carpet, we can let \(S^0_{0,0}=\)#.
For \(k\geq 0\), in order to construct the level-\((k+1)\) carpet, by definition we have the following for integer pairs \((x,y)\) between \(0\) and \(2\):

• If \((x,y)\neq (1,1)\), for \(1\leq i,j\leq 3^k\), let \(S^{k+1}_{x\cdot 3^k+i,y\cdot 3^k+j}=S^k_{i,j}\) .
• If \((x,y)=(1,1)\), for \(1\leq i,j\leq 3^k\) , let \(S^{k+1}_{x\cdot 3^k+i,y\cdot 3^k+j}=\)..

This way, the level-\(k\) carpet can be constructed. The complexity is \(O(3^{2N})\), which is fast enough.

Therefore, the problem has been solved.

• Solution \(2\): consider the condition that a square of the carpet is white.

According to the definition in the problem statement, for the level-\(N\) carpet, the square at the \(i\)-th row from the top and \(j\)-th column from the left is white if and only if,
for some integer \(k\) with \(1\leq k\leq N\), the \(k\)-th digits in the trinary representations of \((i-1)\) and \((j-1)\) are both \(1\).
Thus, it is sufficient to check that condition for each \(1\leq i,j\leq 3^N\). The complexity is \(O(N\cdot 3^{2N})\), which is fast enough.

Sample code in C++:

#include <bits/stdc++.h>

using namespace std;

int main() {
	int n,l=1;
    char a[729][730];
    for(int i=0;i<729;i++)for(int j=0;j<730;j++)a[i][j]=0;

    cin>>n;
    a[0][0]='#';
    for(int k=0;k<n;k++){
        for(int x=0;x<3;x++){
            for(int y=0;y<3;y++){
                if((x==0)&&(y==0))continue;
                if((x==1)&&(y==1)){
                    for(int i=0;i<l;i++)for(int j=0;j<l;j++)a[x*l+i][y*l+j]='.';
                }
                else{
                    for(int i=0;i<l;i++){
                        for(int j=0;j<l;j++){
                            a[x*l+i][y*l+j]=a[i][j];
                        }
                    }
                }
            }
        }
        l*=3;
    }

    for(int i=0;i<l;i++)cout<<a[i]<<endl;

    return 0;
}