题解 P5343 【【XR-1】分块】

· · 题解

首先找出可用的块长集合 S。

设 f_i 为长度为 i 时的分块方案数，边界是 f_0=1。

容易得到下列转移方程：

f_i=\sum_{k \in S} f_{i-k}

时间复杂度 O(n)，可以拿到 60 分。

考虑用矩阵乘法来优化递推过程。

块长只有 100，我们先预处理出 f_0 \sim f_{100} 的值，剩下的可以通过矩阵快速幂递推。

时间复杂度 O(k^3 \log n)。

// Problem : P5343 【XR-1】分块
// Contest : Luogu Online Judge
// URL : https://www.luogu.com.cn/problem/P5343
// Author : StudyingFather
// Site : https://studyingfather.com
// Memory Limit : 125 MB
// Time Limit : 1000 ms
// Powered by CP Editor (https://github.com/cpeditor/cp-editor)

#include <cstring>
#include <iostream>
#define MOD 1000000007
using namespace std;
struct mat
{
 long long a[105][105];
 mat()
 {
  memset(a,0,sizeof(a));
 }
 mat operator*(const mat&b)const
 {
  mat ans;
  for(int k=0;k<=100;k++)
   for(int i=0;i<=100;i++)
    for(int j=0;j<=100;j++)
     ans.a[i][j]=(ans.a[i][j]+a[i][k]*b.a[k][j])%MOD;
  return ans;
 }
}f,g;
long long n;
int vis[105];
mat fpow(mat x,long long y)
{
 mat ans;
 for(int i=0;i<=100;i++)
  ans.a[i][i]=1;
 while(y)
 {
  if(y&1)ans=ans*x;
  x=x*x;
  y>>=1;
 }
 return ans;
}
int main()
{
 memset(vis,-1,sizeof(vis));
 cin>>n;
 int p;
 cin>>p;
 while(p--)
 {
  int x;
  cin>>x;
  if(vis[x]==-1)vis[x]++;
 }
 cin>>p;
 while(p--)
 {
  int x;
  cin>>x;
  if(vis[x]==0)vis[x]++;
 }
 f.a[0][0]=1;
 for(int i=1;i<=100;i++)
  for(int j=1;j<=i;j++)
   if(vis[j]==1)
    f.a[0][i]=(f.a[0][i]+f.a[0][i-j])%MOD;
 for(int i=1;i<=100;i++)
  g.a[i][i-1]=1;
 for(int i=1;i<=100;i++)
  if(vis[i]==1)
   g.a[101-i][100]=1;
 if(n<=100)cout<<f.a[0][n]<<endl;
 else cout<<(f*fpow(g,n-100)).a[0][100]<<endl;
 return 0;
}