寫在前面

我還是太菜了，考試的時候只寫了一個$70pts$的暴力，用$map$居然可以過$70$分。這么良心的出題人少見了啊，然而之后的滿分做法會讓你們知道出題人有多么毒瘤。

Solution

$70pts$做法

反正題目都給了你一個Hash函數，直接預處理然后$map$儲存就可以搞定。

$100pts$做法

本題實質上是一個編碼與解碼的問題，我們只需要對于每個給定的輸入，一波逆運算就可以AC。
然而，$Hash$函數長成這樣：

unsigned int Hash(unsigned int t){unsigned int t=v;t=t+(t<<10);t=t^(t>>6);t=t+(t<<3);t=t^(t>>11);t=t+(t<<16);return t; }

觀察以后發現，誒，有個異或操作，woc，我不會還原異或！！！！！
不要慌，仔細想一想，對于$t=t$ ^ $(t>>i)$，我們在計算之前，可以考慮把$t$分成32i32 \over ii32?份（結果向上取整），為什么要這么做呢？因為可以看做是這樣的：

按照上面的想法，我們將現在的數分成三份（當前的數按照二進制表示，是一個$01$串）：$X1$,$X2$,$X3$。
那么$X1$可以看作是$t<<22$，那么$X2$怎么算呢？我們可以這樣想：

這個想法很直觀，但是怎么在數學上實現呢？先讓$t>>11$，這樣就裁掉$X3$了，然后我們再讓$t$異或上$X1<<11$，因為一個數異或自己等于零，異或零等于自己，所以說我們讓$t$當中原來和$X1$相等的部分和$X1<<11$異或，這樣就在裁掉$X1$的同時，保證了$X2$是完好的。$X3$按照一樣的思想，稍加推算也可以得出式子。
那么，現在我們有$X1$,$X2$,$X3$了，怎么進一步還原$t$呢？注意到，現在的數，實際上是原數異或上$X1,X2$兩段得到的，也就是說現在的$X2$是原數的$X2$和現在的$X1$異或得到的，所以說反過來異或一次，即$X2$異或$X1$，就是原數的$X2$那一段，$X3$同理，$X1$是沒有變的。所以會所我們再將這幾段拼接回去就好了。方法也很簡單，將$X1<<22$異或$X2<<11$再異或$X3$即可，可以自己手推一下，加深理解。
這樣的話，異或的逆運算就解決了，而加又怎么辦呢？
其實這相當解一個方程：
(2i+1)x≡t(mod232) \left(2^i+1\right)x\equiv t \pmod {2^{32}} (2i+1)x≡t(mod232)
顯然擴展歐幾里得算法就可以搞定這一步，具體見代碼實現。

#include<bits/stdc++.h> using namespace std; typedef long long ll; ll read(){ll sum=0,neg=1;char c=getchar();while((c>'9'||c<'0')&&c!='-') c=getchar();if(c=='-') neg=-1,c=getchar();while(c>='0'&&c<='9') sum=(sum<<1)+(sum<<3)+c-'0',c=getchar();return sum*neg; } /* 70pts做法，十分暴力的打表。 map<unsigned int,int> h; unsigned int Hash(unsigned int v){unsigned int t=v;t=t+(t<<10);t=t^(t>>6);t=t+(t<<3);t=t^(t>>11);t=t+(t<<16);return t; } int main(){freopen("encrypt.in","r",stdin);freopen("encrypt.out","w",stdout);for(unsigned int i=1;i<=100000;i++) h[Hash(i)]=i;int q;q=read();for(int i=1;i<=q;i++){int t;t=read();printf("%d\n",h[t]);}return 0; } */ //100pts const ll mod=1ll<<32; ll exgcd(ll a,ll b,ll &x,ll &y){b?(exgcd(b,a%b,y,x),y-=a/b*x):(x=1,y=0); } ll calcinv(ll t){ll x,y;exgcd(t,mod,x,y);x=(x%mod+mod)%mod;return x; } ll ksc(ll a,ll b,ll ret=0){//快速乘，直接乘會爆long long for(;b;b>>=1,a=(a+a)%mod) if(b&1) ret=(ret+a)%mod;return ret; } int main(){/*ios::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL);*/int q;q=read();for(int i=1;i<=q;i++){ll t=read();//第一步還原->還原t=t+(t<<16) t=ksc(t,calcinv((1ll<<16)+1));//第二步還原->還原t=t^(t>>11) ll x1=t>>22,x2=(t>>11)^(x1<<11),x3=t^(x1<<22)^(x2<<11);x2=x2^x1; x3=x3^x2; t=(x1<<22)^(x2<<11)^x3;//第三步還原->還原t=t+(t<<3)t=ksc(t,calcinv((1ll<<3)+1));//第四步還原->還原t=t^(t>>6)x1=t>>30,x2=(t>>24)^(x1<<6),x3=(t>>18)^(x1<<12)^(x2<<6);ll x4=(t>>12)^(x1<<18)^(x2<<12)^(x3<<6),x5=(t>>6)^(x1<<24)^(x2<<18)^(x3<<12)^(x4<<6);ll x6=t^(x1<<30)^(x2<<24)^(x3<<18)^(x4<<12)^(x5<<6);x2^=x1,x3^=x2,x4^=x3,x5^=x4,x6^=x5;t=(x1<<30)^(x2<<24)^(x3<<18)^(x4<<12)^(x5<<6)^x6;//第五步還原->還原t=t+(t<<10)t=ksc(t,calcinv((1ll<<10)+1));printf("%lld\n",t);}return 0; }

轉載于:https://www.cnblogs.com/Neonen/p/9832492.html

總結

以上是生活随笔為你收集整理的NOIP提高模拟-20181019-T1-加密的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。