拆分的情况下，发现f数组本身并不是很好递推。
因为f(123)=f(123)/f(12+3)/f(1+2+3)。
然后考虑f可以怎么表示f(n)=a0*M^n M为转移矩阵。
然后发现 f(x+y)=a0*M(x+y)， 所以只需要对M矩阵进行DP即可。
这样子每一个位置就可以表示为若干转移矩阵的和，然后就可以利用矩阵的相乘进行递推。
最后直接用原向量乘上转移矩阵即可。
#include#include #include #include using namespace std; #define ll long long#define F(i,j,k) for (ll i=j;i<=k;++i)#define D(i,j,k) for (ll i=j;i>=k;--i)const ll md=998244353; ll m,l;char s[505]; struct matrix{ ll x[6][6]; void init(){memset(x,0,sizeof x);} void build1(){ init(); x[1][1]=1; } void build2(){ init(); F(i,1,m) x[i][1]=1; F(i,1,m-1) x[i][i+1]=1; } void build3(){ init(); F(i,1,m) x[i][i]=1; } matrix operator * (matrix b) { matrix ret; ret.init(); F(i,1,m) F(j,1,m) { F(k,1,m) ret.x[i][j]=ret.x[i][j]+x[i][k]*b.x[k][j]; ret.x[i][j]%=md; } return ret; } matrix operator + (matrix b) { matrix ret; ret.init(); F(i,1,m) F(j,1,m) ret.x[i][j]=((ll)x[i][j]+(ll)b.x[i][j])%md; return ret; }}dp[505],one,c[11][501],turn,now,ans; int main(){ scanf("%s",s+1);l=strlen(s+1); scanf("%lld",&m); F(i,0,l) dp[i].init(); one.build1(); turn.build2(); c[0][0].build3(); F(i,1,10) c[i][0]=c[i-1][0]*turn; F(i,1,l-1) { c[0][i]=c[0][i-1]; c[1][i]=c[10][i-1]; F(j,2,10) { c[j][i]=c[j-1][i]*c[10][i-1]; } } dp[0].build3(); F(i,1,l) { now.build3(); D(j,i,1) { now=now*c[s[j]-'0'][i-j]; dp[i]=dp[i]+dp[j-1]*now; } } ans=dp[l]*one; printf("%lld\n",ans.x[1][1]);}