結果

問題 No.1784 Not a star yet...
コンテスト
ユーザー KIreteria
提出日時 2025-06-12 22:23:33
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 65 ms / 2,000 ms
コード長 3,731 bytes
コンパイル時間 2,094 ms
コンパイル使用メモリ 205,084 KB
実行使用メモリ 69,588 KB
最終ジャッジ日時 2025-06-12 22:23:41
合計ジャッジ時間 6,706 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 61
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#define pii std::pair<int,int>
#define mkp std::make_pair
#define fir first
#define sec second
typedef long long ll;
inline void rd(){}
template<typename T,typename ...U>
inline void rd(T &x,U &...args){
    int ch=getchar();
    T f=1;x=0;
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    x*=f;rd(args...);
}
const int N=255,mod=998244353;
int n,m,X,Y,d[2][N];
inline int KSM(int x,int n){
    int ans=1;
    while(n){
        if(n&1)ans=1ll*ans*x%mod;
        x=1ll*x*x%mod;n>>=1;
    }return ans;
}
int c[N][N][5];
inline int Sum(int a,int b){return (a+b)>=mod?a+b-mod:a+b;}
inline void Add(int &a,int b){(a+=b)>=mod?a-=mod:1;}
struct Vector{
    int v[N];
    Vector(){memset(v,0,sizeof v);}
    int& operator[](int x){return v[x];}
    Vector friend operator +(Vector a,Vector b){Vector c;for(int i=0;i<=Y+1;i++)c[i]=Sum(a[i],b[i]);return c;}
    Vector friend operator -(Vector a,Vector b){Vector c;for(int i=0;i<=Y+1;i++)c[i]=Sum(a[i],mod-b[i]);return c;}
    Vector friend operator *(Vector a,int x){Vector c;for(int i=0;i<=Y+1;i++)c[i]=1ll*a[i]*x%mod;return c;}
    Vector friend operator *(int x,Vector a){Vector c;for(int i=0;i<=Y+1;i++)c[i]=1ll*a[i]*x%mod;return c;}
    Vector operator +=(Vector b){return *this=*this+b;}
}v[N][N];
int mp[N][N],ans[N];
inline int Gauss(){
    for(int i=0;i<=Y;i++){
        int cur=i;
        for(int j=i;j<=Y;j++)if(mp[j][i])cur=j;
        if(cur!=i)std::swap(mp[cur],mp[i]);
        if(!mp[i][i])return puts("???"),0;
        for(int j=0;j<=Y;j++){
            if(j==i)continue;
            int div=1ll*(mod-mp[j][i])*KSM(mp[i][i],mod-2)%mod;
            for(int k=i;k<=Y+1;k++){
                Add(mp[j][k],1ll*div*mp[i][k]%mod);
            }
        }
    }
    for(int i=0;i<=Y;i++){
        ans[i]=1ll*(mod-mp[i][Y+1])*KSM(mp[i][i],mod-2)%mod;
    }ans[Y+1]=1;
    return 1;
}
signed main(){
    rd(n);
    for(int i=1;i<n;i++){
        int x,y,z;rd(x,y,z);
        X+=(z==1),Y+=(z==2);
        d[z-1][x]++,d[z-1][y]++;
    }
    m=n*(n-1)/2-(n-2);
    int inv=KSM(X+2*Y,mod-2),invm=KSM(m,mod-2),invn=KSM(n,mod-2);
    for(int i=0;i<=X;i++){
        for(int j=0;j<=Y;j++){
            c[i][j][0]=1ll*(X-i)*inv%mod*(n-1-i-j)%mod*invm%mod;//d1+1
            c[i][j][1]=1ll*(i)*inv%mod*(m-(n-i-j))%mod*invm%mod;//d1-1
            c[i][j][2]=1ll*(2*Y-2*j)*inv%mod*(n-1-i-j)%mod*invm%mod;//d2+1
            c[i][j][3]=1ll*(2*j)*inv%mod*(m-(n-i-j))%mod*invm%mod;//d2-1
            c[i][j][4]=(4ll*mod+1-c[i][j][0]-c[i][j][1]-c[i][j][2]-c[i][j][3])%mod;//nothing happens
        }
    }
    for(int j=0;j<=Y;j++)v[0][j][j]=1;
    for(int i=0;i<X;i++){
        for(int j=0;j<=Y;j++){
            v[i+1][j]=(c[i][j][4]-1+mod)*v[i][j];
            if(i>0)v[i+1][j]+=c[i][j][1]*v[i-1][j];
            if(j>0)v[i+1][j]+=c[i][j][3]*v[i][j-1];
            if(j<Y)v[i+1][j]+=c[i][j][2]*v[i][j+1];
            Add(v[i+1][j][Y+1],invn);
            v[i+1][j]=v[i+1][j]*KSM(mod-c[i][j][0],mod-2);
        }
    }
    for(int j=0;j<Y;j++){
        Vector tmp=v[X][j]*(c[X][j][4]+mod-1);
        if(X>0)tmp+=c[X][j][1]*v[X-1][j];
        if(j>0)tmp+=c[X][j][3]*v[X][j-1];
        if(j<Y)tmp+=c[X][j][2]*v[X][j+1];
        Add(tmp[Y+1],invn);
        for(int i=0;i<=Y+1;i++)mp[j][i]=tmp[i];
    }
    mp[Y][0]=1;
    Gauss();
    auto GetVal=[&](int x,int y){
        int res=0;
        for(int i=0;i<=Y+1;i++)Add(res,1ll*ans[i]*v[x][y][i]%mod);
        return res;
    };
    int res=0;
    for(int i=1;i<=n;i++)Add(res,GetVal(d[0][i],d[1][i]));
    Add(res,mod-1ll*X*GetVal(1,0)%mod);
    Add(res,mod-1ll*Y*GetVal(0,1)%mod);
    Add(res,mod-GetVal(X,Y));
    printf("%d\n",res);
    return 0;
}
0