矩阵快速幂_牛客博客

问题 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 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;

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;
}

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

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

2 1
1 0

这样身下的就简单了。

#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




*/