专栏文章

题解：UVA11551 Experienced Endeavour

wwangbinfeng
UVA11551题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mioko78u
此快照首次捕获于
2025/12/02 20:46
3 个月前
此快照最后确认于
2025/12/02 20:46
3 个月前
查看原文
前置知识：矩阵乘法，矩阵快速幂。
翻译（由 deepseek 翻译，有删改）
问题描述
Bob 给 Alice 一个整数列表，并要求她生成一个新列表，其中每个元素是原列表中某些整数的和。但任务稍复杂：Bob 要求 Alice 重复此操作多次后才返回结果。请帮助 Alice 自动化此任务。
输入格式
第一行输入为整数 t(1≤t≤10)t(1\leq t\leq 10)，表示测试用例的数量。每个测试用例的格式如下：
TXT
n r  
a₀ a₁ … aₙ₋₁  
x₀ b₀,₀ b₀,₁ … b₀,ₓ₀₋₁  
x₁ b₁,₀ b₁,₁ … b₁,ₓ₁₋₁  
…  
xₙ₋₁ bₙ₋₁,₀ bₙ₋₁,₁ … bₙ₋₁,ₓₙ₋₁₋₁
  • 第一行：整数 nn（列表长度，1≤n≤501 \leq n \leq 50 ）和 rr（重复次数，1≤r≤1091 \leq r \leq 10^9）。
  • 第二行：初始列表的 nn 个非负整数 a0,a1,…,an−1a_0, a_1, \ldots, a_{n-1}。
  • 接下来的 nn 行：定义如何生成新列表。第 ii 行格式为：
    xi  bi,0  bi,1  …  bi,xi−1x_i \; b_{i,0} \; b_{i,1} \; \ldots \; b_{i,x_i-1}
    表示新列表的第 ii 个元素是原列表中索引为 bi,0,bi,1,…,bi,xi−1b_{i,0}, b_{i,1}, \ldots, b_{i,x_i-1} 的元素之和。
