2016计蒜之道－初赛－第四场－B－遗失的支付宝密码

描述

某用户忘记了支付宝的登录密码，他只记得自己的密码满足以下几个条件：
密码中最多有 m 种不同的字符；
密码的最大长度为 n，但不能为空；
密码的任意一个前缀都 不是 一个 square。>>>详情请点击

题解

一道找规律的问题，逐位考虑情况。如第二组测试数据：4，5。
一共四位，先来考虑一位的，有5种情况；再来考虑两位的，因为需要避免square的出现，所以需要第二位和第一位不同，那么就有5 x 5 - 5 = 20种情况；接着考虑三位，第三位因为是基于前两位来填数字，所以无论填几都是满足的，所以是20 x 5 = 100种情况；四位的情况是再在三位的情况下填一位，因为要避免第三和第四位的组合和前两位的组合相同，所以是需要减去前两位存在的组合情况，也就是说是100 x 5 - 20 = 480种情况。加在一起也就是605种情况，大概就是这个样子。
大数据范围的情况暂时没有什么好的思路解决，2^32次方是0xffffffff+1，怎么取模是个问题，需要思考思考。

代码C++

#include <iostream>

typedef long long LL;
LL MOD = 4294967296;
LL n, m;
LL A[101];

int main(int argc, const char * argv[])
{
    while (std::cin >> n >> m)
    {
        A[0] = 1;
        for (int i = 1; i <= n; i++)
        {
            if (i % 2)
            {
                A[i] = A[i - 1] * m;
            }
            else
            {
                A[i] = A[i - 1] * m - A[i / 2];
            }
        }
        LL ans = 0;
        for (int i = 1; i <= n; i++)
        {
            ans = (ans + A[i]) % MOD;
        }
        std::cout << ans << std::endl;
    }

    return 0;
}