Submission #54419026

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Edge{
	int x,y;
	vector<ll> e;
}a[50];
int n,m,t;
vector<ll> dp[11];
const int P=998244353,G=3,GI=332748118;
template<typename T>
void madd(T &a,T b){a=(a+b)%P;}
template<typename T>
void read(T &a){
	#define gc getchar()
	char c;a=0;
	while(!isdigit(c=gc));
	do a=a*10+c-'0';
	while(isdigit(c=gc));
}
template<typename T>
void write(T a){
	if(a>=10)write(a/10);
	putchar('0'+a%10);
}
ll qpow(ll a,ll b){
	ll c=1;
	for(;b>0;b>>=1,a=a*a%P)
		if(b&1)
		c=c*a%P;
	return c;
}
vector<ll> get_vec(vector<ll> &a,int l,int r){
	vector<ll> b;
	b.assign(a.begin()+l,a.begin()+r+1);
	return b;
}
int r[160010];
void fntt(vector<ll> &a,int I){
	int s=a.size(),t=s-1,d=0;
	while(t)t>>=1,d++;
	for(int i=0;i<s;++i)
		r[i]=(r[i>>1]>>1)|((i&1)<<(d-1));
	for(int i=0;i<s;++i)
		if(i<r[i])
			swap(a[i],a[r[i]]);
	for(int i=2;i<=s;i<<=1){
		ll gn=qpow(I==1?G:GI,(P-1)/i);
		for(int j=0;j<s;j+=i){
			ll g=1;
			for(int k=0;k<i/2;++k,g=g*gn%P){
				int t=a[j+k+i/2];
				a[j+k+i/2]=(a[j+k]-g*t)%P;
				a[j+k]=(a[j+k]+g*t)%P;
			}
		}
	}
	if(I==-1){
		int inv=qpow(s,P-2);
		for(int i=0;i<s;++i)a[i]=a[i]*inv%P;
	}
}
vector<ll> convolution(vector<ll> a,vector<ll> b){
	auto get_s=[&](int n)->int{
		int m=0;
		while(n){
			n>>=1;
			m++;
		}
		return 1<<m;
	};
	int s=get_s(a.size()+b.size()-1);
	a.resize(s,0);
	b.resize(s,0);
	// printf("a ");for(auto i:a)printf("%d ",i);puts("");
	// printf("b ");for(auto i:b)printf("%d ",i);puts("");
	fntt(a,1);
	fntt(b,1);
	// printf("ia ");for(auto i:a)printf("%d ",i);puts("");
	// printf("ib ");for(auto i:b)printf("%d ",i);puts("");
	for(int i=0;i<s;++i)a[i]=a[i]*b[i]%P;
	fntt(a,-1);
	// printf("c ");for(auto i:a)printf("%d ",i);puts("");
	return a;
}
void online_convolution(int l,int r){
	if(l==r)return;
	int mid=(l+r)/2;
	online_convolution(l,mid);
	for(int i=1;i<=m;++i){
		int x=a[i].x,y=a[i].y;
		vector<ll> dx=get_vec(dp[x],l,mid);
		vector<ll> dy=get_vec(dp[y],l,mid);
		vector<ll> es=get_vec(a[i].e,0,r-l);
		dx=convolution(dx,es);
		dy=convolution(dy,es);
		for(int j=mid+1;j<=r;++j){
			madd(dp[y][j],dx[j-l]);
			madd(dp[x][j],dy[j-l]);
		}
	}
	online_convolution(mid+1,r);
}

signed main(){
	cin>>n>>m>>t;
	for(int i=1;i<=m;++i){
		read(a[i].x),read(a[i].y);
		a[i].e.resize(t+1);
		for(int j=1;j<=t;++j)cin>>a[i].e[j];
	}
	for(int i=1;i<=n;++i)dp[i].resize(t+1);
	dp[1][0]=1;
	online_convolution(0,t);
	write((dp[1][t]+P)%P);putchar('\n');
	return 0;
}

Submission Info

Judge Result