记录编号	600213	评测结果	RRRRRRRRRR
题目名称	加法问题	最终得分	0
用户昵称	ChenBp	是否通过	未通过
代码语言	C++	运行时间	2.093 s
提交时间	2025-04-21 21:57:24	内存使用	3.09 MiB

#include <iostream>
#include <vector>
using namespace std;

template<typename T>
struct Matrix {
	vector<vector<T>>mat;
	int n,m,mod;

	void resize(int nt,int mt){
		n=nt;
		m=mt;
		mat.resize(n);
		for(int i=0;i<n;i++)
			mat[i].resize(m);
	}

	//非const版本（支持修改元素）
	vector<T>&operator[](const int &index){
		return mat[index];
	}
	//const版本（支持const对象访问）
	const vector<T>&operator[](const int &index)const{
		return mat[index];
	}

	Matrix operator+(const Matrix &b)const{
		Matrix ans;
		if(n!=b.n||m!=b.m)return ans;
		ans.resize(n,m);
		for(int i=0;i<n;i++)
			for(int j=0;j<m;j++){
			    ans[i][j]=(*this)[i][j]+b[i][j];
			    ans[i][j]%=mod;
            }
		return ans;
	}

	Matrix operator-(const Matrix &b)const{
		Matrix ans;
		if(n!=b.n||m!=b.m)return ans;
		ans.resize(n,m);
		for(int i=0;i<n;i++)
			for(int j=0;j<m;j++){
			    ans[i][j]=(*this)[i][j]-b[i][j];
			    ans[i][j]%=mod;
            }
		return ans;
	}

	Matrix operator*(const Matrix &b)const{
		Matrix ans;
		if(m!=b.n){
			return ans;
		}
		ans.resize(n,b.m);
		for(int i=0;i<n;++i){
			for(int j=0;j<b.m;++j){
				T sum=0;
				for(int k=0;k<m;++k){
					sum+=(*this)[i][k]*b[k][j];
					sum%=mod;
				}
				ans[i][j]=sum;
			}
		}
		return ans;
	}
	Matrix operator*(const T b)const{
		Matrix ans;
		ans.resize(n,m);
		for(int i=0;i<n;++i){
			for(int j=0;j<m;++j){
				ans=(*this)[i][j]*b;
				ans%=mod;
			}
		}
		return ans;
	}
};
template <typename T>
Matrix<T> pow(const Matrix<T>& a,int b){
    Matrix<T> ans;
    if(a.n!=a.m) return ans;
    if(b==1) return a;
    ans=pow(a,b/2);
    if(b&1) return ans*ans*a;
    else return ans*ans;
}
int main(){
	while(true){
	    int n,m;
	    cin>>n>>m;
	    if(n*m==0) return 0;
	    Matrix <int>ma;
	    ma.resize(n+1,n+1);
	    ma.mod=1000;
	    for(int i=1;i<=m;i++){
	        int s,t;
	        cin>>s>>t;
	        ma[s][t]=1;
        }
        int t;
        cin>>t;
        while(t--){
            int a,b,k;
            cin>>a>>b>>k;
            cout<<pow(ma,k-1)[a][b]<<endl;
        }
    }
	return 0;
}