QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#408422#4811. Be Carefulchenxinyang2006WA 5ms38648kbC++208.4kb2024-05-10 11:16:412024-05-10 11:16:43

Judging History

你现在查看的是最新测评结果

  • [2024-05-10 11:16:43]
  • 评测
  • 测评结果:WA
  • 用时:5ms
  • 内存:38648kb
  • [2024-05-10 11:16:41]
  • 提交

answer

#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define eb emplace_back
#define SZ(S) (int)S.size()
#define mod 998244353
//#define mod 1000000007
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
using namespace std;

template <class T>
void chkmax(T &x,T y){
    if(x < y) x = y;
}

template <class T>
void chkmin(T &x,T y){
    if(x > y) x = y;
}

inline int popcnt(int x){
    return __builtin_popcount(x);
}

inline int ctz(int x){
    return __builtin_ctz(x);
}

template <int P>
class mod_int
{
    using Z = mod_int;

private:
    static int mo(int x) { return x < 0 ? x + P : x; }

public:
    int x;
    int val() const { return x; }
    mod_int() : x(0) {}
    template <class T>
    mod_int(const T &x_) : x(x_ >= 0 && x_ < P ? static_cast<int>(x_) : mo(static_cast<int>(x_ % P))) {}
    bool operator==(const Z &rhs) const { return x == rhs.x; }
    bool operator!=(const Z &rhs) const { return x != rhs.x; }
    Z operator-() const { return Z(x ? P - x : 0); }
    Z pow(long long k) const
    {
        Z res = 1, t = *this;
        while (k)
        {
            if (k & 1)
                res *= t;
            if (k >>= 1)
                t *= t;
        }
        return res;
    }
    Z &operator++()
    {
        x < P - 1 ? ++x : x = 0;
        return *this;
    }
    Z &operator--()
    {
        x ? --x : x = P - 1;
        return *this;
    }
    Z operator++(int)
    {
        Z ret = x;
        x < P - 1 ? ++x : x = 0;
        return ret;
    }
    Z operator--(int)
    {
        Z ret = x;
        x ? --x : x = P - 1;
        return ret;
    }
    Z inv() const { return pow(P - 2); }
    Z &operator+=(const Z &rhs)
    {
        (x += rhs.x) >= P && (x -= P);
        return *this;
    }
    Z &operator-=(const Z &rhs)
    {
        (x -= rhs.x) < 0 && (x += P);
        return *this;
    }
    Z operator-()
    {
        return -x;
    }
    Z &operator*=(const Z &rhs)
    {
        x = 1ULL * x * rhs.x % P;
        return *this;
    }
    Z &operator/=(const Z &rhs) { return *this *= rhs.inv(); }
#define setO(T, o)                                  \
    friend T operator o(const Z &lhs, const Z &rhs) \
    {                                               \
        Z res = lhs;                                \
        return res o## = rhs;                       \
    }
    setO(Z, +) setO(Z, -) setO(Z, *) setO(Z, /)
#undef setO
    
    friend istream& operator>>(istream& is, mod_int& x)
    {
        long long tmp;
        is >> tmp;
        x = tmp;
        return is;
    }
    friend ostream& operator<<(ostream& os, const mod_int& x)
    {
        os << x.val();
        return os;
    }
};

using Z = mod_int<mod>;
Z power(Z p,ll k){
    Z ans = 1;
    while(k){
        if(k % 2 == 1) ans *= p;
        p *= p;
        k /= 2;
    }
    return ans;
}
int n;
vector <int> G[205];

int sz[205];
Z cof[205][205],C[205][205],P[205][205];//cof[i][j],i 个 [0,n] 整数,要求有 j 种值出现 >= 1 次
Z val[205][205],sval[205][205],f[1 << 21],g[1 << 21];
Z comb[1 << 21],prd[1 << 21];
vector <Z> dp[1 << 21],ndp[1 << 21];
int _l,idx[205];

ll cst(int b,int l,int k,int sons){
    if(b + l >= 25) return inf;
    return (1 << b) * (ll)sons + l * (1 << (b + l)) + (((ll)sons * k * l) << l);
}

