当前位置：网站首页>矩阵快速幂

矩阵快速幂

2022-07-15 10:27:00 【51CTO】

问题 G: 强
时间限制: 1 Sec 内存限制: 128 MB
[提交] [状态]
题目描述
Lh：粉兔你教我一下抽屉原理吧

Clz：就是给你一个长度为 n 的序列，每个数只能取 0,1,2，那你连续取三个数必然有两个相等……

Lh：等等你梭啥，再说一遍

Clz：……emmm 当我没说

Marser：就是一个序列，对于每一个连续三元组都要满足其中至少有两个相等

现在粉兔问你：有多少个长度为 n 的序列满足粉兔的要求？请对 19260817 取模。
输入
一行一个正整数n（3≤n≤1018）。
输出
一行一个整数，含义如题。
样例输入 Copy
4
样例输出 Copy
51
提示
51 种序列如下：
[0,0,0,0],[0,0,0,1],[0,0,0,2],[0,0,1,0],[0,0,1,1],[0,0,2,0],[0,0,2,2],[0,1,0,0],[0,1,0,1],[0,1,1,0],[0,1,1,1],[0,1,1,2],[0,2,0,0],[0,2,0,2],[0,2,2,0],[0,2,2,1],[0,2,2,2],[1,0,0,0],[1,0,0,1],[1,0,0,2],[1,0,1,0],[1,0,1,1],[1,1,0,0],[1,1,0,1],[1,1,1,0],[1,1,1,1],[1,1,1,2],[1,1,2,1],[1,1,2,2],[1,2,1,1],[1,2,1,2],[1,2,2,0],[1,2,2,1],[1,2,2,2],[2,0,0,0],[2,0,0,1],[2,0,0,2],[2,0,2,0],[2,0,2,2],[2,1,1,0],[2,1,1,1],[2,1,1,2],[2,1,2,1],[2,1,2,2],[2,2,0,0],[2,2,0,2],[2,2,1,1],[2,2,1,2],[2,2,2,0],[2,2,2,1],[2,2,2,2]。

思路：矩阵快速幂

       
       #include <map>
       
       #include <queue>
       
       #include <string>
       
       #include<iostream>
       
       #include<stdio.h>
       
       #include<string.h>
       
       #include <algorithm>
       
       #include <math.h>
       
       typedef 
       
       long 
       
       long 
       
       ll;
       
       using 
       
       namespace 
       
       std;
       
       const 
       
       int 
       
       maxn
       
       =
       
       2e5
       
       +
       
       1010;
       
       #define
       
       #define
       
       #define
       
       const 
       
       int 
       
       mod
       
       =
       
       19260817;
       
       const 
       
       int 
       
       MOD
       
       =
       
       10007;
       
       inline 
       
       int 
       
       read() {
       
       int 
       
       x
       
       =
       
       0;
       
       bool 
       
       t
       
       =
       
       false;
       
       char 
       
       ch
       
       =
       
       getchar();
       
       while((
       
       ch
       
       <
       
       '0'
       
       ||
       
       ch
       
       >
       
       '9')
       
       &&
       
       ch
       
       !=
       
       '-')
       
       ch
       
       =
       
       getchar();
       
       if(
       
       ch
       
       ==
       
       '-')
       
       t
       
       =
       
       true,
       
       ch
       
       =
       
       getchar();
       
       while(
       
       ch
       
       <=
       
       '9'
       
       &&
       
       ch
       
       >=
       
       '0')
       
       x
       
       =
       
       x
       
       *
       
       10
       
       +
       
       ch
       
       -
       
       48,
       
       ch
       
       =
       
       getchar();
       
       return 
       
       t
       
       ?-
       
       x:
       
       x;
       
}
       
       priority_queue
       
       <
       
       ll , 
       
       vector
       
       <
       
       ll
       
       > , 
       
       greater
       
       <
       
       ll
       
       > 
       
       > 
       
       mn;
       
       //上 小根堆 小到大
       
       priority_queue
       
       <
       
       ll , 
       
       vector
       
       <
       
       ll
       
       > , 
       
       less
       
       <
       
       ll
       
       > 
       
       > 
       
       mx;
       
       //下 大根堆 大到小
       
       //map<ll,ll>mp;
       
       ll 
       
       n,
       
       m,
       
       t,
       
       l,
       
       r,
       
       p;
       
       ll 
       
       sum,
       
       ans,
       
       res,
       
       cnt,
       
       flag;
       
       struct 
       
       Mat
       
