题解：UVA11551 Experienced Endeavour
wangbinfeng · · 题解
前置知识：矩阵乘法，矩阵快速幂。
::::info[翻译（由 deepseek 翻译，有删改）]
问题描述
Bob 给 Alice 一个整数列表，并要求她生成一个新列表，其中每个元素是原列表中某些整数的和。但任务稍复杂：Bob 要求 Alice 重复此操作多次后才返回结果。请帮助 Alice 自动化此任务。
输入格式
第一行输入为整数
n r
a₀ a₁ … aₙ₋₁
x₀ b₀,₀ b₀,₁ … b₀,ₓ₀₋₁
x₁ b₁,₀ b₁,₁ … b₁,ₓ₁₋₁
…
xₙ₋₁ bₙ₋₁,₀ bₙ₋₁,₁ … bₙ₋₁,ₓₙ₋₁₋₁ - 第一行：整数
n （列表长度，1 \leq n \leq 50 ）和r （重复次数，1 \leq r \leq 10^9 ）。 - 第二行：初始列表的
n 个非负整数a_0, a_1, \ldots, a_{n-1} 。 - 接下来的
n 行：定义如何生成新列表。第i 行格式为：x_i \; b_{i,0} \; b_{i,1} \; \ldots \; b_{i,x_i-1} 表示新列表的第
i 个元素是原列表中索引为b_{i,0}, b_{i,1}, \ldots, b_{i,x_i-1} 的元素之和。
输出格式
输出
样例输入
2
2 2
1 2
2 0 1
1 1
2 4
507 692
2 0 1
1 1样例输出
5 2
275 692::::
由题目可知执行
考虑第一次进行矩阵快速幂，由
考虑
对于矩阵
::::success[代码]
#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();
}::::