## [题目链接](https://qoj.ac/contest/2641/problem/14942) 第一次见通信题诶！ 但这题本质是一道奇思妙想的构造题！ 一种很好的构造方法是前 $m$ 位为 $1,2,\cdots,m$，这样就可以在解码时知道每个数变成了 $0$ 还是 $1$ 对于剩下的位置，我们需要找到一种编码方式，使其在 $0/1$ 映射下具有唯一性 这时候，如果 $m$ 是一个质数，显然只需要将 $1,2,\cdots,m$ 循环位移 $x_i$ 次就一定可以保证映射后不同 [collapse status="false" title="这是为什么？"] 对于一个长度位 $m$ 的数组，我们想知道最少将数组循环位移多少次后会和原数组相同 这时循环位移次数一定是 $p$ 的一个因数 $x$ 所以若 $m$ 时质数，$x$ 只能是 $1$ 或 $p$ 但该题保证不会有全 $0$ 或全 $1$，那么 $x$ 只能是 $p$ [/collapse] 这就启发我们，当 $m$ 不是质数的时候我们可以尝试找到一个比 $m$ 大的质数 $p$，保证 $1\to m$ 都在一个长度为 $p$ 的数组中，由上面的证明，还可以保证映射后的唯一性 一个比较方便的构造方法是前 $m$ 位不变，然后放 $p$ 位，令 $B = [1, 2, \dots, m, \quad 1, 2, \dots, p-m]$，将 $B$ 循环位移 $x_i$ 位，剩下的位置补充 $p-m+1, \dots, m$ 并且题解说，有一个伯特兰-切比雪夫定理：$m$ 到 $2m$ 之间必然存在一个质数 $p$，所以从 $m$ 开始往大找到的第一个质数一定满足条件！ 对于解码，有两种方法 我们需要计算长度为 $p$ 的初始数组（由前 $m$ 位映射得到）循环位移多少次可以得到中间 $p$ 位，这有非常多种方法！ 一种方法是把中间 $p$ 位倍长后使用 KMP，找到第一次完全匹配！ 还有一种方法是计算初始数组 $1$ 的平均位置需要位移多少距离可以到达加密数组 $1$ 的平均位置，因为 $p$ 是质数，可以保证解的唯一性！ 还可以通过最小表示法来计算！ 代码还是超好写的！ ## CODE（使用 KMP 计算位移） ```cpp #include <bits/stdc++.h> // #define int long long using namespace std; const int N=1e6+25; int n, m, s1[N], s2[N], nxt[N]; bool pvis[N]; int pcnt, p[N]; void init(int n) { for (int i=2; i<=n; i++) { if (!pvis[i]) p[++pcnt]=i; for (int j=1; j<=pcnt && i*p[j]<=n; j++) { pvis[i*p[j]]=1; if (i%p[j]==0) break; } } } int find(int m) { while (pvis[m]) m++; return m; } void solve1() { cin>>n>>m; int p=find(m); for (int i=1; i<=n; i++) { int x; cin>>x; x--; for (int i=1; i<=m; i++) cout<<i<<" "; for (int i=1; i<=p; i++) cout<<(i-1+p-x)%p%m+1<<" "; for (int i=p+1; i<=m*2; i++) cout<<(i-1)%m+1<<" "; cout<<endl; } } void solve2() { cin>>n>>m; int p=find(m); while (n--) { for (int i=1; i<=m; i++) { cin>>s2[i]; if (i+m<=p) s2[i+m]=s2[i]; } s2[p+1]=-1; nxt[1]=0; for (int i=2, j=0; i<=p; i++) { while (j && s2[i]!=s2[j+1]) j=nxt[j]; if (s2[i]==s2[j+1]) j++; nxt[i]=j; } for (int i=1; i<=p; i++) { cin>>s1[i]; s1[i+p]=s1[i]; } s1[p*2+1]=-1; int ans=0; for (int i=1, j=0; i<=p*2; i++) { while (j && (j==p || s1[i]!=s2[j+1])) j=nxt[j]; if (s1[i]==s2[j+1]) j++; if (j==p) { ans=i-p+1; break; } } for (int i=p+1; i<=m*2; i++) { int x; cin>>x; } cout<<ans<<endl; } } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); init(N-10); int T=1; cin>>T; if (T==1) solve1(); else solve2(); return 0; } ``` ## CODE（使用位移差计算位移） ```cpp void solve2() { cin>>n>>m; int p=find(m); while (n--) { int cnt=0, pos1=0, pos2=0; for (int i=1; i<=m; i++) { int x; cin>>x; if (x) { cnt++, pos1=(pos1+i)%p; if (i+m<=p) cnt++, pos1=(pos1+i+m)%p; } } for (int i=1; i<=p; i++) { int x; cin>>x; if (x) pos2=(pos2+i)%p; } for (int i=p+1; i<=m*2; i++) { int x; cin>>x; } for (int i=1; i<=m; i++) { if (pos1==pos2) { cout<<i<<endl; break; } pos1=(pos1+cnt)%p; } } } ``` Loading... ## [题目链接](https://qoj.ac/contest/2641/problem/14942) 第一次见通信题诶！ 但这题本质是一道奇思妙想的构造题！ 一种很好的构造方法是前 $m$ 位为 $1,2,\cdots,m$，这样就可以在解码时知道每个数变成了 $0$ 还是 $1$ 对于剩下的位置，我们需要找到一种编码方式，使其在 $0/1$ 映射下具有唯一性 这时候，如果 $m$ 是一个质数，显然只需要将 $1,2,\cdots,m$ 循环位移 $x_i$ 次就一定可以保证映射后不同 <div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-6fb36f48571d2416122a36ada6a80a0c46" aria-expanded="true"><div class="accordion-toggle"><span style="">这是为什么？</span> <i class="pull-right fontello icon-fw fontello-angle-right"></i> </div> </div> <div class="panel-body collapse-panel-body"> <div id="collapse-6fb36f48571d2416122a36ada6a80a0c46" class="collapse collapse-content"><p></p> 对于一个长度位 $m$ 的数组，我们想知道最少将数组循环位移多少次后会和原数组相同 这时循环位移次数一定是 $p$ 的一个因数 $x$ 所以若 $m$ 时质数，$x$ 只能是 $1$ 或 $p$ 但该题保证不会有全 $0$ 或全 $1$，那么 $x$ 只能是 $p$ <p></p></div></div></div> 这就启发我们，当 $m$ 不是质数的时候我们可以尝试找到一个比 $m$ 大的质数 $p$，保证 $1\to m$ 都在一个长度为 $p$ 的数组中，由上面的证明，还可以保证映射后的唯一性 一个比较方便的构造方法是前 $m$ 位不变，然后放 $p$ 位，令 $B = [1, 2, \dots, m, \quad 1, 2, \dots, p-m]$，将 $B$ 循环位移 $x_i$ 位，剩下的位置补充 $p-m+1, \dots, m$ 并且题解说，有一个伯特兰-切比雪夫定理：$m$ 到 $2m$ 之间必然存在一个质数 $p$，所以从 $m$ 开始往大找到的第一个质数一定满足条件！ 对于解码，有两种方法 我们需要计算长度为 $p$ 的初始数组（由前 $m$ 位映射得到）循环位移多少次可以得到中间 $p$ 位，这有非常多种方法！ 一种方法是把中间 $p$ 位倍长后使用 KMP，找到第一次完全匹配！ 还有一种方法是计算初始数组 $1$ 的平均位置需要位移多少距离可以到达加密数组 $1$ 的平均位置，因为 $p$ 是质数，可以保证解的唯一性！ 还可以通过最小表示法来计算！ 代码还是超好写的！ ## CODE（使用 KMP 计算位移） ```cpp #include <bits/stdc++.h> // #define int long long using namespace std; const int N=1e6+25; int n, m, s1[N], s2[N], nxt[N]; bool pvis[N]; int pcnt, p[N]; void init(int n) { for (int i=2; i<=n; i++) { if (!pvis[i]) p[++pcnt]=i; for (int j=1; j<=pcnt && i*p[j]<=n; j++) { pvis[i*p[j]]=1; if (i%p[j]==0) break; } } } int find(int m) { while (pvis[m]) m++; return m; } void solve1() { cin>>n>>m; int p=find(m); for (int i=1; i<=n; i++) { int x; cin>>x; x--; for (int i=1; i<=m; i++) cout<<i<<" "; for (int i=1; i<=p; i++) cout<<(i-1+p-x)%p%m+1<<" "; for (int i=p+1; i<=m*2; i++) cout<<(i-1)%m+1<<" "; cout<<endl; } } void solve2() { cin>>n>>m; int p=find(m); while (n--) { for (int i=1; i<=m; i++) { cin>>s2[i]; if (i+m<=p) s2[i+m]=s2[i]; } s2[p+1]=-1; nxt[1]=0; for (int i=2, j=0; i<=p; i++) { while (j && s2[i]!=s2[j+1]) j=nxt[j]; if (s2[i]==s2[j+1]) j++; nxt[i]=j; } for (int i=1; i<=p; i++) { cin>>s1[i]; s1[i+p]=s1[i]; } s1[p*2+1]=-1; int ans=0; for (int i=1, j=0; i<=p*2; i++) { while (j && (j==p || s1[i]!=s2[j+1])) j=nxt[j]; if (s1[i]==s2[j+1]) j++; if (j==p) { ans=i-p+1; break; } } for (int i=p+1; i<=m*2; i++) { int x; cin>>x; } cout<<ans<<endl; } } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); init(N-10); int T=1; cin>>T; if (T==1) solve1(); else solve2(); return 0; } ``` ## CODE（使用位移差计算位移） ```cpp void solve2() { cin>>n>>m; int p=find(m); while (n--) { int cnt=0, pos1=0, pos2=0; for (int i=1; i<=m; i++) { int x; cin>>x; if (x) { cnt++, pos1=(pos1+i)%p; if (i+m<=p) cnt++, pos1=(pos1+i+m)%p; } } for (int i=1; i<=p; i++) { int x; cin>>x; if (x) pos2=(pos2+i)%p; } for (int i=p+1; i<=m*2; i++) { int x; cin>>x; } for (int i=1; i<=m; i++) { if (pos1==pos2) { cout<<i<<endl; break; } pos1=(pos1+cnt)%p; } } } ``` 最后修改：2026 年 01 月 04 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