{
       
       ll 
       
       m[
       
       101][
       
       101];
       
};
       
       //存储结构体
       
       Mat 
       
       a,
       
       e; 
       
       //a是输入的矩阵，e是输出的矩阵
       
       Mat 
       
       Mul(
       
       Mat 
       
       x,
       
       Mat 
       
       y)
       
{
       
       Mat 
       
       c;
       
       for(
       
       int 
       
       i
       
       =
       
       1;
       
       i
       
       <=
       
       n;
       
       ++
       
       i){
       
       for(
       
       int 
       
       j
       
       =
       
       1;
       
       j
       
       <=
       
       n;
       
       ++
       
       j){
       
       c.
       
       m[
       
       i][
       
       j] 
       
       = 
       
       0;
       
        }
       
    }
       
       for(
       
       int 
       
       i
       
       =
       
       1;
       
       i
       
       <=
       
       n;
       
       ++
       
       i){
       
       for(
       
       int 
       
       j
       
       =
       
       1;
       
       j
       
       <=
       
       n;
       
       ++
       
       j){
       
       for(
       
       int 
       
       k
       
       =
       
       1;
       
       k
       
       <=
       
       n;
       
       ++
       
       k){
       
       c.
       
       m[
       
       i][
       
       j] 
       
       = 
       
       c.
       
       m[
       
       i][
       
       j]
       
       %
       
       mod 
       
       + 
       
       x.
       
       m[
       
       i][
       
       k]
       
       *
       
       y.
       
       m[
       
       k][
       
       j]
       
       %
       
       mod;
       
            }
       
        }
       
    }
       
       return 
       
       c;
       
}
       
       Mat 
       
       pow(
       
       Mat 
       
       x,
       
       ll 
       
       y)
       
       //矩阵快速幂
       
