记录编号	160505	评测结果	AAAAAAAAAA
题目名称	1966.[HAOI 2015]数字串拆分	最终得分	100
用户昵称	Asm.Def	是否通过	通过
代码语言	C++	运行时间	1.603 s
提交时间	2015-04-28 00:13:01	内存使用	29.43 MiB

/***********************************************************************/
/**********************By Asm.Def-Wu Jiaxin*****************************/
/***********************************************************************/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <cctype>
#include <algorithm>
using namespace std;
#define SetFile(x) ( freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout) );
#define UseFREAD
#ifdef UseFREAD
#define getc() *(file_ptr++)
#define FreadLenth 5000000
char CHARPOOL[FreadLenth], *file_ptr = CHARPOOL;
#else
#define getc() getchar() 
#endif
#ifdef DEBUG
#include <sys/timeb.h>
timeb SysTp;
#endif
template<class T>inline void getd(T &x){
	char ch = getc();bool neg = false;
	while(!isdigit(ch) && ch != '-')ch = getc();
	if(ch == '-')ch = getc(), neg = true;
	x = ch - '0';
	while(isdigit(ch = getc()))x = x * 10 - '0' + ch;
	if(neg)x = -x;
}
/***********************************************************************/
const int maxn = 505, mod = 998244353;
typedef long long LL;

int n, num[maxn], len, Vect[5];

struct Mat{int A[5][5];}I, F, dp[maxn], Pow[maxn][maxn], Pow10[10];
inline Mat operator * (const Mat &a, const Mat &b){
	Mat ans;
	int i, j, k;
	unsigned long long tmps;
	for(i = 0;i < n;++i)for(j = 0;j < n;++j){
		tmps = 0;
		for(k = 0;k < n;++k)tmps += (LL)a.A[i][k] * b.A[k][j];
		ans.A[i][j] = tmps % mod;
	}

	return ans;
}

inline void operator += (Mat &a, const Mat &b){
	int i, j;
	for(i = 0;i < n;++i)for(j = 0;j < n;++j)
		a.A[i][j] = (a.A[i][j] + b.A[i][j]) % mod;
}

inline Mat power(Mat a, int t){
	Mat ans = I;
	while(t){if(t & 1)ans = ans * a;a = a * a;t >>= 1;}
	return ans;
}

inline void init(){
	int i, j, ch = getc();while(!isdigit(ch))ch = getc();
	while(isdigit(ch)){
		num[len++] = ch - '0';
		ch = getc();
	}
	getd(n);
	*Vect = 1;for(i = 1;i < n;++i)for(j = 0;j < i;++j)Vect[i] += Vect[j];
	for(i = 1;i < n;++i)F.A[i][i-1] = 1;
	for(i = 0;i < n;++i)F.A[i][n-1] = 1;
	for(i = 0;i < n;++i)I.A[i][i] = 1;
	Pow10[0] = I;Pow10[1] = F;
	for(i = 2;i < 10;++i)Pow10[i] = Pow10[i-1] * F;
	for(i = 0;i < len;++i){
		Pow[i][i+1] = Pow10[num[i]];
		for(j = i + 1;j < len;++j)Pow[i][j+1] = power(Pow[i][j], 10) * Pow10[num[j]];
	}
}

inline void work(){
	int i, j;
	dp[0] = I;
	for(i = 1;i <= len;++i)for(j = 0;j < i;++j)
		dp[i] += dp[j] * Pow[j][i];
	int Ans = 0;
	for(i = 0;i < n;++i)Ans = ((LL)dp[len].A[i][0] * Vect[i] + Ans) % mod;
	printf("%d\n", Ans);
}

int main(){

#ifdef DEBUG
	freopen("test.txt", "r", stdin);
#elif !defined ONLINE_JUDGE
	SetFile(haoi2015_str);
#endif
#ifdef UseFREAD
	fread(file_ptr, 1, FreadLenth, stdin);
#endif
	init();
	work();

#ifdef DEBUG
	printf("\n%.3lf sec \n", (double)clock() / CLOCKS_PER_SEC);
#endif
	return 0;
}