kmjp's blog

競技プログラミング参加記です

yukicoder : No.623 fudan no modulus to tigau

うーん?
https://yukicoder.me/problems/no/623

問題

整数列T[i]に対し、以下の関数f(k)を考える。

  • f(0)(x) = 1
  • f(1)(x) = x
  • i≧2に対し
    • T[i]==1 ならf(i)(x) = f(a[i])(x) + f(b[i])(x)
    • T[i]==2 ならf(i)(x) = a[i] * f(b[i])(x)
    • T[i]==3 ならf(i)(x) = f(a[i])(x) * f(b[i])(x)

いくつかの値xが指定されるので、f(x)を求めよ。

解法

fを愚直に多項式で表す必要はなく、順にf(i)(x)を求めるだけ。

int N,Q;

int T[51];
ll A[51],B[51];
ll F[51];
ll mo=998244353;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	for(i=2;i<=N;i++) cin>>T[i]>>A[i]>>B[i];
	
	F[0]=1;
	cin>>Q;
	while(Q--) {
		cin>>F[1];
		for(i=2;i<=N;i++) {
			if(T[i]==1) F[i]=(F[A[i]]+F[B[i]])%mo;
			if(T[i]==2) F[i]=A[i]*F[B[i]]%mo;
			if(T[i]==3) F[i]=(F[A[i]]*F[B[i]])%mo;
		}
		cout<<F[N]<<endl;
	}
}

まとめ

これ何の意図があったんだろう…時間切れとかかな。