递推与递归

费解的开关

题目描述

你玩过“拉灯”游戏吗？

25 盏灯排成一个 5×5 的方形。

每一个灯都有一个开关，游戏者可以改变它的状态。

每一步，游戏者可以改变某一个灯的状态。

游戏者改变一个灯的状态会产生连锁反应：和这个灯上下左右相邻的灯也要相应地改变其状态。

我们用数字 1 表示一盏开着的灯，用数字 0 表示关着的灯。

下面这种状态

10111
01101
10111
10000
11011

在改变了最左上角的灯的状态后将变成：

01111
11101
10111
10000
11011

再改变它正中间的灯后状态将变成：

01111
11001
11001
10100
11011

给定一些游戏的初始状态，编写程序判断游戏者是否可能在 6 步以内使所有的灯都变亮。

输入格式

第一行输入正整数 n，代表数据中共有 n 个待解决的游戏初始状态。

以下若干行数据分为 n 组，每组数据有 5 行，每行 5 个字符。

每组数据描述了一个游戏的初始状态。

各组数据间用一个空行分隔。

输出格式

一共输出 n 行数据，每行有一个小于等于 66 的整数，它表示对于输入数据中对应的游戏状态最少需要几步才能使所有灯变亮。

对于某一个游戏初始状态，若 6 步以内无法使所有灯变亮，则输出 ?1。

问题分析

暴力打表

对于这道题，比较容易想到的是利用 BFS，从目标状态（所有灯都亮）开始，搜索经过 6 步“拉灯”所能到达的所有状态，判断初始状态是否包括在内。

对于暴力打表，可以得出时间复杂度应该是 $O(25^{6}N)$，其中 N 为待解决的游戏初始状态。

递推求解

仔细观察可以发现，灯的亮灭与拉灯的次序无关，只与灯的上下左右以及自身被按下的次数有关

首先确定第一行的开关状态，然后逐渐递推锁定后续行的开关状态。

假设第一层已经固定，即不能再对第一层的开关进行任何的拉灯操作。要让第一层的灯全亮，只能通过第二层的开关进行操作。

因此，第 i+1 层的开关操作的目的是为了让第 i 层的开关全亮

当最后一层的操作进行完毕，前面层数的灯一定处于全亮状态，只需关注最后一层是否全亮。若最后一层没有全亮，则说明，对于该第一层的开关操作，最终无法得出所有灯全亮的操作。

对于每一种的第一层开关操作，我们都可以通过上述方式，判断最终是否能得到灯全亮的状态。

通过先固定第一层的开关操作，我们就可以确定初始状态，并通过递推确定后续层的开关操作，进而判断对于任意一种初始状态，能否到达灯全亮的最终状态。

程序代码

#include <iostream>
#include <cstring>
using namespace std;

const int N = 6;

char g[N][N], bg[N][N];  // 初始状态
int dx[5] = {-1, 0, 0, 1, 0}, dy[5] = {0, -1, 0, 0, 1};

// 按下(x, y)开关，对应产生的变化
void turn(int x, int y)
{
    for(int i = 0; i < 5; i++) {
        int a = x + dx[i];
        int b = y + dy[i];
        // 越界
        if(a < 0 || a >= 5 || b < 0 || b >= 5)  continue;
        g[a][b] ^= 1;  // 开关变化本质是个异或
    }
}

int main()
{
    int t;
    cin >> t;
    while( t-- ) {
        for(int i = 0; i < 5; i++) {
            for(int j = 0; j < 5; j++){
                cin >> bg[i][j];
            }
        }
        int res = 10;
        // 第一行所有可能的情况是2^5
        for(int op = 0; op < 32; op++) {
            int cnt = 0;
            memcpy(g, bg, sizeof(g));
            // 对第一行进行的操作用5位二进制表示
            // 1表示按下，0表示不按
            for(int i = 0; i < 5; i++) {
                // 固定第一行的操作
                if( op >> i & 1 ) {
                    turn(0, i);
                    cnt++;
                }
            }
            
            // 递推后续行的操作
            for(int i = 0; i < 4; i++) {
                for(int j = 0; j < 5; j++) {
                    // 上一行i的操作固定，要将0变成1，只能在第i+1行进行
                    if(g[i][j] == '0') {
                        turn(i + 1, j);
                        cnt++;
                    }
                }
            }
            // 前四行已经全亮，只需要检查最后一行是否全亮
            bool success = true;
            for(int i = 0; i < 5; i++) {
                if(g[4][i] == '0') {
                    success = false;
                    break;
                }
            }
            if(success && res > cnt) {
                res = cnt;
            }
        }
        if(res > 6)  res = -1;
        cout << res << endl;
    }
    return 0;
}

