P5343 【XR-1】分块矩阵快速幂

题目描述

有一个长度为 nnn 的序列，xht37 现在想分块维护它。

PinkRabbit 要求他只准将序列分成 PRPRPR 种长度的块。

NaCly_Fish 要求他只准将序列分成 NFNFNF 种长度的块。

同一个人可能会要求 xht37 多次相同的块长。

xht37 想同时满足 PinkRabbit 和 NaCly_Fish 要求，只好使用两个人都允许的长度分块。

xht37 想知道，有多少种不同的分块方案，答案对 109+710 ^ 9 + 7109+7 取模。

输入格式

第一行一个正整数 nnn，表示序列的长度。

第二行一个正整数 PRPRPR，表示 PinkRabbit 要求的分块长度的种类数。

第三行 PRPRPR 个正整数，表示 PinkRabbit 要求的 PRPRPR 种分块长度。

第四行一个正整数 NFNFNF，表示 NaCly_Fish 要求的分块长度的种类数。

第五行 NFNFNF 个正整数，表示 NaCly_Fish 要求的 NFNFNF 种分块长度。

输出格式

输出一行一个整数，表示不同分块方案的种类数对 109+710 ^ 9 + 7109+7 取模的值。

样例

输入 111

输出 111

样例 111 说明

PinkRabbit 和 NaCly_Fish 都允许的块长为 {1,2}\{1,2\}{1,2}。

长度为 444 的序列分块，每块长度为 {1,2}\{1,2\}{1,2} 的方案有：

1 1 1 11\ 1\ 1\ 11 1 1 1
1 1 21\ 1\ 21 1 2
1 2 11\ 2\ 11 2 1
2 1 12\ 1\ 12 1 1
2 22\ 22 2

共 555 种。

输入 222

19260817
7
8 9 6 3 7 2 1
7
4 5 2 9 7 8 3

输出 222

859254329

数据范围与提示

设最大块长为 xxx。

对于 60%60 \%60% 的数据，1≤n≤1061 \le n \le 10 ^ 61≤n≤106，1≤PR,NF,x≤101 \le PR,NF,x \le 101≤PR,NF,x≤10，保证同一个人不会要求多次相同的块长。

对于 100%100 \%100% 的数据，1≤n≤10181 \le n \le 10 ^ {18}1≤n≤1018，1≤PR,NF,x≤1001 \le PR,NF,x \le 1001≤PR,NF,x≤100。

矩阵快速幂

不是

保证同一个人不会要求多次相同的块长吗 WA了好多发

f5=f(5-2) +f(5-3)

矩阵快速幂构造矩阵方法第一行就是 0 1 1 0 0

1 0 0 0 0

0 1 0 0 0

. .... .........

0 0 0 0 1

洛谷 760ms

xht37的OJ 1093ms卡常-----

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;

ll mod=1e9+7;
ll flag[105];
ll num[105];
ll exi[105];
ll ma=100;
ll p[105][105];
ll tp2[105][105];
ll ans[105];
ll tp[105];
void f1()
{

    for(ll i=1; i<=ma; i++)
    {
        tp[i]=0;
        for(ll j=1; j<=ma; j++)
        {
            tp[i]=(tp[i]+p[i][j]*ans[j])%mod;

        }
    }
    for(ll i=1; i<=ma; i++)
        ans[i]=tp[i];
}
void f2()
{
    for(ll i=1; i<=ma; i++)
    {
        for(ll j=1; j<=ma; j++)
        {
            tp2[i][j]=0;
            for(ll k=1; k<=ma; k++)
            {
                tp2[i][j]=(tp2[i][j]+p[i][k]*p[k][j])%mod;
            }
        }
    }
    for(ll i=1; i<=ma; i++)
    {
        for(ll j=1; j<=ma; j++)
        {
            p[i][j]=tp2[i][j];
        }
    }
}
void print()
{
    for(ll i=1; i<=ma; i++)
    {
        for(ll j=1; j<=ma; j++)
        {
            printf("%lld ",p[i][j]);
        }
        printf("\n");
    }
    printf("\n");

    for(ll i=1;i<=ma;i++)
        printf("%lld ",ans[i]);
    printf("\n");
     printf("\n");

}
ll flag2[105];
int main()
{
    ll n;
    ll cnt=0;
    scanf("%lld",&n);
    memset(p,0,sizeof(p));
    memset(flag,0,sizeof(flag));
    memset(flag2,0,sizeof(flag2));
    memset(num,0,sizeof(num));
    ll l1,l2,x;
    scanf("%lld",&l1);
    for(ll i=0; i<l1; i++)
    {
        scanf("%lld",&x);flag[x]=1;
    }

    scanf("%lld",&l2);
    for(ll i=0; i<l2; i++)
    {
        scanf("%lld",&x);
        flag2[x]=1;
    }

    for(ll i=0; i<105; i++)
        if(flag[i]&&flag2[i])
            num[cnt]=i,cnt++;
    for(ll i=0; i<cnt; i++)
        p[1][num[i]]=1;

    for(ll i=2; i<=ma; i++)
    {
        p[i][i-1]=1;
    }
    memset(ans,0,sizeof(ans));
    ans[1]=1;
    while(n)
    {
        if(n&1)
            f1();
        //print();
        f2();
        n>>=1;
    }
    printf("%lld\n",ans[1]%mod);
}

P5343 【XR-1】分块 矩阵快速幂

P5343 【XR-1】分块矩阵快速幂