求助P5643 80分
  • 板块题目总版
  • 楼主SentoAyaka
  • 当前回复0
  • 已保存回复0
  • 发布时间2022/7/12 19:57
  • 上次更新2023/10/27 20:47:47
查看原帖
求助P5643 80分
89667
SentoAyaka楼主2022/7/12 19:57

测试点#2:wrong answer Too short on line 2.

不知道为什么

#include<bits/stdc++.h>
#define db double
#define int long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
using namespace std;
inline int read(){
    register int x=0,f=1;register char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
inline void write(int x){
    if(x<0)x=-x,putchar('-');
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
const int N=(1<<18)+5,mod=998244353;
int A[20],B[20],cnt[N],f[N];
vector<int>G[20];
int Qpow(int b,int p,int k){
    int res=1ll;
    while(p){
        if(p&1)(res*=b)%=k;
        (b*=b)%=k;p>>=1;
    }
    return res;
}
void dfs(int x,int fa,int S){
    if(S&(1<<x))return ;
    int deg=G[x].size(),sumA=0,sumB=0;
    for(int i=0;i<G[x].size();i++){
        int y=G[x][i];if(y==fa)continue;
        dfs(y,x,S);
        (sumA+=A[y])%=mod;
        (sumB+=B[y])%=mod;
    }
    A[x]=Qpow(deg-sumA,mod-2,mod),B[x]=A[x]*(sumB+deg)%mod;
}
void FWT_OR(int *f,int n,int ty=1){
    for(int h=2;h<=n;h<<=1){
        for(int i=0;i<n;i+=h){
            for(int j=i;j<i+h/2;j++){
                f[j+h/2]=(f[j+h/2]+f[j]*ty)%mod;
            }
        }
    }
}
signed main(){
    freopen("read.in","r",stdin);
    int n=read(),q=read(),X=read()-1,S=(1<<n);
    for(int i=1;i<n;i++){
        int u=read()-1,v=read()-1;
        G[u].pb(v);G[v].pb(u);
    }
    for(int i=1;i<S;i++){
        cnt[i]=cnt[i>>1]+(i&1);
        memset(A,0,sizeof A);memset(B,0,sizeof B);
        dfs(X,0,i);
        f[i]=((cnt[i]&1)?1:-1)*B[X]%mod;
        //cout<<f[i]<<' ';
    }
    //cout<<"\n";
    FWT_OR(f,S);
    while(q--){
        int k=read(),T=0;
        for(int i=1;i<=k;i++)T+=(1<<(read()-1));
        cout<<(f[T]%mod+mod)%mod<<"\n";
    }
    return 0;
}
2022/7/12 19:57
加载中...