void dfs(int u,int fa){
    int leaf = 0;
    for(int v:G[u]){
        if(v == fa) continue;
        dfs(v,u);
        sz[u] += sz[v];
        if(SZ(G[v]) == 1) leaf++;
    }
    if(SZ(G[u]) == 1 && u != 1) return;
    sz[u] += leaf;

    int B = inf,l = inf,qwq;
    rep(b,0,22){
        qwq = 0;
        for(int v:G[u]) if(v != fa && SZ(G[v]) > max(1,b)) qwq++;
        if(B == inf || cst(b,qwq,leaf,SZ(G[u])) < cst(B,l,leaf,SZ(G[u]))){
            B = b;
            l = qwq;
        }
    }

    fill(f,f + (1 << B),0);
    f[0] = 1;
    for(int v:G[u]){
        if(v == fa) continue;

        if(SZ(G[v]) == 1){
            leaf++;
            continue;
        }else if(SZ(G[v]) > B){
            continue;
        }
        
        rep(i,0,SZ(G[v]) - 1){
            rep(S,0,(1 << B) - 1) g[S | (1 << i)] += f[S] * val[v][i];
        }
        rep(S,0,(1 << B) - 1){
            f[S] = g[S];
            g[S] = 0;
        }
    }
//    printf("slv %d B=%d l=%d\n",u,B,l);
//    rep(S,0,(1 << B) - 1) printf("%d ",f[S].val());
//    printf("\n");
 
    _l = 0;
    for(int v:G[u]) if(v != fa && SZ(G[v]) > max(1,B)) idx[_l++] = v;
//    rep(i,0,_l - 1) printf("%d ",idx[i]);
//    printf("\n");
    rep(S,0,(1 << (B + l)) - 1){
        dp[S].resize(1);
        dp[S][0] = 0;
    }
    rep(S,0,(1 << B) - 1) dp[S << l][0] = f[S];
    //[0,B-1] old,[B,B+l-1] new
    rep(i,0,B - 1){
        rep(s,0,l - 1){
            rep(_S,0,(1 << (B - i)) - 1){
                rep(SS,_S << l,((_S + 1) << l) - 1){
                    if((SS >> s) & 1) continue;
                    rep(k,0,i) dp[SS | (1 << l) | (1 << s)][k] += dp[SS][k] * val[idx[s]][i];      
                }                
            }               
        }

        rep(S,0,(1 << (l + B - i - 1)) - 1){
            ndp[S].resize(i + 2);
            dp[S].resize(i + 2);
        }
        rep(_S,0,(1 << (B - i)) - 1){
            rep(SS,0,(1 << l) - 1){
                if(_S & 1) rep(k,0,i) ndp[(_S >> 1) << l | SS][k] += dp[(_S << l) | SS][k];            
                else rep(k,0,i) ndp[(_S >> 1) << l | SS][k + 1] += dp[(_S << l) | SS][k];  
            }
        }
        rep(S,0,(1 << (l + B - i - 1)) - 1){
            copy(ndp[S].begin(),ndp[S].begin() + i + 2,dp[S].begin());
            fill(ndp[S].begin(),ndp[S].begin() + i + 2,0);
            rep(k,0,i + 1) comb[S & ((1 << l) - 1)] += dp[S][k] * cof[leaf][k];
        }

        prd[0] = 1;
        rep(S,1,(1 << l) - 1){
            int p = ctz(S);
            prd[S] = prd[S - (1 << p)] * sval[idx[p]][i + 1];
        }
        rep(S,0,(1 << l) - 1){
            val[u][i] += comb[S] * prd[(1 << l) - 1 - S];
            comb[S] = 0;
        }
    }
    rep(S,0,(1 << l) - 1){
        dp[S].resize(leaf + 1);
        ndp[S].resize(leaf + 1);
//        rep(k,0,leaf) printf("%d ",dp[S][k].val());
//        printf("\n");
    }
//    printf("\n");
    rep(i,B,SZ(G[u]) - 1){
        rep(s,0,l - 1){
            rep(S,0,(1 << l) - 1){
                if((S >> s) & 1) continue;
                rep(k,0,leaf) ndp[S + (1 << s)][k] += (dp[S][k] + ndp[S][k]) * val[idx[s]][i];
            }
        }
        prd[0] = 1;
        rep(S,1,(1 << l) - 1){
            int p = ctz(S);
            prd[S] = prd[S - (1 << p)] * sval[idx[p]][i + 1];
        }
//        printf("state %d\n",i);
        rep(S,0,(1 << l) - 1){
            per(k,leaf,1) dp[S][k] = dp[S][k - 1];
            dp[S][0] = 0;
            rep(k,0,leaf){
                dp[S][k] += ndp[S][k];
                val[u][i] += dp[S][k] * prd[(1 << l) - 1 - S] * cof[leaf][k];
                ndp[S][k] = 0;
            }
//            rep(k,0,leaf) printf("%d ",dp[S][k].val());
//            printf("\n"); 
        }
    }
/*    printf("limit info of %d\n",u);
    rep(i,0,SZ(G[u]) - 1) printf("%d ",val[u][i].val());
    printf("\n");*/
    per(i,SZ(G[u]),1) val[u][i] = val[u][i - 1] - val[u][i];
    val[u][0] = P[n + 1][sz[u]] - val[u][0];

    per(i,SZ(G[u]),0) sval[u][i] = sval[u][i + 1] + val[u][i];
//    printf("dp info of %d\n",u);
//    rep(i,0,SZ(G[u]) - 1) printf("%d ",val[u][i].val());
//    printf("\n");
    //sval suf sum of val
}

int main(){
//    freopen("test.in","r",stdin);
    scanf("%d",&n);
    rep(i,0,n + 1){
        P[i][0] = 1;
        rep(j,1,n) P[i][j] = P[i][j - 1] * i;
    }
    rep(i,0,n){
        C[i][0] = 1;
        rep(j,1,i) C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
    }
    rep(i,0,n){
        rep(j,0,n){
            rep(k,0,j){
                if(k & 1) cof[i][j] -= C[j][k] * P[n + 1 - k][i];
                else cof[i][j] += C[j][k] * P[n + 1 - k][i];
            }
        }
    }
    rep(i,1,n - 1){
        int u,v;
        scanf("%d%d",&u,&v);
        G[u].eb(v);G[v].eb(u);
    }
    dfs(1,0);
    rep(i,0,n) printf("%d\n",val[1][i].val());
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 5ms
memory: 38648kb

input:

5
1 2
1 3
2 4
2 5

output:

15695
998231196
998242031
0
0
0

result:

wrong answer 1st numbers differ - expected: '55', found: '15695'