結果

問題 No.1784 Not a star yet...
ユーザー KIreteria
提出日時 2025-06-12 22:21:18
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 68 ms / 2,000 ms
コード長 4,318 bytes
コンパイル時間 2,619 ms
コンパイル使用メモリ 205,304 KB
実行使用メモリ 69,788 KB
最終ジャッジ日時 2025-06-12 22:21:26
合計ジャッジ時間 7,224 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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++){
    //     for(int j=0;j<=Y+1;j++)printf("%d ",mp[i][j]);
    //     printf("\n");
    // }
    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);
                // printf("%d %d %d %d\n",j,k,div,mp[j][k]);
            }
        }
    }
    for(int i=0;i<=Y;i++){
        ans[i]=1ll*mp[i][Y+1]*KSM(mp[i][i],mod-2)%mod;
    }ans[Y+1]=1;
    // for(int i=0;i<=Y+1;i++)printf("%d ",ans[i]);
    // printf("\n");
    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);
    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
            // printf("%d %d %d %d\n",i,j,n-i-j,m);
        }
    }
    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],KSM(n,mod-2));
            // for(int k=0;k<=Y+1;k++)printf("%d ",v[i+1][j][k]);
            // printf("\n");
            v[i+1][j]=v[i+1][j]*KSM(mod-c[i][j][0],mod-2);
            // for(int k=0;k<=Y+1;k++)printf("%d ",v[i+1][j][k]);
            // printf("\n");
        }
    }
    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],KSM(n,mod-2));
        tmp[Y+1]=mod-tmp[Y+1];
        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);//printf("%d %d\n",i,ans[i]);
        // printf("res = %d\n",res);
        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