結果

問題 No.1784 Not a star yet...
コンテスト
ユーザー vjudge1
提出日時 2025-06-05 20:28:36
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 40 ms / 2,000 ms
コード長 2,288 bytes
コンパイル時間 3,781 ms
コンパイル使用メモリ 281,956 KB
実行使用メモリ 36,560 KB
最終ジャッジ日時 2025-06-05 20:28:43
合計ジャッジ時間 7,109 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 61
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:17:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   17 |         scanf("%d",&n);
      |         ~~~~~^~~~~~~~~
main.cpp:19:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   19 |                 scanf("%d%d%d",&u,&v,&l);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~

ソースコード

diff # 

#include<bits/stdc++.h>
#define mod 998244353
#define N 253
using namespace std;
int power(int x,int y){
	int res=1;
	while(y){
		if(y&1) res=1ll*res*x%mod;
		x=1ll*x*x%mod;
		y=y/2;
	}
	return res;
}
int n,ra[N],rb[N],A,B,ans;
int f[N][N][N],tmp[N],g[N][N],h[N][N]; 
int main(){
	scanf("%d",&n);
	for(int i=1,u,v,l;i<n;i++){
		scanf("%d%d%d",&u,&v,&l);
		if(l==1) A++,ra[u]++,ra[v]++;
		else B++,rb[u]++,rb[v]++;
	}
	int S0=A+2*B,S1=n*(n-1)/2-(n-2);
	int invS0=power(S0,mod-2),invS1=power(S1,mod-2);
	for(int j=1;j<=B;j++) f[0][j][j-1]=1;
	for(int i=0;i<=A;i++){
		for(int j=0;j<=B;j++){
			if(i==A&&j==B) continue;
			int dl_a=1ll*i*invS0%mod;
			int dl_b=2ll*j*invS0%mod;
			int dl_n=1ll*(S0-i-2*j)*invS0%mod;
			int ad0=1ll*(n-1-i-j)*invS1%mod;
			int ad1=1ll*(n-i-j)*invS1%mod;
			int ad_n0=(1+mod-ad0)%mod;
			int ad_n1=(1+mod-ad1)%mod;
			int wm=0,wl=0,wr=0,wd=0,wu=0;
			wm=(1ll*dl_n*ad_n0+1ll*(dl_a+dl_b)*ad1)%mod;
			wd=1ll*dl_a*ad_n1%mod;
			wu=1ll*(A-i)*invS0%mod*ad0%mod;
			wl=1ll*dl_b*ad_n1%mod;
			wr=2ll*(B-j)*invS0%mod*ad0%mod;
			wm=(1+mod-wm)%mod;
			for(int x=0;x<=B;x++) tmp[x]=1ll*f[i][j][x]*wm%mod;
			if(i>0){
				for(int x=0;x<=B;x++)
					tmp[x]=(tmp[x]+1ll*(mod-wd)*f[i-1][j][x])%mod;
			}
			if(j>0){
				for(int x=0;x<=B;x++)
					tmp[x]=(tmp[x]+1ll*(mod-wl)*f[i][j-1][x])%mod;
			}
			if(j<B){
				for(int x=0;x<=B;x++)
					tmp[x]=(tmp[x]+1ll*(mod-wr)*f[i][j+1][x])%mod;
			}
			tmp[B]++;
			if(i<A){
				int inv=power(wu,mod-2);
				for(int x=0;x<=B;x++)
					f[i+1][j][x]=1ll*tmp[x]*inv%mod;
			}
			else{for(int x=0;x<=B;x++) g[j][x]=tmp[x];}
		}
	}
	for(int i=0;i<B;i++) g[i][B]=mod-g[i][B];
	for(int i=0;i<B;i++){
		int inv=power(g[i][i],mod-2);
		for(int j=i+1;j<B;j++){
			if(!g[j][i]) continue;
			int div=1ll*(mod-g[j][i])*inv%mod;
			for(int p=i;p<=B;p++)
				g[j][p]=(g[j][p]+1ll*div*g[i][p])%mod;
		}
	}
	for(int i=B-1;i>=0;i--){
		for(int j=i+1;j<B;j++) g[i][B]=(g[i][B]+1ll*(mod-g[i][j])*g[j][B])%mod;
		g[i][B]=1ll*g[i][B]*power(g[i][i],mod-2)%mod;
	}
	g[B][B]=1;
	for(int i=0;i<=A;i++)
		for(int j=0;j<=B;j++)
			for(int x=0;x<=B;x++) h[i][j]=(h[i][j]+1ll*f[i][j][x]*g[x][B])%mod;
	ans=(h[A][B]+1ll*A*h[1][0]+1ll*B*h[0][1])%mod;
	for(int i=1;i<=n;i++) ans=(ans-h[ra[i]][rb[i]]+mod)%mod;
	ans=1ll*ans*power(n,mod-2)%mod;
	printf("%d",ans);
}
0