結果

問題 No.1784 Not a star yet...
ユーザー QZJ123456
提出日時 2025-06-05 21:26:02
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 104 ms / 2,000 ms
コード長 3,444 bytes
コンパイル時間 2,523 ms
コンパイル使用メモリ 214,652 KB
実行使用メモリ 48,708 KB
最終ジャッジ日時 2025-06-05 21:26:13
合計ジャッジ時間 7,157 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 61
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:60:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   60 |         scanf("%d",&n);
      |         ~~~~~^~~~~~~~~
main.cpp:62:32: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   62 |                 int x,y,z;scanf("%d%d%d",&x,&y,&z);
      |                           ~~~~~^~~~~~~~~~~~~~~~~~~

ソースコード

diff # 

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const ll mod=998244353;
int X,Y,d1[255],d2[255],n;
ll mat[505][505];
map<ll,ll>mp[100005];
ll ksm(ll a,ll m,ll p){
	ll ans=1;
	while(m){
		if(m&1)ans=ans*a%p;
		a=a*a%p;
		m>>=1;
	}
	return ans;
}
int Getid(int i,int j){
	i++,j++;
	return (i-1)*(Y+1)+j;
}
ll xs[255][255][255];
void gauss(int n){
	for(int i=1;i<=n;i++){
		int p=i;
		for(int j=i+1;j<=n;j++){
			if(mat[j][i])p=j;
		}
		swap(mat[i],mat[p]);
		ll inv=ksm(mat[i][i],mod-2,mod);
		for(int j=i+1;j<=n;j++){
			ll val=mat[j][i]*inv%mod;
			for(int k=i;k<=n+1;k++)mat[j][k]=(mat[j][k]-mat[i][k]*val%mod+mod)%mod;
		}
	}
	for(int i=n;i;i--){
		mat[i][n+1]=mat[i][n+1]*ksm(mat[i][i],mod-2,mod)%mod;
		for(int j=1;j<i;j++)mat[j][n+1]=(mat[j][n+1]-mat[i][n+1]*mat[j][i]%mod+mod)%mod;
	}
	return;
}
void add(int x,int y,int x1,int y1,ll val){
	for(int i=0;i<=Y+1;i++)xs[x][y][i]=(xs[x][y][i]+xs[x1][y1][i]*val)%mod;
}
void dec(int x,int y,int x1,int y1,ll val){
	add(x,y,x1,y1,mod-val);
}
void add(int x,int y,ll val){
	xs[x][y][Y+1]=(xs[x][y][Y+1]+val)%mod;
}
void div(int x,int y,ll val){
	val=ksm(val,mod-2,mod);
	for(int i=0;i<=Y+1;i++)xs[x][y][i]=xs[x][y][i]*val%mod;
}
ll calc(int x,int y){
	ll res=xs[x][y][Y+1];
	for(int i=0;i<=Y;i++)res=(res+mat[i+1][Y+2]*xs[x][y][i])%mod;
	return res;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<n;i++){
		int x,y,z;scanf("%d%d%d",&x,&y,&z);
		if(z==1)X++,d1[x]++,d1[y]++;
		else Y++,d2[x]++,d2[y]++;
	}
	int P=n*(n-1)/2-n+2,all=Getid(X,Y);ll iv=ksm(n,mod-2,mod);
	for(int i=0;i<=X;i++){
		for(int j=0;j<=Y;j++){
			if(i==X&&j==Y){
				mp[Getid(i,j)][Getid(i,j)]=1;
				continue;
			}
			int Q=n-i-j;
			mp[Getid(i,j)][Getid(i,j)]=(X+Y+Y)*P%mod;
			mp[Getid(i,j)][Getid(i,j)]=(mp[Getid(i,j)][Getid(i,j)]-(Q*(i+j+j)+(P-Q+1)*((X-i)+2*(Y-j)))%mod+mod)%mod;
			if(i)mp[Getid(i,j)][Getid(i-1,j)]=(mp[Getid(i,j)][Getid(i-1,j)]-(P-Q)*i%mod+mod)%mod;
			if(j)mp[Getid(i,j)][Getid(i,j-1)]=(mp[Getid(i,j)][Getid(i,j-1)]-2*(P-Q)*j%mod+mod)%mod;
			if(i<X)mp[Getid(i,j)][Getid(i+1,j)]=(mp[Getid(i,j)][Getid(i+1,j)]-(Q-1)*(X-i)%mod+mod)%mod;
			if(j<Y)mp[Getid(i,j)][Getid(i,j+1)]=(mp[Getid(i,j)][Getid(i,j+1)]-(Q-1)*2*(Y-j)%mod+mod)%mod;
			mp[Getid(i,j)][all+1]=(ll)(X+2*Y)*P%mod*iv%mod;
		}
	}
	for(int i=0;i<=Y;i++)xs[0][i][i]=1;
	for(int i=0;i<X;i++){
		for(int j=0;j<=Y;j++){
			add(i+1,j,mp[Getid(i,j)][all+1]);
			dec(i+1,j,i,j,mp[Getid(i,j)][Getid(i,j)]);
			if(i)dec(i+1,j,i-1,j,mp[Getid(i,j)][Getid(i-1,j)]);
			if(j)dec(i+1,j,i,j-1,mp[Getid(i,j)][Getid(i,j-1)]);
			if(j<Y)dec(i+1,j,i,j+1,mp[Getid(i,j)][Getid(i,j+1)]);
			div(i+1,j,mp[Getid(i,j)][Getid(i+1,j)]);
		}
	}
	for(int i=0;i<=Y;i++){
		ll val=mp[Getid(X,i)][Getid(X,i)];
		for(int j=0;j<=Y+1;j++)mat[i+1][j+1]=(mat[i+1][j+1]+xs[X][i][j]*val)%mod;
		if(X){
			val=mp[Getid(X,i)][Getid(X-1,i)];
			for(int j=0;j<=Y+1;j++)mat[i+1][j+1]=(mat[i+1][j+1]+xs[X-1][i][j]*val)%mod;
		}
		if(i){
			val=mp[Getid(X,i)][Getid(X,i-1)];
			for(int j=0;j<=Y+1;j++)mat[i+1][j+1]=(mat[i+1][j+1]+xs[X][i-1][j]*val)%mod;
		}
		if(i<Y){
			val=mp[Getid(X,i)][Getid(X,i+1)];
			for(int j=0;j<=Y+1;j++)mat[i+1][j+1]=(mat[i+1][j+1]+xs[X][i+1][j]*val)%mod;
		}
		mat[i+1][Y+2]=(mp[Getid(X,i)][all+1]-mat[i+1][Y+2]+mod)%mod;
	}
	gauss(Y+1);
	ll ans=0;
	for(int i=1;i<=n;i++)ans=(ans+calc(d1[i],d2[i]))%mod;
	ans=(ans-calc(X,Y)+mod)%mod;
	ans=(ans-calc(1,0)*X%mod+mod)%mod;
	ans=(ans-calc(0,1)*Y%mod+mod)%mod;
	printf("%lld",ans);
	return 0;
}
0