【题解】U281338 分书

自创题题目解析

考虑可以先去看Sam数

从标签我们可以知道，需要使用矩阵加速

考虑这道题一眼看出是一道DP题（毕竟是熟悉的背包加了一个上限）

再看每一种人的人数\(10^9\)！(蒙了)

我们从数据范围知道该去用一个优化算法（或者是结论题），那到底是什么呢？

组合数学？好像有一点难，出题人好像故意把模数设成了\(~998244354~\)(到底能不能做给大家留下思考空间)

怎么办，这时你发现，它和Sam数这道题一样，都没有上限！！！

这矩阵好像和Sam数差不多耶，只要构造一个\(m \times m\)的递推矩阵即可。

但是\(~n~\)种人怎么搞？

……思考中

当然是直接乘起来完事啦！

下面是code:

#include<bits/stdc++.h> 
using namespace std;
typedef long long ll;
const ll NN = 3e2 + 8,MOD = 998244354;
inline ll read(){
	register ll res = 0,flag = 1;
	register char c = getchar();
	while(!isdigit(c)){
		if(c == '-')flag = -1;c = getchar();
	}
	while(isdigit(c)){
		res = res * 10 + c - '0';
		c = getchar();
	}
	return res * flag;
}//快读
inline ll calc(ll x,ll y){
	ll r = x + y;
	return r - (r >= MOD ? MOD : 0);
}//取模意义下加法加速
ll n,m;
ll A[NN],B[NN];
struct Matrix{
	ll a[NN][NN];
	void clear(){
		memset(a,0,sizeof(a));
	}//清空矩阵
	Matrix operator * (Matrix &x){
		Matrix c;c.clear();
		for(int l = 0; l <= m; ++l){
			for(int i = 0; i <= m; ++i){
				for(int j = 0; j <= m; ++j){
					c.a[i][j] = calc(c.a[i][j],a[i][l] * x.a[l][j] % MOD);
				}
			}
		}
		return c;
	}//矩阵乘法
	void get(int x){
		for(int i = 0; i <= m; ++i){
			for(int j = i; j >= max(0,i-x); --j){
				a[j][i] = 1;
			}
		}
	}//构造递推矩阵
	void init(){
		for(int i = 0; i <= m; ++i)a[i][i] = 1;
	}//构造单位矩阵
}ans,ori,res,cal;
Matrix ksm(Matrix &x,ll k){
	cal = x;
	res.clear();res.init();
	while(k){
		if(k&1)res = res * cal;
		cal = cal * cal;
		k >>= 1;
	}
	return res;
}//矩阵快速幂
ll r;
int main(){
	n = read(),m = read();
	ans.a[0][0] = 1;
	for(int i = 1; i <= n; ++i)A[i] = read();
	for(int i = 1; i <= n; ++i)B[i] = read();
	for(int i = 1; i <= n; ++i){
		ori.clear();ori.get(A[i]);
		ori = ksm(ori,B[i]);
		ans = ans * ori;
	}
	for(int i = 0; i <= m; ++i){
		r = calc(r,ans.a[0][i]);
	}
	printf("%lld",r);
	return 0;
}