【HAOI2015】bzoj4037 数字串拆分

本文主要是介绍【HAOI2015】bzoj4037 数字串拆分，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description
你有一个长度为n的数字串。定义f(S)为将S拆分成若干个1~m的数的和的方案数，比如m=2时，f(4)=5，分别为4=1+
1+1+1你可以将这个数字串分割成若干个数字（允许前导0），将他们加起来，求f，并求和。比如g(123)=f(1+2+3)
+f(1+23)+f(12+3)+f(123)。已知字符串和m后求答案对998244353（7×17×223+1，一个质数）取模后的值。 Input

第一行输入一个字符串，第二行输入m Output

仅输出一个数表示答案

构造 $m\times m$ 的转移矩阵 $A$ 满足 $a_{i,j}=1$ 当且仅当 $j=1$ 或 $i+1=j$ 。可以发现， $f_n={A^n}_{1,1}$ 。
接下来考虑在字符串上dp，但是发现如果直接做不满足乘法分配律，也就是不能写成 $dp_i=\sum_{j=0}^{i-1}dp_j*f_{j+1..i}$ 。但是因为 $f$ 可以写成矩阵的幂的形式，这样就可以提取公因式，满足了分配律。
在算一段区间的时候，可以预处理出来 $x*10^y$ 的答案，然后直接相乘，注意不要写成 $O(n^3)$ 。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define LL long long
const int mod=998244353;
int m,n;
char s[510];
struct mat
{int a[6][6];void init(){for (int i=1;i<=m;i++)for (int j=1;j<=m;j++)a[i][j]=(j==1||i+1==j);}void I(){for (int i=1;i<=m;i++)for (int j=1;j<=m;j++)a[i][j]=(i==j);}mat operator + (const mat &mm) const{mat ret;for (int i=1;i<=m;i++)for (int j=1;j<=m;j++)ret.a[i][j]=(a[i][j]+mm.a[i][j])%mod;return ret;}mat operator * (const mat &mm) const{mat ret;for (int i=1;i<=m;i++)for (int j=1;j<=m;j++){ret.a[i][j]=0;for (int k=1;k<=m;k++)ret.a[i][j]=(ret.a[i][j]+(LL)a[i][k]*mm.a[k][j]%mod)%mod;}return ret;}mat pow(int x){mat ret,base;ret.I();for (int i=1;i<=m;i++)for (int j=1;j<=m;j++)base.a[i][j]=a[i][j];while (x){if (x&1) ret=ret*base;base=base*base;x>>=1;}return ret;}
}f[10][510],dp[510],t;
mat cal(int l,int r)
{mat ret;ret.I();for (int i=l;i<=r;i++)ret=ret*f[s[i]-'0'][r-i];return ret;
}
int main()
{scanf("%s",s+1);n=strlen(s+1);scanf("%d",&m);for (int i=0;i<=n;i++) f[0][i].I();f[1][0].init();for (int i=1;i<=n;i++) f[1][i]=f[1][i-1].pow(10);for (int i=2;i<=9;i++)for (int j=0;j<=n;j++)f[i][j]=f[i-1][j]*f[1][j];dp[0].I();for (int i=1;i<=n;i++){t=f[s[i]-'0'][0];for (int j=i-1;j>=0;j--){dp[i]=dp[i]+dp[j]*t;if (j) t=t*f[s[j]-'0'][i-j];}}printf("%d\n",dp[n].a[1][1]);
}