QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#74479 | #4811. Be Careful | Appleblue17 | WA | 4ms | 37320kb | C++14 | 3.5kb | 2023-02-01 22:41:13 | 2023-02-01 22:41:14 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=205,M=1e6+5,mod=998244353;
int n;
int mul[N],inv[N],S2[N][N],pre[N][N][N];
vector <int> G[N];
int ksm(int a,int x){
int tot=1;
while(x){
if(x & 1ll) tot=1ll*tot*a%mod;
a=1ll*a*a%mod;
x>>=1ll;
}
return tot;
}
void gmod(int &x){
x%=mod;
}
void init(int lim){
mul[0]=inv[0]=1;
for(int i=1;i<=lim;i++) mul[i]=1ll*mul[i-1]*i%mod;
inv[lim]=ksm(mul[lim],mod-2);
for(int i=lim-1;i>=1;i--) inv[i]=1ll*inv[i+1]*(i+1)%mod;
S2[0][0]=1;
for(int i=1;i<=lim;i++){
for(int j=1;j<=i;j++){
S2[i][j]=(S2[i-1][j-1]+1ll*S2[i-1][j]*j%mod)%mod;
}
}
// for(int c=0;c<=lim;c++){
// for(int p=0;p<=c;p++){
// for(int i=0;i<=c;i++)
// gmod(pre[c][p]+=1ll*inv[c-i]%mod*inv[i]%mod*S2[i][p]%mod*ksm(n-t,c-i)%mod);
// }
// }
}
int cal(int c,int p,int x){
if(pre[c][p][x]!=-1) return pre[c][p][x];
int tot=0;
for(int i=0;i<=c;i++)
gmod(tot+=1ll*inv[c-i]%mod*inv[i]%mod*S2[i][p]%mod*ksm(x,c-i)%mod);
return pre[c][p][x]=1ll*tot*mul[c]%mod*mul[p]%mod;
}
int dp[N][N],sdp[N][N];
int f[2][M],fid;
int g[2][M][N],gid;
void dfs(int u,int fa){
vector <int> A,B;
bool fl=0;
for(int v: G[u]){
if(v==fa) continue;
fl=1;
dfs(v,u);
}
if(!fl){
for(int i=0;i<=n;i++) dp[u][i]=1;
return ;
}
int mn=1e9,k;
for(int t=0;t<=n;t++){
int s=0;
for(int v: G[u]){
if(v==fa || G[v].size()==1) continue;
s+=((int)G[v].size()-1>=t);
}
if(s<t && t+s<=mn) mn=t+s,k=t;
}
int c=0;
for(int v: G[u]){
if(v==fa) continue;
if(G[v].size()==1) c++;
else if((int)G[v].size()-1<k) A.push_back(v);
else B.push_back(v);
}
fid=0;
for(int mac=0;mac<(1<<k);mac++) f[fid][mac]=0;
f[fid][0]=1;
for(int i=0;i<(int)A.size();i++){
int v=A[i];
fid^=1;
for(int mac=0;mac<(1<<k);mac++) f[fid][mac]=0;
for(int mac=0;mac<(1<<k);mac++){
for(int t=0;t<k;t++){
gmod(f[fid][mac | (1<<t)]+=1ll*f[fid^1][mac]*dp[v][t]%mod);
}
}
}
if(u==1){
cout<<"";
}
int m=A.size()+B.size()+c,l=B.size();
for(int mac0=0;mac0<(1<<k);mac0++){
gid=0;
for(int mac=0;mac<(1<<l);mac++)
memset(g[gid][mac],0,(m+1)<<2);
g[gid][0][0]=1;
int mac0_=mac0;
for(int t=0;t<=m;t++,mac0_>>=1){
int lim=min(c,t);
gid^=1;
for(int mac=0;mac<(1<<l);mac++)
for(int p=0;p<=lim;p++)
g[gid][mac][p]=g[gid^1][mac][p];
for(int i=0;i<l;i++){
int v=B[i];
for(int mac=(1<<l)-1;mac>=0;mac--){
if(mac>>i & 1) continue;
for(int p=0;p<=lim;p++){
gmod(g[gid][mac | (1<<i)][p]+=1ll*g[gid][mac][p]*dp[v][t]%mod);
}
}
}
for(int mac=0;mac<(1<<l);mac++){
for(int p=lim;p>=0;p--){
gmod(g[gid][mac][p+1]+=g[gid][mac][p]);
}
}
if(!(mac0_ & 1)){
for(int mac=0;mac<(1<<l);mac++){
int val=1;
for(int i=0;i<l;i++)
if(!(mac>>i & 1)) val=1ll*val*sdp[B[i]][t+1]%mod;
for(int p=0;p<=lim;p++){
if(!g[gid^1][mac][p]) continue;
int w=1ll*cal(c,p,n-t)*f[fid][mac0]%mod;
gmod(dp[u][t]+=1ll*g[gid^1][mac][p]*val%mod*w%mod);
gmod(g[gid][mac][p]+=mod-g[gid^1][mac][p]);
}
}
}
}
}
for(int i=n;i>=0;i--) gmod(sdp[u][i]=sdp[u][i+1]+dp[u][i]);
}
int main(){
// freopen("1.txt","r",stdin);
// freopen("2.txt","w",stdout);
init(N-5);
memset(pre,-1,sizeof(pre));
cin>>n;
for(int i=1;i<n;i++){
int u,v; scanf("%d%d",&u,&v);
G[u].push_back(v);
G[v].push_back(u);
}
dfs(1,0);
for(int i=0;i<=n;i++) cout<<dp[1][i]<<'\n';
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 4ms
memory: 37320kb
input:
5 1 2 1 3 2 4 2 5
output:
55 129 34 0 0 0
result:
wrong answer 2nd numbers differ - expected: '127', found: '129'