結果

問題 No.1483 Many Graph in Namori
ユーザー oceeff
提出日時 2025-05-22 11:59:46
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 47 ms / 2,000 ms
コード長 2,985 bytes
コンパイル時間 3,482 ms
コンパイル使用メモリ 221,216 KB
実行使用メモリ 19,792 KB
最終ジャッジ日時 2025-05-22 11:59:55
合計ジャッジ時間 8,087 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 56
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#ifdef ONLINE_JUDGE
	#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
	char buf[1<<21],*p1=buf,*p2=buf;
#endif
using namespace std;int read(){int num=0,f=1;char c;while(!isdigit(c=getchar()))if(c=='-')f=-1;while(isdigit(c))num=num*10+(c&15),c=getchar();return num*f;}void write(int x,char ch=' '){int F[20],cnt=0;if(!x)putchar('0');if(x<0)putchar('-'),x=-x;while(x)F[cnt++]=x%10+'0',x/=10;while(cnt)putchar(F[--cnt]);putchar(ch);}
namespace Main
{
    const int N=100010,mod=998244353;int ksm(int x,int y=mod-2){int res=1;for(;y;y>>=1,x=1ll*x*x%mod)if(y&1)res=1ll*res*x%mod;return res;}int n,m,k,A,B,a[N],head[N],to[N<<1],nxt[N<<1],tot,pre[N],dep[N],x,y,z,xx,yy,ans,anss;bool fl[N];void Add(int&x,int y){(x+=y)>=mod&&(x-=mod);}int add(int x,int y){return (x+=y)>=mod&&(x-=mod),x;}void link(int x,int y){to[++tot]=y,nxt[tot]=head[x],head[x]=tot;}
    struct nd{int x,y;int&operator[](int z){return z?y:x;}}f[N][3],h[N][4],tmp[3],s,S,zz;const nd E=(nd){0,0};nd operator|(nd x,nd y){return (nd){add(x.x,y.x),add(x.y,y.y)};}void operator|=(nd&x,nd y){Add(x.x,y.x),Add(x.y,y.y);}nd operator+(nd x,nd y){return (nd){(int)(1ll*x.x*y.x%mod),(int)((1ll*x.y*y.x+1ll*x.x*y.y)%mod)};}nd operator*(nd x,int y){return (nd){(int)(1ll*x.x*y%mod),(int)(1ll*x.y*y%mod)};}void operator+=(nd&x,nd y){x=x+y;}void mrg(nd*x,nd*y){for(int i=0;i<3;++i)tmp[i]=x[i];for(int i=0;i<3;++i)for(int j=0;j<3;++j)x[min(i+1,2)]|=(tmp[i]+(y[j]*(j?B:A)));}void mrg(nd&z,nd*y,nd&x,int d){for(int i=0;i<3;++i)z|=(x+(y[i]*(i+d>1?B:A)));}
    void Tag(int x){for(int i=0;i<3;++i)Add(f[x][i].y,f[x][i].x);}
    void dfs0(int x){dep[x]=dep[pre[x]]+1;for(int i=head[x];i;i=nxt[i])if(!dep[to[i]])pre[to[i]]=x,dfs0(to[i]);else if(dep[to[i]]+1<dep[x]){for(int j=x;j!=pre[to[i]];j=pre[j])a[++m]=j,fl[j]=1;}}void dfs(int x,int Fa){for(int i=head[x];i;i=nxt[i])if(to[i]!=Fa&&!fl[to[i]])dfs(to[i],x),mrg(f[x],f[to[i]]);Tag(x);for(int i=0;i<3;++i)ans=(ans+1ll*(i==2?B:A)*f[x][i].y)%mod;}
    void main()
    {
        n=read(),k=read(),z=ksm(mod+1-k),anss=ksm(mod+1-k,n),A=1ll*k*z%mod,B=z;for(int i=1;i<=n;++i)x=read(),y=read(),link(x,y),link(y,x),f[i][0]=(nd){1,0};
        dfs0(1),S=h[0][0]=(nd){1,0};for(int i=1;i<=m;++i)dfs(a[i],0),S=S+((f[a[i]][0]|f[a[i]][1]|f[a[i]][2])*B);Add(ans,S.y);
        for(int i=1;i<=m;++i)memset(h[i],0,sizeof(h[i])),s=E,h[i][0]=h[i-1][0],mrg(h[i][1],f[a[i]],h[i-1][0],1),mrg(h[i][1],f[a[i]],h[i-1][1],2),mrg(s,f[a[i]],h[i-1][1],1),Add(ans,s.y);
        for(int i=1;i<=m;++i)memset(h[i],0,sizeof(h[i])),mrg(h[i][0],f[a[i]],h[i-1][0],2),mrg(h[i][1],f[a[i]],h[i-1][0],1),h[i][2]=h[i-1][1]|h[i-1][2],mrg(h[i][3],f[a[i]],h[i-1][1],1),mrg(h[i][3],f[a[i]],h[i-1][2],1),mrg(h[i][3],f[a[i]],h[i-1][3],2);
        Add(ans,h[m][3].y),write(1ll*ans*anss%mod,'\n');
    }
}
int main()
{
    const bool base=0,IO=1;int T;if(!base)T=1;else if(IO)T=read();else ios::sync_with_stdio(0),cin>>T;for(;T--;)Main::main();
    return 0;
}
0