結果

問題 No.1483 Many Graph in Namori
ユーザー vjudge1
提出日時 2025-05-22 15:56:49
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 83 ms / 2,000 ms
コード長 4,231 bytes
コンパイル時間 762 ms
コンパイル使用メモリ 79,404 KB
実行使用メモリ 21,012 KB
最終ジャッジ日時 2025-05-22 15:56:56
合計ジャッジ時間 5,057 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 56
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:40:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   40 |     scanf("%d%d",&n,&k);
      |     ~~~~~^~~~~~~~~~~~~~
main.cpp:41:36: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   41 |     for(int i=1,a,b;i<=n;i++) scanf("%d%d",&a,&b),g[a].push_back(b),g[b].push_back(a),deg[a]++,deg[b]++;
      |                               ~~~~~^~~~~~~~~~~~~~

ソースコード

diff # 

#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N=1e5+9,P=998244353;
int qmi(int a,int b){
    int res=1;
    while(b){
        if(b&1) res=(LL)res*a%P;
        a=(LL)a*a%P;
        b>>=1;
    }
    return res;
}
int n,k,x,y; bool on[N];
vector<int> g[N]; int deg[N];
int q[N],hh,tt=-1;
int ch[N],len;
int f[N][3][2],tmp[3][2];
int res;
int pre[N][2],suf[N][2];
void dfs(int u,int p){
    f[u][0][0]=f[u][0][1]=1;
    for(int &v:g[u]){
        if(v==p||on[v]) continue;
        dfs(v,u);
        memcpy(tmp,f[u],sizeof(tmp));
        for(int x1:{0,1,2}) for(int y1:{0,1}) for(int x2:{0,1,2}) for(int y2:{0,1}) if(!y1||!y2){
            f[u][min(x1+1,2)][y1+y2]=(f[u][min(x1+1,2)][y1+y2]+(LL)tmp[x1][y1]*f[v][x2][y2]%P*(x2?y:x))%P;
        } 
    }
    for(int x1:{0,1,2}) res=(res+(LL)f[u][x1][1]*(x1>=2?y:x))%P;
    // printf("dfs %d %d: ",u,res);
    // for(int x1:{0,1,2}) for(int y1:{0,1}) printf("%d ",f[u][x1][y1]); puts("");
}
int main(){
    scanf("%d%d",&n,&k);
    for(int i=1,a,b;i<=n;i++) scanf("%d%d",&a,&b),g[a].push_back(b),g[b].push_back(a),deg[a]++,deg[b]++;
    for(int i=1;i<=n;i++){
        on[i]=1;
        if(deg[i]==1) q[++tt]=i;
    }
    while(hh<=tt){
        int u=q[hh++];
        on[u]=0;
        for(int &v:g[u]) if(--deg[v]==1) q[++tt]=v;
    }
    y=qmi(1-k+P,P-2),x=(LL)k*y%P;
    for(int i=1;i<=n;i++) if(on[i]){
        int x=i;
        do{
            ch[++len]=x;
            for(int &u:g[x]) if(on[u]&&u!=ch[len-1]){
                x=u;
                break;
            }
        }while(x^i);
        break;
    }
    for(int i=1;i<=n;i++) if(on[i]) dfs(i,0);
    for(int i=1,pre[2]={0,0};i<=len;i++){
        int sm[2][2]={0,0};
        for(int x1:{0,1,2}) for(int y1:{0,1}) sm[!!x1][y1]=(sm[!!x1][y1]+f[ch[i]][x1][y1])%P;
        int tmp[2]={0,0},co[2]={0,0};
        for(int x1:{0,1}) for(int y1:{0,1}) tmp[y1]=(tmp[y1]+(LL)sm[x1][y1]*(x1?y:x))%P,co[y1]=(co[y1]+(LL)sm[x1][y1]*y)%P;
        res=(res+(LL)pre[0]*tmp[1]+(LL)pre[1]*tmp[0])%P;
        int p0=pre[0],p1=pre[1];
        pre[0]=(tmp[0]+(LL)p0*co[0])%P;
        pre[1]=(tmp[1]+(LL)p1*co[0]+(LL)p0*co[1])%P;
    }
    // printf("%d\n",res);
    for(int i=1,mul[2]={1,0};i<=len;i++){
        int sm[2][2]={0,0};
        for(int x1:{0,1,2}) for(int y1:{0,1}) sm[!!x1][y1]=(sm[!!x1][y1]+f[ch[i]][x1][y1])%P;
        int tmp[2]={0,0},co[2]={0,0};
        for(int x1:{0,1}) for(int y1:{0,1}) tmp[y1]=(tmp[y1]+(LL)sm[x1][y1]*(x1?y:x))%P,co[y1]=(co[y1]+(LL)sm[x1][y1]*y)%P;
        pre[i][0]=(LL)mul[0]*tmp[0]%P;
        pre[i][1]=((LL)mul[0]*tmp[1]+(LL)mul[1]*tmp[0])%P;
        int m0=mul[0],m1=mul[1];
        mul[0]=(LL)m0*co[0]%P;
        mul[1]=((LL)m1*co[0]+(LL)m0*co[1])%P;
        // printf("pre %d %d %d %d %d %d %d %d %d\n",ch[i],tmp[0],tmp[1],pre[i][0],pre[i][1],mul[0],mul[1],co[0],co[1]);
    }
    for(int i=len,mul[2]={1,0};i;i--){
        int sm[2][2]={0,0};
        for(int x1:{0,1,2}) for(int y1:{0,1}) sm[!!x1][y1]=(sm[!!x1][y1]+f[ch[i]][x1][y1])%P;
        int tmp[2]={0,0},co[2]={0,0};
        for(int x1:{0,1}) for(int y1:{0,1}) tmp[y1]=(tmp[y1]+(LL)sm[x1][y1]*(x1?y:x))%P,co[y1]=(co[y1]+(LL)sm[x1][y1]*y)%P;
        suf[i][0]=(LL)mul[0]*tmp[0]%P;
        suf[i][1]=((LL)mul[0]*tmp[1]+(LL)mul[1]*tmp[0])%P;
        int m0=mul[0],m1=mul[1];
        mul[0]=(LL)m0*co[0]%P;
        mul[1]=((LL)m1*co[0]+(LL)m0*co[1])%P;
        // printf("suf %d %d %d %d %d %d %d %d %d\n",ch[i],tmp[0],tmp[1],suf[i][0],suf[i][1],mul[0],mul[1],co[0],co[1]);
    }
    for(int i=len;i;i--) for(int o:{0,1}) suf[i][o]=(suf[i][o]+suf[i+1][o])%P;
    for(int i=1;i<len;i++) res=(res+(LL)pre[i][0]*suf[i+1][1]+(LL)pre[i][1]*suf[i+1][0])%P;
    // printf("%d\n",res);
    int mul[2]={1,0};
    for(int i=1;i<=len;i++){
        int sm[2]={0,0};
        for(int x1:{0,1,2}) for(int y1:{0,1}) sm[y1]=(sm[y1]+(LL)f[ch[i]][x1][y1]*y)%P;
        int m0=mul[0],m1=mul[1];
        mul[0]=(LL)m0*sm[0]%P;
        mul[1]=((LL)m0*sm[1]+(LL)m1*sm[0])%P;
        // printf("--%d %d %d %d %d\n",ch[i],sm[0],sm[1],mul[0],mul[1]);
    }
    res=(res+mul[1])%P;
    // printf("%d\n",res);
    res=(LL)res*qmi(1-k+P,n)%P;
    printf("%d\n",res);
    return 0;
}
0