結果

問題 No.1784 Not a star yet...
ユーザー wjwweiwei
提出日時 2025-07-04 16:51:17
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 72 ms / 2,000 ms
コード長 2,681 bytes
コンパイル時間 3,861 ms
コンパイル使用メモリ 282,668 KB
実行使用メモリ 68,544 KB
最終ジャッジ日時 2025-07-04 16:51:26
合計ジャッジ時間 8,942 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 61
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=255,P=998244353;
inline ll ksm(ll a,int b){
	ll res=1;
	while(b){
		if(b&1)res=res*a%P;
		a=a*a%P,b>>=1;
	}
	return res;
}
inline ll ginv(int x){return ksm(x,P-2);}
int n;
int d[N][3];
int kp,kq;
int a[N][N];
ll val[N];
inline int mol(int x,int y){return x+y>=P?x+y-P:x+y;}
int x,y;
struct Line{
	int v[N];//v[i]->f[0][i]
	inline int& operator [](int x){return v[x];}
	inline const int& operator [](int x)const{return v[x];}
	Line(){memset(v,0,sizeof v);}
	inline Line operator +(const Line B){
		Line C;
		for(int i=0;i<=y+1;i++)C[i]=mol(v[i],B[i]);
		return C;
	}
	inline void operator +=(const Line B){*this=*this+B;}
	inline Line operator -(const Line B){
		Line C;
		for(int i=0;i<=y+1;i++)C[i]=mol(v[i],P-B[i]);
		return C;
	}
	inline void operator -=(const Line B){*this=*this-B;}
	inline Line operator *(int k){
		Line C;
		for(int i=0;i<=y+1;i++)C[i]=1ll*v[i]*k%P;
		return C;
	}
	inline void operator *=(int k){(*this)=(*this)*k;}
	inline Line operator /(int k){
		k=ginv(k);
		if(k==0)assert(0);
		return (*this)*k;
	}
	inline void operator /=(int k){(*this)=(*this)/k;}
	inline ll gt(){
		ll res=v[y+1];
		for(int i=0;i<=y;i++)res+=val[i]*v[i]%P;
		return res%P;
	}
}rea[N][N];
int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n;kp=n*(n-1)/2-(n-2);
	int u,v,w;
	for(int i=1;i<n;i++){
		cin>>u>>v>>w;
		x+=(w==1),y+=(w==2);
		d[u][w]++,d[v][w]++;
	}
	for(int i=0;i<=y;i++)rea[0][i].v[i]=1;
	ll tp=(P-ginv(n)*kp%P*(x+2*y)%P)%P;
	for(int i=0;i<=x;i++){
		for(int j=0;j<=y;j++){
			if(x==i&&y==j)continue;
			kq=n-i-j;
			Line cur=rea[i][j]*((1ll*kp*(x+2*y)-1ll*kq*(i+2*j)-1ll*(kp-kq+1)*((x-i)+2*(y-j)))%P+P);
			if(i)cur-=rea[i-1][j]*(1ll*(kp-kq)*i%P);
			if(j)cur-=rea[i][j-1]*(2ll*(kp-kq)*j%P);
			if(j<y)cur-=rea[i][j+1]*(2ll*(kq-1)*(y-j)%P);
			cur[y+1]=mol(cur[y+1],tp);
			if(i<x)rea[i+1][j]=cur/(1ll*(kq-1)*(x-i)%P);
			else{
				for(int k=0;k<=y;k++)a[j][k]=cur[k];
				a[j][y+1]=mol(P,-cur[y+1]);
			}
		}
	}
	a[y][0]=1;
	Line cur=(rea[1][0]*x)+(rea[0][1]*y)+rea[x][y];
	for(int i=0;i<=y;i++)a[y][i]=cur[i];
	a[y][y+1]=mol(P,-cur[y+1]);
	for(int i=0;i<=y;i++){
		int r=i;
		for(int j=i+1;j<=y;j++){
			if(a[j][i]>a[r][i])r=j;
		}
		swap(a[i],a[r]);
		ll inv=ginv(a[i][i]);
		for(int j=i;j<=y+1;j++)a[i][j]=a[i][j]*inv%P;
		for(int j=0;j<=y;j++){
			if(i==j)continue;
			inv=a[j][i];
			for(int k=i;k<=y+1;k++)a[j][k]=mol(a[j][k],P-inv*a[i][k]%P);
		}
	}
	for(int i=0;i<=y;i++)val[i]=a[i][y+1];
	ll ans=0;
	for(int i=1;i<=n;i++){
		if(d[i][1]==x&&d[i][2]==y){
			cout<<"0\n";
			return 0;
		}
		ans+=rea[d[i][1]][d[i][2]].gt();
	}
	cout<<(ans%P+P)%P<<"\n";
	return 0;
}
0