LOJ10196越狱

2024-09-02 15:37:37

题目描述

原题来自：HNOI 2008

监狱有连续编号为 1 到 n 的 n 个房间，每个房间关押一个犯人。有 m 种宗教，每个犯人可能信仰其中一种。如果相邻房间的犯人信仰的宗教相同，就可能发生越狱。求有多少种状态可能发生越狱。

输入格式

输入两个整数 m 和n 。

输出格式

可能越狱的状态数，对 100003 取余。

样例

样例输入

2 3

样例输出

样例说明

所有可能的 6 种状态为：

{0,0,0}{0,0,1}{0,1,1}{1,0,0}{1,1,0}{1,1,1}。

数据范围与提示

对于全部数据，1<=m<=1e8,1<=n<=1e12。

______________________________________________

动态规划，f[i]表示到第i个房间越狱的情况有多少种。

则：f[i]=f[i-1]*m+(m^(i-1)-f[i-1])=m^(i-1)+(m-1)f[i-1]

f[i-1]*m表示前i-1个房间已经出现越狱情况，则第i个房间随便放一个宗教的犯人都会出现越狱

(m^(i-1)-f[i-1])表示前i-1个房间没有出现越狱的情况等于所有的情况减去有越狱的情况。

数据太大，需要矩阵快速幂。

[ 0 , 1 ] [m-1,0 ]

[m ,m ]

______________________________________________

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 typedef long long ll;

 4 const ll mod=100003;

 5 ll n,m;

 6 struct jz22

 7 {

 8     ll jz[2][2];

 9     jz22()

10     {

11         jz[1][0]=jz[1][1]=m;

12         jz[0][0]=m-1;

13         jz[0][1]=0;

14     }

15     jz22 operator * (jz22 const &a)const

16     {

17         jz22 b;

18         for(int i = 0;i<2;++i)

19             for(int j=0 ;j<2;++j)

20             {

21                 b.jz[i][j]=0;

22                 for(int k=0;k<2;++k)

23                     b.jz[i][j]=(b.jz[i][j]+jz[i][k]*a.jz[k][j])%mod;

24             }

25         return b;

26     }

27 };

28 jz22 pow(jz22 a,ll p)

29 {

30     if(p==1)return a;

31     jz22 ans=pow(a,p/2);

32     ans=ans*ans;

33     ans.jz[0][0]%=mod;

34     ans.jz[0][1]%=mod;

35     ans.jz[1][0]%=mod;

36     ans.jz[1][1]%=mod;

37     if(p%2)

38         {

39             ans=ans*a;

40             ans.jz[0][0]%=mod;

41             ans.jz[0][1]%=mod;

42             ans.jz[1][0]%=mod;

43             ans.jz[1][1]%=mod;

44         }

45     return ans;

46 }

47 int main()

48 {

49     cin>>m>>n;

50     n--;

51     m%=mod;

52     jz22 a,b,c;

53     b=pow(a,n);

54     cout<<b.jz[1][0];

55     return 0;

56 }

最新文章

热门文章