1042 Shuffling Machine

快速幂练习

Shuffling is a procedure used to randomize a deck of playing cards. Because standard shuffling techniques are seen as weak, and in order to avoid “inside jobs” where employees collaborate with gamblers by performing inadequate shuffles, many casinos employ automatic shuffling machines. Your task is to simulate a shuffling machine.

The machine shuffles a deck of 54 cards according to a given random order and repeats for a given number of times. It is assumed that the initial status of a card deck is in the following order:

S1, S2, ..., S13, 
H1, H2, ..., H13, 
C1, C2, ..., C13, 
D1, D2, ..., D13, 
J1, J2

where “S” stands for “Spade”, “H” for “Heart”, “C” for “Club”, “D” for “Diamond”, and “J” for “Joker”. A given order is a permutation of distinct integers in [1, 54]. If the number at the i-th position is j, it means to move the card from position i to position j. For example, suppose we only have 5 cards: S3, H5, C1, D13 and J2. Given a shuffling order {4, 2, 5, 3, 1}, the result will be: J2, H5, D13, S3, C1. If we are to repeat the shuffling again, the result will be: C1, H5, S3, J2, D13.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive integer K (≤20) which is the number of repeat times. Then the next line contains the given order. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print the shuffling results in one line. All the cards are separated by a space, and there must be no extra space at the end of the line.

Sample Input:

2
36 52 37 38 3 39 40 53 54 41 11 12 13 42 43 44 2 4 23 24 25 26 27 6 7 8 48 49 50 51 9 10 14 15 16 5 17 18 19 1 20 21 22 28 29 30 31 32 33 34 35 45 46 47

Sample Output:

S7 C11 C10 C12 S1 H7 H8 H9 D8 D9 S11 S12 S13 D10 D11 D12 S3 S4 S6 S10 H1 H2 C13 D2 D3 D4 H6 H3 D13 J1 J2 C1 C2 C3 C4 D1 S5 H5 H11 H12 C6 C7 C8 C9 S2 S8 S9 H10 D5 D6 D7 H4 H13 C5

如果将每种牌组的状态视为一个54维矩阵M,将每次shuffle都视作一次线性变换(比如,行变换),很显然是一个矩阵经过n次线性变换之后变成另一个矩阵的过程,而这线性变换的规则可以视作右乘(因为是行变换)某特定矩阵ORI。则原题重点转化为求M*ORIn 的值。

虽然本题的数据量不大,但是作为练习可以尝试写一下快速幂。

#include <cstdio>
#include <iostream>
#define CARDN 54 // 防止魔数,也便于小样本调试时修改
using namespace std;
int ori[CARDN][CARDN];                   // 矩阵快速幂变化矩阵
int m[CARDN][CARDN];                     // 矩阵快速幂目标矩阵
string cards[CARDN];                     // 数字到卡牌名的映射
string f[5] = {"S", "H", "C", "D", "J"}; // 花色
void init()                              // 初始化cards数组,将花色和数字进行拼接
{
    for (int i = 0; i < CARDN; i++)
    {
        string s = f[i / 13];
        char p[3];
        sprintf(p, "%d", i % 13 + 1);
        s.append(p);
        cards[i] = s;
    }
}
void mMul(int a[][CARDN], int b[][CARDN]) // 方阵乘法,相当于A = A*B,注意这里二维数组传参的写法
{
    int c[CARDN][CARDN]; // 存放临时结果的矩阵,注意这里不能直接用A矩阵接收结果
    for (int i = 0; i < CARDN; i++)
    {
        for (int j = 0; j < CARDN; j++)
        {
            c[i][j] = 0;
            for (int k = 0; k < CARDN; k++)
            {
                c[i][j] += a[i][k] * b[k][j];
            }
            // cout << a[i][j] << " ";
            // cout << "\n";
        }
    }
    for (int i = 0; i < CARDN; i++)
    {
        for (int j = 0; j < CARDN; j++)
        {
            a[i][j] = c[i][j]; // 将结果复制回A矩阵
        }
    }
}

void fastPower(int n) // 矩阵快速幂,快速幂实际上就是二进制分解
{
    while (n != 0)
    {
        if (n % 2)
        {
            mMul(m, ori);
        }
        mMul(ori, ori);

        n = n >> 1;
    }
}

int main()
{
    init();
    int n;
    cin >> n;
    for (int i = 0; i < CARDN; i++) // 从输入变换规则到ori矩阵的映射
    {
        int l;
        cin >> l;
        ori[l - 1][i] = 1;
        m[i][i] = 1;
    }
    fastPower(n);

    // for (int i = 0; i < n; i++)
    // {
    //     mMul(m, ori);    // 非快速幂版本
    // }
    for (int i = 0; i < CARDN; i++)
    {
        for (int j = 0; j < CARDN; j++)
        {
            if (m[i][j] == 1)
            {
                cout << cards[j];
                if (i != CARDN - 1)
                {
                    cout << " ";
                }
            }
        }
    }
    return 0;
}
Subscribe
提醒
guest
0 评论
Inline Feedbacks
View all comments