結果

問題 No.1614 Majority Painting on Tree
ユーザー 沙耶花
提出日時 2021-07-21 23:58:30
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,809 ms / 5,000 ms
コード長 1,812 bytes
コンパイル時間 3,714 ms
コンパイル使用メモリ 259,512 KB
最終ジャッジ日時 2025-01-23 05:22:38
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 45
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:102:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  102 |                 scanf("%d %d",&u,&v);
      |                 ~~~~~^~~~~~~~~~~~~~~

ソースコード

diff #
プレゼンテーションモードにする

#include <stdio.h>
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
using mint = modint998244353;
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define Inf 1000000000
struct combi{
    deque<mint> kaijou;
    deque<mint> kaijou_;
    
    combi(int n){
        kaijou.push_back(1);
        for(int i=1;i<=n;i++){
            kaijou.push_back(kaijou[i-1]*i);
        }
        
        mint b=kaijou[n].inv();
        
        kaijou_.push_front(b);
        for(int i=1;i<=n;i++){
            int k=n+1-i;
            kaijou_.push_front(kaijou_[0]*k);
        }
    }
    
    mint combination(int n,int r){
        if(r>n)return 0;
        mint a = kaijou[n]*kaijou_[r];
        a *= kaijou_[n-r];
        return a;
    }
    
    mint junretsu(int a,int b){
        mint x = kaijou_[a]*kaijou_[b];
        x *= kaijou[a+b];
        return x;
    }
    
    mint catalan(int n){
        return combination(2*n,n)/(n+1);
    }
    
};
combi Co(500000);
vector<vector<int>> E;
mint c;
vector<mint> dp;
mint INV;
void dfs(int cur,int p){
    rep(i,E[cur].size()){
        int to = E[cur][i];
        if(to==p)continue;
        dfs(to,cur);
        dp[cur] *= dp[to];
    }
    int d = E[cur].size();
    
    mint temp = 0;
    {
        mint X = 1;
        rep(i,E[cur].size())X *= c;
        temp += X;
    }
    
    {
        mint Y = 0;
        mint Temp = 1;
        rep(i,E[cur].size()){
            int remain = d-i;
            if(remain > d/2){
                
                Y += Co.combination(d,i) * Temp;
                
            }
            else break;
            Temp *= c-1;
        }
        Y *= c;
        
        temp -= Y;
    }
    temp += c;
    if(cur!=0)temp *= INV;
    dp[cur] *= temp;
}
    
    
int main(){
    
    int N,C;
    cin>>N>>C;
    
    E.resize(N);
    
    rep(i,N-1){
        int u,v;
        scanf("%d %d",&u,&v);
        u--;v--;
        E[u].push_back(v);
        E[v].push_back(u);
    }
    mint ans = 0;
    rep(i,C){
        c = C - i;
        mint temp = Co.combination(C,C-i);
        INV = c.inv();
        dp.assign(N,1);
        dfs(0,-1);
        
        
        temp *= dp[0];
        //cout<<temp.val()<<endl;
        if(i%2==1)temp *= -1;
        ans += temp;
    }
    
    cout<<ans.val()<<endl;
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0