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

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

阅读量：5738 次

发布时间：2019-06-18

本文共 2232 字，大约阅读时间需要 7 分钟。

题目描述

众所周知，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( $\le n \le 2 \times 10^91≤n≤2×109)。$

输出

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

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

样例输入

样例输出

题目来源

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

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 #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #define debug(a) cout << #a << " " << a << endlusing 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;}

转载于:https://www.cnblogs.com/l609929321/p/9316864.html

你可能感兴趣的文章