{
       
       Mat 
       
       ans;
       
       for(
       
       int 
       
       i
       
       =
       
       1;
       
       i
       
       <=
       
       n;
       
       i
       
       ++){
       
       ans.
       
       m[
       
       i][
       
       i]
       
       =
       
       1;
       
    }
       
       while(
       
       y){
       
       if(
       
       y
       
       &
       
       1) 
       
       ans 
       
       = 
       
       Mul(
       
       ans,
       
       x);
       
       x 
       
       = 
       
       Mul(
       
       x,
       
       x);
       
       y
       
       >>=
       
       1;
       
    }
       
       return 
       
       ans;
       
}
       
       int 
       
       main() {
       
       sf(
       
       "%lld",
       
       &
       
       m);
       
       a.
       
       m[
       
       1][
       
       1]
       
       =
       
       2;
       
       a.
       
       m[
       
       1][
       
       2]
       
       =
       
       1;
       
       a.
       
       m[
       
       2][
       
       1]
       
       =
       
       1;
       
       a.
       
       m[
       
       2][
       
       2]
       
       =
       
       0;
       
       n
       
       =
       
       2;
       
       e
       
       =
       
       pow(
       
       a,
       
       m
       
       -
       
       1);
       
       cout
       
       <<(
       
       e.
       
       m[
       
       1][
       
       1]
       
       +
       
       e.
       
       m[
       
       1][
       
       2])
       
       *
       
       3
       
       %
       
       mod
       
       <<
       
       endl;
       
       /* 
       
       [0,0,0,0],[0,0,0,1],[0,0,0,2],[0,0,1,0],[0,0,1,1],
       
       [0,0,2,0],[0,0,2,2],[0,1,0,0],[0,1,0,1],[0,1,1,0],
       
       [0,1,1,1],[0,1,1,2],[0,2,0,0],[0,2,0,2],[0,2,2,0],
       
       [0,2,2,1],[0,2,2,2],
       
       [1,0,0,0],[1,0,0,1],[1,0,0,2],[1,0,1,0],[1,0,1,1],
       
       [1,1,0,0],[1,1,0,1],[1,1,1,0],[1,1,1,1],[1,1,1,2],
       
       [1,1,2,1],[1,1,2,2],[1,2,1,1],[1,2,1,2],[1,2,2,0],
       
       [1,2,2,1],[1,2,2,2],
       
       [2,0,0,0],[2,0,0,1],[2,0,0,2],[2,0,2,0],[2,0,2,2],
       
       [2,1,1,0],[2,1,1,1],[2,1,1,2],[2,1,2,1],[2,1,2,2],
       
       [2,2,0,0],[2,2,0,2],[2,2,1,1],[2,2,1,2],[2,2,2,0],
       
       [2,2,2,1],[2,2,2,2]。*/
       
       return 
       
       0;
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.

推这个东西的过程可以和大家分享一下
其实也没什么就是用计算机跑for循环毕竟计算机算大数据时比我算的快而准。

最后得到一组数 21 51 123 197…
都是 3的倍数除以三得到
7 17 41 99 …
可以得到 a_n=2*a_n-1+a_n-2;
当时忘了怎么用矩阵快速幂了（也就是不会，嘻嘻~~）。
这样我们就可以构造了。我也不太懂是怎么构造的，这个简单还是巧了我一下凑出来了，就是

这样身下的就简单了。

       
       #include <map>
       
#include <queue>
       
#include <string>
       
#include<iostream>
       
#include<stdio.h>
       
#include<string.h>
       
#include <algorithm>
       
#include <math.h>
       
typedef long long ll;
       
using namespace std;
       
const int maxn=2e5+1010;
       
#define inf 0x3f3f3f3f
       
#define sf scanf
       
#define pf printf
       
const int mod=19260817;
       
const int MOD=10007;
       
inline int read() {
       
  int x=0;
       
  bool t=false;
       
  char ch=getchar();
       
  while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
       
  if(ch=='-')t=true,ch=getchar();
       
  while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
       
  return t?-x:x;
       
}
       
priority_queue<ll , vector<ll> , greater<ll> > mn;//上  小根堆    小到大
       
priority_queue<ll , vector<ll> , less<ll> > mx;//下    大根堆   大到小
       
//map<ll,ll>mp;
       
ll n,m,t,l,r,p;
       
ll sum,ans,res,cnt,flag;
       
ll a[maxn];
       
int main (){
       
  for(int o=1;o<=3;o++) 
       
  for(int i=1;i<=3;i++)
       
    for(int j=1;j<=3;j++)
       
    {
       
      for(int k=1;k<=3;k++)
       
        for(int h=1;h<=3;h++)
       
          for(int y=1;y<=3;y++)
       
          if((o!=i&&o!=j&&i!=j)||(i!=j&&i!=k&&j!=k)||(j!=k&&j!=h&&h!=k)||(k!=h&&h!=y&&k!=y))continue;
       
          else  
       
          a[++cnt]=i*10000+j*1000+k*100+h*10+y+o*100000;
       
  }
       
  sort(a+1,a+1+cnt);
       
  cout<<cnt<<endl<<endl;
       
  for(int i=1;i<=cnt;i++)
       
  {
       
    cout<<a[i]<<" ";
       
    if(i%5==0) cout<<endl;
       
  }
       
  return 0;
       
}
       
/*
       
111  112  113  121  122
       
131  133  211  212  221
       
222  223  232  233  311  
       
313  322  323  331  332  
       
333
       
*/
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.

原网站

版权声明
本文为[51CTO]所创，转载请带上原文链接，感谢
https://blog.51cto.com/u_15719209/5474527

当前位置：网站首页>矩阵快速幂

矩阵快速幂

边栏推荐

猜你喜欢

随机推荐