复杂度分析

时间复杂度为 $O(2^5\times 5\times 5N)$

• 第一行的开关状态：$2^5$
• 上一行锁定，下一行状态的递推：5
• 需要检查的行数：5
• N：待解决的游戏初始状态。

约数之和

题目描述

假设现在有两个自然数 A 和 B，S 是 $A^B$ 的所有约数之和。

请你求出 S mod 9901 的值是多少。

前置知识

设一个自然数 $N=P_1^{{\alpha }_1}{P}_2^{{\alpha }_2}...P_k^{{\alpha }_k}$

• 约数个数：$({\alpha }_1+1)({\alpha }_2+1)...({\alpha }_k+1)$
• 约数之和：$(1+P_1+P_1^2+...+P_1^{{\alpha }_1})(1+P_2+P_2^2+...+P_2^{{\alpha }_2})(1+P_k+P_k^2+...+P_k^{{\alpha }_k})$

问题分析

将自然数 A 分解成 $P_1^{{\alpha }_1}{P}_2^{{\alpha }_2}...P_k^{{\alpha }_k}$

则 $A^B=P_1^{{\alpha }_{1}B}{P}_2^{{\alpha }_{2}B}...P_k^{{\alpha }_{k}B}$

所以约数之和为：$(1+P_1+P_1^2+...+P_1^{{\alpha }_{1}B})(1+P_2+P_2^2+...+P_2^{{\alpha }_{2}B})(1+P_k+P_k^2+...+P_k^{{\alpha }_{k}B})$

上述的约数之和，核心在于计算等比数列的求和。由于数据量很大，直接套用等比数列求和公式可能爆int。因此，可以采用通用的分治递归策略对等比数列进行求和。

记 $sum(P,k)=(P^0+P^1+P^2+...+P^{k?1})$

• 若 k 是偶数：可以将区间分成两部分，即sum(P, k) = sum(P, k/2) + P^(k/2)*sum(P, k/2)
• 若 k 是奇数：则 k -1 为偶数，则可以从 k - 1 推导过来，即sum(P, k) = sum(P, k-1) + P^(k-1)

程序代码

#include <iostream>
using namespace std;

const int MOD = 9901;

// 快速幂计算a^k
int qmi(int a, int k)
{
    int res = 1;
    a %= MOD;
    while( k ) {
        if(k & 1)  res = res * a % MOD;
        a = a * a % MOD;
        k >>= 1;
    }
    return res;
}

// 求约数之和的其中一项（等比数列）
// 1 + p + p^2 + ... + p^(k-1)
int sum(int p, int k)
{
    if( k == 1 )  return 1;
    if(k % 2 == 0)  return (1 + qmi(p, k / 2)) * sum(p, k / 2) % MOD;
    return (sum(p, k - 1) + qmi(p, k - 1)) % MOD;
}

int main()
{
    int a, b;
    cin >> a >> b;
    int res = 1;
    // 对A分解质因数
    for(int i = 2; i * i <= a; i++) {
        if(a % i == 0) {
            int s = 0;
            while(a % i == 0) {
                a /= i;
                s++;
            }
            // 约数和公式
            res = res * sum(i, b * s + 1) % MOD;
        }
    }
    // 分解质因数收尾
    if(a > 1)  res = res * sum(a, b + 1) % MOD;
    if(a == 0)  res = 0;
    cout << res << endl;
    return 0;
}