QOJ 可以评测

Solution

所有合法数独终盘约 \(6.67\times10^{21}\) 个。而字符串共 \(\sum_{k=1}^{15}26^k < 1.75 \times 10^{21}\) 种。合法数独的数量大于字符串数量，因此一定存在一种映射方案。

直接处理字符串并不方便，可以转换成它在所有可能字符串中字典序排名（从 \(0\) 开始），设为 \(x\)。

把每个 \(3\times 3\) 的块看作整体，预处理所有 \(9!\) 种块，从上到下从左往右逐块确定，就能先解决块内不重复的限制。设当前可以填 \(d\) 种块，则填第 \(x\bmod d\) 种，然后令 \(x\leftarrow \lfloor x/d\rfloor\)，相当于把 \(x\) 看成多进制数。但是这样限制太严，极易填到一半就填不下去了。

尝试优先填充限制最少的区域，先填数独中左上 \((0,0)\)、中间 \((1,1)\) 和右下 \((2,2)\) 这三个互相独立的块，但是上述问题仍然存在。

注意到填完对角线上三个块后：

\[x< \frac{1.75\times 10^{21}}{(9!)^3}<37000 \]

而填完这三个块后一定仍有大量解。对于剩下的空格，我们已经能够直接爆搜出第 \(x\) 个解。可以在时限内通过。

由于解密是加密的严格逆过程，上述加密过程直接倒过来即可。

Code

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i(a);i<b;++i)
#define per(i,a,b) for(int i(a);i>b;--i)
#define rept(i,a,b) for(int i(a);i<=b;++i)
#define pert(i,a,b) for(int i(a);i>=b;--i)
#define fi first
#define se second
#define pii pair<int,int>
#define me(a,x) memset(a,x,sizeof(a))
using namespace std;
constexpr int N=16,F=362880;
int n,cnt;
bool suc;
string s;
pair<int,int> ord[54];
__int128 x,pw[N],sm[N];
char p[3][3][F],t[9][9],a[9][9];
int f1[9],f2[9],f3[3][3];
void init(){
    char t[9];
    int k=0;
    iota(t,t+9,0);
    do{
        rep(i,0,3) rep(j,0,3) p[i][j][k]=t[i*3+j];
        ++k;
    }while(next_permutation(t,t+9));
    pw[0]=1;
    rept(i,1,15){
        pw[i]=pw[i-1]*26;
        sm[i]=sm[i-1]+pw[i];
    }
    k=0;
    rep(i,0,9) rep(j,0,9) if(i/3^j/3) ord[k++]={i,j};
}
void reset(){
    n=cnt=suc=x=0;
    s.clear();
    me(f1,0),me(f2,0),me(f3,0),me(t,0);
}
void dfs(int id,bool tp){
    if(id==54){
        if(tp&&cnt==x){
            suc=true;
            rep(i,0,9){
                rep(j,0,9) cout<<char(t[i][j]+'1');
                cout<<'\n';
            }
        }else if(!tp&&!memcmp(a,t,sizeof(a))) return suc=true,void();
        ++cnt;
        return;
    }
    int i=ord[id].fi,j=ord[id].se,bi=i/3,bj=j/3;
    rep(c,0,9){
        if(!(f1[i]>>c&1)&&!(f2[j]>>c&1)&&!(f3[bi][bj]>>c&1)){
            f1[i]|=1<<c,f2[j]|=1<<c,f3[bi][bj]|=1<<c;
            t[i][j]=c;
            dfs(id+1,tp);
            if(suc) return;
            f1[i]^=1<<c,f2[j]^=1<<c,f3[bi][bj]^=1<<c;
        }
    }
}
void encode(){
    reset();
    cin>>n>>s;
    pert(i,n-1,0) x=x*26+(s[i]-'a');
    x+=sm[n-1];
    rep(b,0,3){
        int k=x%F;
        rep(i,0,3) rep(j,0,3){
            char c=p[i][j][k];
            t[b*3+i][b*3+j]=c;
            f1[b*3+i]|=1<<c,f2[b*3+j]|=1<<c,f3[b][b]|=1<<c;
        }
        x/=F;
    }
    dfs(0,1);
}
void decode(){
    reset();
    rep(i,0,9) rep(j,0,9) cin>>a[i][j],a[i][j]-='1';
    __int128 d=1;
    rep(b,0,3){
        rep(k,0,F){
            bool f=true;
            rep(i,0,3) rep(j,0,3) if(p[i][j][k]^a[b*3+i][b*3+j]) f=false;
            if(f){
                rep(i,0,3) rep(j,0,3){
                    char c=p[i][j][k];
                    f1[b*3+i]|=1<<c,f2[b*3+j]|=1<<c,f3[b][b]|=1<<c;
                }
                x+=d*k;
                break;
            }
        }
        d*=F;
    }
    memcpy(t,a,sizeof(t));
    dfs(0,0);
    x+=d*cnt;
    while(sm[n]<=x) ++n;
    x-=sm[n-1];
    s.resize(n);
    rep(i,0,n) s[i]=x%26+'a',x/=26;
    cout<<s<<'\n';
}
signed main(){
    int op,t;
    cin>>op>>t;
    init();
    if(op==1) while(t--) encode();
    else while(t--) decode();
    return 0;
}