FJXM JKY 在t狗上组织的比赛的 D10T1

题面：https://note.ms/tdogD10T1

赛事代码贴上来了

#pragma GCC optimize("Ofast")
#include<cstdio>
#include<cstring>
#include<cctype>
#include<cstring>
#include<iostream>
using namespace std;
const int N=1e7;
const int mod=998244353;
long long inv[N+5];
int n,m[N+5],h[N+5],e[N*2+5],ne[N*2+5],idx,cnt[N*2+5];
int w[N+5][30];
int f[N+5];
inline int ksm(int a,int b){
	int ans=1;
	for(;b;b>>=1){
		if(b&1)ans=ans*a%mod;
		a=a*a%mod;
	}
	return ans;
}
inline void init(int n){
	inv[0]=0,inv[1]=1;
	for(int i=2;i<=n;i++){
        inv[i]=(mod-mod/i)*inv[mod%i]%mod;
        //printf("%lld\n",inv[i]);
    }
}
void add(int a,int b){e[++idx]=b,ne[idx]=h[a],h[a]=idx;}
int dfs(int u,int d){
	if(f[u]>=0)return f[u];
    f[u]=0;
    f[u]+=w[u][d]*inv[m[u]]%mod;
    for(int i=h[u];i!=-1;i=ne[i]){
        int j=e[i];
        //cout<<j<<" "<<d<<" "<<f[u]<<" "<<dfs(j,d)<<" "<<m[u]<<endl;
        f[u]=(f[u]+dfs(j,d)*inv[m[u]]%mod)%mod;
    }
    return f[u];
}
int trans(char v[]){
	int ans=0;
	for(int i=0;i<strlen(v);i++)ans=ans*10+v[i]-'0';
	return ans;
}
signed main(){
    cin>>n;
    init(N);
    memset(h,-1,sizeof(h));
    for(int i=1;i<=n;i++){
        cin>>m[i];
        for(int j=1;j<=m[i];j++){
        	char v[10];cin>>v;
        	if(isupper(v[0]))w[i][(v[0]-'A')]++;
        	else add(i,trans(v));
		}
    }
    for(int i=0;i<26;i++)memset(f,-1,sizeof(f)),cout<<dfs(1,i)<<" ";
}
/*
10
3 2 3 4
3 3 4 5
3 4 5 6
3 5 6 7
3 6 7 8
3 7 8 9
3 8 9 10
3 9 10 B
3 D E A
3 B C D
*/

喜提爆8个点的60pts佳绩

YZ全场T得一个比一个惨，但是SS有人A了，全场过的人最少的一题。

用记搜来写时间应该是O(n)的，然后每个字母搜一遍乘上26常数。

逆元也是O(n)求。赛后发现cin>>m[i]，改成scanf后分数雷打不动。

有没有大佬提供常数更优的做法？