输出格式
输出 tt 行，每行对应一个测试用例的结果。输出最终列表的每个元素模 10001000 后的值，格式为：
c0  c1  …cn−1c_0 \; c_1 \; \ldots c_{n-1}
样例输入
TXT
2
2 2
1 2
2 0 1
1 1
2 4
507 692
2 0 1
1 1
样例输出
TXT
5 2
275 692
由题目可知执行 rr 次中每次的操作均相同，且操作对象为一个数列（数组），可以知道使用矩阵快速幂是一个很好的选择。
考虑第一次进行矩阵快速幂，由 1×n1\times n 的矩阵到 1×n1\times n 的矩阵需要乘一个 n×nn\times n 的矩阵。
考虑 A×Br=CA\times B^r=C（A,CA,C 为 1×n1\times n 的矩阵，BB 为 n×nn\times n 的矩阵），显然 AA 为输入矩阵，CC 为结果矩阵，只需分析矩阵 BB 的内容。
对于矩阵 BB，考虑矩阵乘法的原理，对于每个 CjC_j 的加数 AiA_i，应当令 Bi,j=1B_{i,j}=1，否则应当令 Bi,j=0B_{i,j}=0。原理很简单，建议以矩阵乘法的原理为基点自己推一遍。
代码CPP
#include<bits/stdc++.h> 
using namespace std;
const int mod=1000;
namespace userMatrix{
	template<class T,const int MAXN,const int MAXM,const int MOD=1e9+7>
	class Matrix{
	public:
		T (*dat)[MAXM];
		int n=-1,m=-1,mod=MOD;
		Matrix(){dat=new T[MAXN][MAXM];}
		Matrix(const int n,const int m,const int mod=MOD):n(n),m(m),mod(mod){
			dat=new T[MAXN][MAXM];
			for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)dat[i][j]=0;
		}//构造函数 
		Matrix(const Matrix &a){
			dat=new T[MAXN][MAXM];
			n=a.n,m=a.m,mod=a.mod;
			for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)dat[i][j]=a.dat[i][j];
		}//拷贝构造函数 
		~Matrix(){delete[]dat;}
		Matrix one()const{
			Matrix ret(m,m,mod);
			for(int i=1;i<=m;i++)ret.dat[i][i]=1;
			return ret;
		}//单位矩阵 
		void reset(){
			for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)dat[i][j]=0;
			n=m=-1;
		}//重置为全 0 矩阵 
		Matrix operator=(const Matrix &a){
			delete[]dat;
			dat=new T[MAXN][MAXM];
			n=a.n,m=a.m,mod=a.mod;
			for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)dat[i][j]=a.dat[i][j];
			return *this;
		}
		void read(const int n,const int m,const int mod=1e9+7){
			this->n=n,this->m=m,this->mod=mod;
			for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>dat[i][j];
		}
		void read(const bool readMod=false){
			if(n==-1&&m==-1)cin>>n>>m;
			if(readMod)cin>>mod;
			read(n,m,mod);
		}
		Matrix operator+(const Matrix &a)const{
			if(n!=a.n && m!=a.m)throw("[Throws exception from function operator+ of class Matrix] Both n and m are wrong, please try again.");
			if(n!=a.n)throw("[Throw exception from function operator+ of class Matrix] Error in variable n, please try again.");
			if(m!=a.m)throw("[Throw exception from function operator+ of class Matrix] Error in variable m, please try again.");
			Matrix ret(n,m,mod);
			for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)ret.dat[i][j]=(dat[i][j]+a.dat[i][j])%mod;
			return ret;
		}
		Matrix operator+=(const Matrix &a){
			if(n!=a.n && m!=a.m)throw("[Throws exception from function operator+= of class Matrix] Both n and m are wrong, please try again.");
			if(n!=a.n)throw("[Throw exception from function operator+= of class Matrix] Error in variable n, please try again.");
			if(m!=a.m)throw("[Throw exception from function operator+= of class Matrix] Error in variable m, please try again.");
			for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)dat[i][j]=(dat[i][j]+a.dat[i][j])%mod;
			return *this;
		}
		Matrix operator-(const Matrix &a)const{
			if(n!=a.n && m!=a.m)throw("[Throws exception from function operator- of class Matrix] Both n and m are wrong, please try again.");
			if(n!=a.n)throw("[Throw exception from function operator- of class Matrix] Error in variable n, please try again.");
			if(m!=a.m)throw("[Throw exception from function operator- of class Matrix] Error in variable m, please try again.");
			Matrix ret(n,m,mod);
			for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)ret.dat[i][j]=(dat[i][j]-a.dat[i][j]+mod)%mod;
			return ret;
		}
		Matrix operator-=(const Matrix &a){
			if(n!=a.n && m!=a.m)throw("[Throws exception from function operator-= of class Matrix] Both n and m are wrong, please try again.");
			if(n!=a.n)throw("[Throw exception from function operator-= of class Matrix] Error in variable n, please try again.");
			if(m!=a.m)throw("[Throw exception from function operator-= of class Matrix] Error in variable m, please try again.");
			for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)dat[i][j]=(dat[i][j]-a.dat[i][j]+mod)%mod;
			return *this;
		}
		Matrix operator*(const Matrix &a)const{
			if(m!=a.n)throw("[Throw exception from function operator* of class Matrix] The previous item's m is not equal to the latter item's n, please try again!");
			Matrix ret(n,a.m,mod);
			for(int k=1;k<=m;k++)for(int i=1;i<=n;i++)for(int j=1;j<=a.m;j++)
				ret.dat[i][j]=(ret.dat[i][j]+dat[i][k]*a.dat[k][j])%mod;
			return ret;
		}
		Matrix operator*=(const Matrix &a){
			if(m!=a.n)throw("[Throw exception from function operator*= of class Matrix] The previous item's m is not equal to the latter item's n, please try again!");
			//Matrix *ret=new Matrix(n,a.m);
			Matrix ret(n,a.m,mod);
			for(int k=1;k<=m;k++)for(int i=1;i<=n;i++)for(int j=1;j<=a.m;j++)
				ret.dat[i][j]=(ret.dat[i][j]+dat[i][k]*a.dat[k][j])%mod;
			*this=ret;
			return *this;
		}
		Matrix operator^(long long k)const{
			Matrix ans(one()),a(*this);
			//Matrix *ans=new Matrix(one()),*a=new Matrix(*this);
			do{
				if(k&1)ans*=a;
				a*=a;k>>=1;
			}while(k);
			return ans;
		}
		Matrix operator^=(long long k){
			//Matrix *ans=new Matrix(one()); 
			Matrix ans(one());
			do{
				if(k&1)ans*=*this;
				*this*=*this;k>>=1;
			}while(k);
			return (*this=ans);
		}
		int print()const{
			cerr<<endl<<"[stderr_start]"<<endl;
			for(int i=1;i<=n;i++){for(int j=1;j<=m;j++)cerr<<dat[i][j]<<' ';cerr<<'\n';}
			cerr<<endl<<"[stderr_end]"<<endl;
			return n*m;
		}
	};
}
using namespace userMatrix;
Matrix<int,59,59,mod>a,b,c;
int t=-1,n,r;
signed main(){
	if(t==-1){ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);cin>>t;}
	if(t--==0)return 0;
	cin>>n>>r;
	a.n=1,a.m=n;
	b.n=n,b.m=n;
	for(int i=1;i<=n;i++)cin>>a.dat[1][i];
	for(int i=1,m;i<=n;i++){
		cin>>m;
		for(int j=1,x;j<=m;j++)cin>>x,b.dat[x+1][i]=1;
	}
	c=a*(b^=r);
	//cout<<"ans="; 
	for(int i=1;i<=n;i++)cout<<c.dat[1][i]<<(i==n?'\n':' ');
	//a.print(),b.print(),c.print();
	a.reset(),b.reset(),c.reset();
	main();
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...