计蒜客 ACM训练联盟周赛第一场 Alice和Bob的Nim游戏矩阵快速幂

题目描述

众所周知，Alice和Bob非常喜欢博弈，而且Alice永远是先手，Bob永远是后手。

Alice和Bob面前有3堆石子，Alice和Bob每次轮流拿某堆石子中的若干个石子（不可以是0个），拿到所有石子中最后一个石子的人获胜。这是一个只有3堆石子的Nim游戏。

Bob错误的认为，三堆石子的Nim游戏只需要少的两堆的石子数量加起来等于多的那一堆，后手就一定会胜利。所以，Bob把三堆石子的数量分别设为 {k，4k，5k}（k>0）。

现在Alice想要知道，在k 小于 2^n 的时候，有多少种情况先手一定会获得胜利。

输入

一个整数n(1 \le n \le 2 \times 10^91≤n≤2×109)。

输出

输出先手胜利的可能情形数。答案对10^9+7109+7取模。

输出时每行末尾的多余空格，不影响答案正确性

样例输入

样例输出

题目来源

ACM训练联盟周赛

首先我们按照题目基本意思模拟打表可以得出

n A胜 B胜

1 0 2

2 0 4

3 2 6

4 7 9

5 17 15

6 39 25

7 88 40

8 192 64

9 408 104

从上面的数据我们不难得到B获胜的可能性的规律是第五项开始，f(n)=f(n-1)+f(n-3)+f(n-4)

这样我们从第五项开始，就可以得到所有B获胜的可能数，而A获胜的可能数就是2^n-f(n)

题目给出的n的范围可以取到10^9，所以我们在求f(n)时要用到矩阵快速幂，求2^n时用快速幂

首先写出递推式的矩阵式

| f(n-1) f(n-2) f(n-3) f(n-4) | | 1 1 0 0 |

| 0 0 0 0 | x | 0 0 1 0 |

| 0 0 0 0 | | 1 0 0 1 |

| 0 0 0 0 | | 1 0 0 0 |

写出矩阵式后直接套用模板就可以求出f(n)

#include <map>

#include <set>

#include <stack>

#include <cmath>

#include <queue>

#include <cstdio>

#include <vector>

#include <string>

#include <cstring>

#include <iostream>

#include <algorithm>

#define debug(a) cout << #a << " " << a << endl

using namespace std;

const int maxn = 1e4 + 10;

const int mod = 1e9 + 7;

typedef long long ll;

struct matrix {

    ll a[10][10];

};

matrix base, ans;

matrix multiply( matrix x, matrix y ) {

    matrix tmp;

    for( ll i = 0; i < 4; i ++ ) {

        for( ll j = 0; j < 4; j ++ ) {

            tmp.a[i][j] = 0;

            for( ll k = 0; k < 4; k ++ ) {

                tmp.a[i][j] = ( tmp.a[i][j] + x.a[i][k]*y.a[k][j] ) % mod;

            }

        }

    }

    return tmp;

}

ll f( ll n ) {

    while( n ) {

        if( n&1 ) {

            ans = multiply( ans, base );

        }

        base = multiply( base, base );

        n /= 2;

    }

    return ans.a[0][0];

}

ll qow( ll a, ll b ) {

    ll sum = 1;

    while( b ) {

        if( b&1 ) {

            sum = sum*a%mod;

        }

        a = a*a%mod;

        b /= 2;

    }

    return sum;

}

int main() {

    ll n;

    while( cin >> n ) {

        memset( base.a, 0, sizeof(base.a) );

        memset( ans.a, 0, sizeof(ans.a) );

        ans.a[0][0] = 9, ans.a[0][1] = 6;

        ans.a[0][2] = 4, ans.a[0][3] = 2;

        base.a[0][0] = base.a[0][1] = base.a[1][2] =

        base.a[2][0] = base.a[2][3] = base.a[3][0] = 1;

        //debug(qow(2,n));

        if( n == 1 || n == 2 ) {

            cout << 0 << endl;

        } else if( n == 3 ) {

            cout << 2 << endl;

        } else if( n == 4 ) {

            cout << 7 << endl;

        } else {

            cout << ( qow(2,n) - f(n-4) + mod ) % mod << endl;  //记得结果取模这里要先加mod再取模，否则会得到负值

        }

    }

    return 0;

}