题目描述Bob\texttt{Bob}Bob和Alice\texttt{Alice}Alice开始使用一种全新的编码方案。他们选择了一个由nnn个不同整数组成的密钥a1,a2,…,ana_1, a_2, \dots, a_na1,a2,…,an其中1≤ai≤n1 \leq a_i \leq n1≤ai≤n。编码原理如下将消息写在密钥下方使得消息中的字符与密钥中的数字对齐。位置iii处的字符在加密后出现在位置aia_iai处。然后对加密后的消息以相同的方式再次加密。这个过程重复kkk次。经过kkk次加密后他们交换消息。消息长度总是≤n\leq n≤n。如果消息短于nnn则在末尾添加空格以使其长度达到nnn。要求编写程序读取密钥然后读取一系列由kkk和消息组成的对输出经过kkk次加密后的消息。输入格式输入文件由多个数据块组成。每个数据块的第一行包含一个整数nnn0n≤2000 n \leq 2000n≤200。下一行包含nnn个两两不同的整数每个整数在111到nnn之间。接下来的若干行每行包含一个整数kkk和一个ASCII\texttt{ASCII}ASCII字符消息用空格分隔。数据块以单独一行0结束。最后一个数据块之后还有单独一行0。输出格式输出分为与输入块对应的块。每个块包含输入消息按相同顺序加密后的结果。每个加密消息的长度为nnn。每个块之后输出一个空行。样例输入10 4 5 3 7 2 8 1 6 10 9 1 Hello Bob 1995 CERC 0 0样例输出BolHeol b C RCE题目分析问题的本质这是一个置换的幂问题。密钥定义了一个置换σ\sigmaσ对于位置iiiσ(i)ai\sigma(i) a_iσ(i)ai。一次加密就是将消息按照置换σ\sigmaσ重新排列encrypted[ai]message[i] \text{encrypted}[a_i] \text{message}[i]encrypted[ai]message[i]等价地如果我们将消息看作一个函数m:{1,…,n}→charm: \{1, \dots, n\} \to \text{char}m:{1,…,n}→char那么加密一次得到的新消息是m∘σ−1m \circ \sigma^{-1}m∘σ−1。但更方便的理解是位置iii的字符在加密后会移动到位置σ(i)\sigma(i)σ(i)。经过kkk次加密后位置iii的字符会移动到位置σk(i)\sigma^k(i)σk(i)。直接模拟的瓶颈最直接的方法是对每条消息循环kkk次每次应用置换。时间复杂度为O(k×n)O(k \times n)O(k×n)。但kkk可能非常大样例中k1995k 1995k1995实际可能更大直接模拟不可行。置换的循环分解置换可以分解为若干个不相交的循环cycle\texttt{cycle}cycle。例如密钥4 5 3 7 2 8 1 6 10 9对应的置换为1→4→7→11 \to 4 \to 7 \to 11→4→7→1循环长度为3332→5→22 \to 5 \to 22→5→2循环长度为2223→33 \to 33→3循环长度为1116→8→66 \to 8 \to 66→8→6循环长度为2229→10→99 \to 10 \to 99→10→9循环长度为222在一个长度为LLL的循环中经过kkk次置换后位置iii的字符会移动到循环中的第(k mod L)(k \bmod L)(kmodL)个位置之后。快速加密因此不需要模拟kkk次加密只需要找出每个位置所在的循环及其长度计算k mod Lk \bmod LkmodL确定字符移动的目标位置直接构造加密后的消息解题思路步骤一读取密钥并构建置换密钥是一个长度为nnn的排列表示σ(i)ai\sigma(i) a_iσ(i)ai。读取后存储在key[1..n]中。步骤二循环分解对于每个位置iii沿着置换追踪直到回到iii记录循环中的位置序列。同时记录循环长度cycle[i]。代码中的实现方式for(inti1;in;i){intlength1;permutation[i][length]key[i];for(intjkey[i];j!i;jkey[j],permutation[i][length]j)length;permutation[i][0]permutation[i][length];cycle[i]length;}这里permutation[i][t]表示从位置iii出发经过ttt次置换后到达的位置。特别地permutation[i][0]存储的是经过cycle[i]次置换后回到的位置即iii本身。步骤三处理消息每条消息的格式为k message。由于消息可能包含空格需要使用getline读取。但需要注意输入格式中k和消息之间用空格分隔且消息可能为空。处理步骤读取整数kkk使用getline读取剩余的行作为消息如果消息长度小于nnn在末尾补空格计算k % cycle[i]确定位置iii的字符应该移动到permutation[i][k % cycle[i]]构造加密后的消息并输出步骤四输出格式每个加密消息占一行长度为nnn每个数据块结束后输出一个空行算法复杂度分析时间复杂度循环分解O(n)O(n)O(n)因为每个位置只被访问一次每条消息加密O(n)O(n)O(n)总复杂度O(n×m)O(n \times m)O(n×m)其中mmm是消息数量空间复杂度存储密钥O(n)O(n)O(n)存储循环信息permutation数组大小为O(n2)O(n^2)O(n2)200×20040000200 \times 200 40000200×20040000完全可行消息存储O(n)O(n)O(n)正确性证明引理 1置换可以分解为若干个不相交的循环。证明这是置换的循环分解定理。□\square□引理 2对于长度为LLL的循环经过kkk次置换后位置iii的字符移动到循环中距iii步数为k mod Lk \bmod LkmodL的位置。证明在循环中每应用一次置换字符沿循环移动一步。经过kkk步后移动了k mod Lk \bmod LkmodL步因为LLL步后回到原位置。□\square□引理 3permutation[i][k % cycle[i]]正确给出了位置iii的字符在kkk次加密后的目标位置。证明permutation[i][t]存储从iii出发经过ttt步到达的位置。由引理 2tk mod Lt k \bmod LtkmodL即为所需步数。□\square□参考代码// Cipher// UVa ID: 306// Verdict: Accepted// Submission Date: 2016-07-01// UVa Run Time: 0.030s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intkey[210];// 存储密钥置换intcycle[210];// 每个位置所在循环的长度intpermutation[210][210];// permutation[i][t] 表示从 i 出发经过 t 次置换后的位置intn,k;// n: 置换长度, k: 加密次数charmessage[210];// 原始消息处理后长度为 ncharciphered[210];// 加密后的消息// 找出每个位置所在的循环并记录循环信息和步进位置voidfindCycle(){for(inti1;in;i){intlength1;// 记录第一步从 i 到 key[i]permutation[i][length]key[i];// 沿着置换追踪直到回到 ifor(intjkey[i];j!i;jkey[j],permutation[i][length]j)length;// permutation[i][0] 存储经过 cycle[i] 步后的位置即 i 本身permutation[i][0]permutation[i][length];cycle[i]length;}}intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);while(cinn,n){// 读取密钥1-based 索引for(inti1;in;i)cinkey[i];// 处理该数据块中的所有消息while(cink,k){// 读取消息可能包含空格cin.getline(message,210);// 计算消息的实际长度intnumber1;while(message[number]!\0)number;// 如果消息长度不足 n用空格填充while(numbern)message[number] ;message[number]\0;// 计算置换的循环分解findCycle();// 加密位置 i 的字符移动到 permutation[i][k % cycle[i]]for(inti1;in;i)ciphered[permutation[i][k%cycle[i]]]message[i];// 输出加密后的消息for(inti1;in;i)coutciphered[i];cout\n;}// 每个数据块后输出一个空行cout\n;}return0;}总结本题的核心在于置换的循环分解将置换分解为若干个不相交的循环快速幂思想kkk次置换等价于在循环中移动k mod Lk \bmod LkmodL步预处理循环信息提前计算每个位置ttt步后的目标位置关键点回顾知识点说明置换a1,a2,…,ana_1, a_2, \dots, a_na1,a2,…,an是1∼n1 \sim n1∼n的一个排列循环分解每个位置属于唯一的一个循环循环长度LLL经过LLL次置换后回到原位置加密kkk次等价于在循环中移动k mod Lk \bmod LkmodL步空格填充消息短于nnn时末尾补空格输出格式每个数据块后空行与快速幂的类比本题的核心技巧与快速幂思想类似通过预计算置换的幂次将O(k)O(k)O(k)的模拟优化为O(logk)O(\log k)O(logk)甚至O(1)O(1)O(1)因为kkk的模数很小。这种“置换幂”的技巧在密码学和组合数学中具有广泛应用。
UVa 306 Cipher
题目描述Bob\texttt{Bob}Bob和Alice\texttt{Alice}Alice开始使用一种全新的编码方案。他们选择了一个由nnn个不同整数组成的密钥a1,a2,…,ana_1, a_2, \dots, a_na1,a2,…,an其中1≤ai≤n1 \leq a_i \leq n1≤ai≤n。编码原理如下将消息写在密钥下方使得消息中的字符与密钥中的数字对齐。位置iii处的字符在加密后出现在位置aia_iai处。然后对加密后的消息以相同的方式再次加密。这个过程重复kkk次。经过kkk次加密后他们交换消息。消息长度总是≤n\leq n≤n。如果消息短于nnn则在末尾添加空格以使其长度达到nnn。要求编写程序读取密钥然后读取一系列由kkk和消息组成的对输出经过kkk次加密后的消息。输入格式输入文件由多个数据块组成。每个数据块的第一行包含一个整数nnn0n≤2000 n \leq 2000n≤200。下一行包含nnn个两两不同的整数每个整数在111到nnn之间。接下来的若干行每行包含一个整数kkk和一个ASCII\texttt{ASCII}ASCII字符消息用空格分隔。数据块以单独一行0结束。最后一个数据块之后还有单独一行0。输出格式输出分为与输入块对应的块。每个块包含输入消息按相同顺序加密后的结果。每个加密消息的长度为nnn。每个块之后输出一个空行。样例输入10 4 5 3 7 2 8 1 6 10 9 1 Hello Bob 1995 CERC 0 0样例输出BolHeol b C RCE题目分析问题的本质这是一个置换的幂问题。密钥定义了一个置换σ\sigmaσ对于位置iiiσ(i)ai\sigma(i) a_iσ(i)ai。一次加密就是将消息按照置换σ\sigmaσ重新排列encrypted[ai]message[i] \text{encrypted}[a_i] \text{message}[i]encrypted[ai]message[i]等价地如果我们将消息看作一个函数m:{1,…,n}→charm: \{1, \dots, n\} \to \text{char}m:{1,…,n}→char那么加密一次得到的新消息是m∘σ−1m \circ \sigma^{-1}m∘σ−1。但更方便的理解是位置iii的字符在加密后会移动到位置σ(i)\sigma(i)σ(i)。经过kkk次加密后位置iii的字符会移动到位置σk(i)\sigma^k(i)σk(i)。直接模拟的瓶颈最直接的方法是对每条消息循环kkk次每次应用置换。时间复杂度为O(k×n)O(k \times n)O(k×n)。但kkk可能非常大样例中k1995k 1995k1995实际可能更大直接模拟不可行。置换的循环分解置换可以分解为若干个不相交的循环cycle\texttt{cycle}cycle。例如密钥4 5 3 7 2 8 1 6 10 9对应的置换为1→4→7→11 \to 4 \to 7 \to 11→4→7→1循环长度为3332→5→22 \to 5 \to 22→5→2循环长度为2223→33 \to 33→3循环长度为1116→8→66 \to 8 \to 66→8→6循环长度为2229→10→99 \to 10 \to 99→10→9循环长度为222在一个长度为LLL的循环中经过kkk次置换后位置iii的字符会移动到循环中的第(k mod L)(k \bmod L)(kmodL)个位置之后。快速加密因此不需要模拟kkk次加密只需要找出每个位置所在的循环及其长度计算k mod Lk \bmod LkmodL确定字符移动的目标位置直接构造加密后的消息解题思路步骤一读取密钥并构建置换密钥是一个长度为nnn的排列表示σ(i)ai\sigma(i) a_iσ(i)ai。读取后存储在key[1..n]中。步骤二循环分解对于每个位置iii沿着置换追踪直到回到iii记录循环中的位置序列。同时记录循环长度cycle[i]。代码中的实现方式for(inti1;in;i){intlength1;permutation[i][length]key[i];for(intjkey[i];j!i;jkey[j],permutation[i][length]j)length;permutation[i][0]permutation[i][length];cycle[i]length;}这里permutation[i][t]表示从位置iii出发经过ttt次置换后到达的位置。特别地permutation[i][0]存储的是经过cycle[i]次置换后回到的位置即iii本身。步骤三处理消息每条消息的格式为k message。由于消息可能包含空格需要使用getline读取。但需要注意输入格式中k和消息之间用空格分隔且消息可能为空。处理步骤读取整数kkk使用getline读取剩余的行作为消息如果消息长度小于nnn在末尾补空格计算k % cycle[i]确定位置iii的字符应该移动到permutation[i][k % cycle[i]]构造加密后的消息并输出步骤四输出格式每个加密消息占一行长度为nnn每个数据块结束后输出一个空行算法复杂度分析时间复杂度循环分解O(n)O(n)O(n)因为每个位置只被访问一次每条消息加密O(n)O(n)O(n)总复杂度O(n×m)O(n \times m)O(n×m)其中mmm是消息数量空间复杂度存储密钥O(n)O(n)O(n)存储循环信息permutation数组大小为O(n2)O(n^2)O(n2)200×20040000200 \times 200 40000200×20040000完全可行消息存储O(n)O(n)O(n)正确性证明引理 1置换可以分解为若干个不相交的循环。证明这是置换的循环分解定理。□\square□引理 2对于长度为LLL的循环经过kkk次置换后位置iii的字符移动到循环中距iii步数为k mod Lk \bmod LkmodL的位置。证明在循环中每应用一次置换字符沿循环移动一步。经过kkk步后移动了k mod Lk \bmod LkmodL步因为LLL步后回到原位置。□\square□引理 3permutation[i][k % cycle[i]]正确给出了位置iii的字符在kkk次加密后的目标位置。证明permutation[i][t]存储从iii出发经过ttt步到达的位置。由引理 2tk mod Lt k \bmod LtkmodL即为所需步数。□\square□参考代码// Cipher// UVa ID: 306// Verdict: Accepted// Submission Date: 2016-07-01// UVa Run Time: 0.030s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intkey[210];// 存储密钥置换intcycle[210];// 每个位置所在循环的长度intpermutation[210][210];// permutation[i][t] 表示从 i 出发经过 t 次置换后的位置intn,k;// n: 置换长度, k: 加密次数charmessage[210];// 原始消息处理后长度为 ncharciphered[210];// 加密后的消息// 找出每个位置所在的循环并记录循环信息和步进位置voidfindCycle(){for(inti1;in;i){intlength1;// 记录第一步从 i 到 key[i]permutation[i][length]key[i];// 沿着置换追踪直到回到 ifor(intjkey[i];j!i;jkey[j],permutation[i][length]j)length;// permutation[i][0] 存储经过 cycle[i] 步后的位置即 i 本身permutation[i][0]permutation[i][length];cycle[i]length;}}intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);while(cinn,n){// 读取密钥1-based 索引for(inti1;in;i)cinkey[i];// 处理该数据块中的所有消息while(cink,k){// 读取消息可能包含空格cin.getline(message,210);// 计算消息的实际长度intnumber1;while(message[number]!\0)number;// 如果消息长度不足 n用空格填充while(numbern)message[number] ;message[number]\0;// 计算置换的循环分解findCycle();// 加密位置 i 的字符移动到 permutation[i][k % cycle[i]]for(inti1;in;i)ciphered[permutation[i][k%cycle[i]]]message[i];// 输出加密后的消息for(inti1;in;i)coutciphered[i];cout\n;}// 每个数据块后输出一个空行cout\n;}return0;}总结本题的核心在于置换的循环分解将置换分解为若干个不相交的循环快速幂思想kkk次置换等价于在循环中移动k mod Lk \bmod LkmodL步预处理循环信息提前计算每个位置ttt步后的目标位置关键点回顾知识点说明置换a1,a2,…,ana_1, a_2, \dots, a_na1,a2,…,an是1∼n1 \sim n1∼n的一个排列循环分解每个位置属于唯一的一个循环循环长度LLL经过LLL次置换后回到原位置加密kkk次等价于在循环中移动k mod Lk \bmod LkmodL步空格填充消息短于nnn时末尾补空格输出格式每个数据块后空行与快速幂的类比本题的核心技巧与快速幂思想类似通过预计算置换的幂次将O(k)O(k)O(k)的模拟优化为O(logk)O(\log k)O(logk)甚至O(1)O(1)O(1)因为kkk的模数很小。这种“置换幂”的技巧在密码学和组合数学中具有广泛应用。
