QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#564880	#4811. Be Careful	Harry27182	AC ✓	780ms	53928kb	C++14	3.1kb	2024-09-15 16:29:46	2024-09-15 16:29:47

Judging History

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

[2024-09-15 16:29:47]
评测

测评结果：AC
用时：780ms
内存：53928kb

查看

[2024-09-15 16:29:46]
提交

answer

#include<bits/stdc++.h>
using namespace std;
vector<int>e[205],e1[205],e2[205];
int f[100005],g[100005][205],tmp[100005][205],tmp2[100005][205],tmp3[100005];
int dp[205][205],n,suf[205][205],C[205][205],pw[205][205],u,v;
const int mod=998244353;
void Add(int &x,int y){x=(x+y>=mod?x+y-mod:x+y);}
void dfs(int u,int fa)
{
	if(e[u].size()==1&&fa)return;
	int num=0,B=0,mn=0x3f3f3f3f,mx=0;vector<int>vec;
	for(int i=0;i<e[u].size();i++)
	{
		int v=e[u][i];
		if(v==fa)continue;
		dfs(v,u);
		if(e[v].size()==1)num++;
		else vec.emplace_back(e[v].size()),mx=max(mx,(int)e[v].size());
	}
	sort(vec.begin(),vec.end());
	for(int i=0;i<=vec.size();i++)
	{
		if((i==0?0:vec[i-1])+vec.size()-i+(i>10)<=mn)
		{
			mn=(i==0?0:vec[i-1])+vec.size()-i;
			B=(i==0?0:vec[i-1]);
		}
	}
	for(int i=0;i<e[u].size();i++)
	{
		int v=e[u][i];
		if(v==fa)continue;
		if(e[v].size()==1);
		else if(e[v].size()<=B)e1[u].emplace_back(v);
		else e2[u].emplace_back(v);
	}
	for(int i=0;i<(1<<B);i++)f[i]=0;
	f[0]=1;
	for(int i=0;i<e1[u].size();i++)
	{
		int v=e1[u][i];
		for(int s=0;s<(1<<B);s++)tmp3[s]=f[s],f[s]=0;
		for(int s=0;s<(1<<B);s++)
		{
			if(!tmp[s])continue;
			for(int j=0;j<B;j++)Add(f[s|(1<<j)],1ll*tmp3[s]*dp[v][j]%mod);
		}
	}
	for(int t=0;t<(1<<B);t++)
	{
		if(!f[t])continue;
		for(int s=0;s<(1<<e2[u].size());s++)for(int j=0;j<=num;j++)g[s][j]=0;
		g[0][0]=1;
		for(int i=0;i<=e[u].size();i++)
		{
			for(int s=0;s<(1<<e2[u].size());s++)
			{
				for(int j=0;j<=num;j++)
				{
					if(!g[s][j])continue;
					if(i<B&&((t>>i)&1))continue;
					int now=1ll*f[t]*g[s][j]%mod;
					for(int j=0;j<e2[u].size();j++)if(!((s>>j)&1))now=1ll*now*suf[e2[u][j]][i+1]%mod;
					Add(dp[u][i],1ll*now*pw[n-i][num-j]%mod);
				}
			}
			for(int s=0;s<(1<<e2[u].size());s++)
			{
				for(int j=0;j<=num;j++)tmp[s][j]=g[s][j];
			}
			for(int j=0;j<e2[u].size();j++)
			{
				for(int s=0;s<(1<<e2[u].size());s++)
				{
					if((s>>j)&1)continue;
					for(int k=0;k<=num;k++)
					{
						if(!g[s][k])continue;
						Add(g[s|(1<<j)][k],1ll*g[s][k]*dp[e2[u][j]][i]%mod);
					}
				}
			}
			for(int s=0;s<(1<<e2[u].size());s++)
			{
				for(int j=0;j<=num;j++)tmp2[s][j]=g[s][j],g[s][j]=0;
				for(int j=0;j<=num;j++)
				{
					if(!tmp2[s][j])continue;
					for(int k=j;k<=num;k++)Add(g[s][k],1ll*tmp2[s][j]*C[num-j][k-j]%mod);
				}
			}
			if(i>=B||!((t>>i)&1))
			{
				for(int s=0;s<(1<<e2[u].size());s++)
				{
					for(int j=0;j<=num;j++)Add(g[s][j],mod-tmp[s][j]);
				}
			}
		}
	}
	for(int i=n;i>=0;i--)
	{
		suf[u][i]=suf[u][i+1];
		Add(suf[u][i],dp[u][i]);
	}
	//for(int i=0;i<=n;i++)cout<<u<<' '<<i<<' '<<dp[u][i]<<'\n';
}
int main()
{
	//freopen("mex.in","r",stdin);
	//freopen("mex.out","w",stdout);
	cin.tie(0)->sync_with_stdio(0);
	cin>>n;
	for(int i=1;i<n;i++)cin>>u>>v,e[u].emplace_back(v),e[v].emplace_back(u);
	for(int i=0;i<=n;i++)
	{
		pw[i][0]=1;
		for(int j=1;j<=n;j++)pw[i][j]=1ll*pw[i][j-1]*i%mod;
	}
	C[0][0]=1;
	for(int i=1;i<=n;i++)
	{
		C[i][0]=1;
		for(int j=1;j<=i;j++)C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
	}
	dfs(1,0); 
	for(int i=0;i<=n;i++)cout<<dp[1][i]<<'\n';
	return 0;
}

源文件, 语言: C++14

详细

Test #1:

score: 100

Accepted

time: 1ms

memory: 8012kb

input:

output:

result:

ok 6 numbers

Test #2:

score: 0

Accepted

time: 0ms

memory: 9716kb

input:

output:

result:

ok 9 numbers

Test #3:

score: 0

Accepted

time: 1ms

memory: 7664kb

input:

3
1 2
2 3

output:

result:

ok 4 number(s): "1 3 0 0"

Test #4:

score: 0

Accepted

time: 0ms

memory: 7708kb

input:

2
1 2

output:

2
1
0

result:

ok 3 number(s): "2 1 0"

Test #5:

score: 0

Accepted

time: 0ms

memory: 9864kb

input:

output:

result:

ok 11 numbers

Test #6:

score: 0

Accepted

time: 1ms

memory: 7764kb

input:

output:

result:

ok 11 numbers

Test #7:

score: 0

Accepted

time: 1ms

memory: 10068kb

input:

output:

result:

ok 11 numbers

Test #8:

score: 0

Accepted

time: 1ms

memory: 9880kb

input:

output:

result:

ok 11 numbers

Test #9:

score: 0

Accepted

time: 0ms

memory: 9836kb

input:

output:

result:

ok 15 numbers

Test #10:

score: 0

Accepted

time: 1ms

memory: 9856kb

input:

output:

result:

ok 21 numbers

Test #11:

score: 0

Accepted

time: 1ms

memory: 9812kb

input:

output:

result:

ok 22 numbers

Test #12:

score: 0

Accepted

time: 1ms

memory: 9896kb

input:

output:

result:

ok 23 numbers

Test #13:

score: 0

Accepted

time: 2ms

memory: 10036kb

input:

output:

result:

ok 24 numbers

Test #14:

score: 0

Accepted

time: 0ms

memory: 8080kb

input:

output:

result:

ok 25 numbers

Test #15:

score: 0

Accepted

time: 0ms

memory: 10112kb

input:

output:

result:

ok 25 numbers

Test #16:

score: 0

Accepted

time: 4ms

memory: 10380kb

input:

output:

result:

ok 201 numbers

Test #17:

score: 0

Accepted

time: 0ms

memory: 8328kb

input:

output:

result:

ok 201 numbers

Test #18:

score: 0

Accepted

time: 2ms

memory: 10476kb

input:

output:

result:

ok 201 numbers

Test #19:

score: 0

Accepted

time: 2ms

memory: 10252kb

input:

output:

result:

ok 200 numbers

Test #20:

score: 0

Accepted

time: 0ms

memory: 8256kb

input:

output:

result:

ok 201 numbers

Test #21:

score: 0

Accepted

time: 2ms

memory: 10284kb

input:

output:

result:

ok 201 numbers

Test #22:

score: 0

Accepted

time: 0ms

memory: 10388kb

input:

output:

result:

ok 201 numbers

Test #23:

score: 0

Accepted

time: 2ms

memory: 10132kb

input:

output:

result:

ok 201 numbers

Test #24:

score: 0

Accepted

time: 4ms

memory: 14784kb

input:

output:

result:

ok 201 numbers

Test #25:

score: 0

Accepted

time: 5ms

memory: 16348kb

input:

output:

result:

ok 201 numbers

Test #26:

score: 0

Accepted

time: 3ms

memory: 28612kb

input:

output:

result:

ok 201 numbers

Test #27:

score: 0

Accepted

time: 17ms

memory: 53928kb

input:

output:

result:

ok 201 numbers

Test #28:

score: 0

Accepted

time: 23ms

memory: 28836kb

input:

output:

result:

ok 201 numbers

Test #29:

score: 0

Accepted

time: 10ms

memory: 24364kb

input:

output:

result:

ok 201 numbers

Test #30:

score: 0

Accepted

time: 8ms

memory: 12008kb

input:

output:

result:

ok 201 numbers

Test #31:

score: 0

Accepted

time: 6ms

memory: 12564kb

input:

output:

result:

ok 201 numbers

Test #32:

score: 0

Accepted

time: 3ms

memory: 10504kb

input:

output:

result:

ok 201 numbers

Test #33:

score: 0

Accepted

time: 7ms

memory: 12632kb

input:

output:

result:

ok 201 numbers

Test #34:

score: 0

Accepted

time: 2ms

memory: 9928kb

input:

output:

result:

ok 201 numbers

Test #35:

score: 0

Accepted

time: 0ms

memory: 10056kb

input:

output:

result:

ok 201 numbers

Test #36:

score: 0

Accepted

time: 2ms

memory: 8380kb

input:

output:

result:

ok 201 numbers

Test #37:

score: 0

Accepted

time: 5ms

memory: 10204kb

input:

output:

result:

ok 201 numbers

Test #38:

score: 0

Accepted

time: 1ms

memory: 10184kb

input:

output:

result:

ok 201 numbers

Test #39:

score: 0

Accepted

time: 1ms

memory: 8432kb

input:

output:

result:

ok 201 numbers

Test #40:

score: 0

Accepted

time: 0ms

memory: 10728kb

input:

output:

result:

ok 201 numbers

Test #41:

score: 0

Accepted

time: 0ms

memory: 8364kb

input:

output:

result:

ok 201 numbers

Test #42:

score: 0

Accepted

time: 2ms

memory: 10144kb

input:

output:

result:

ok 201 numbers

Test #43:

score: 0

Accepted

time: 0ms

memory: 10420kb

input:

output:

result:

ok 201 numbers

Test #44:

score: 0

Accepted

time: 0ms

memory: 10392kb

input:

output:

result:

ok 201 numbers

Test #45:

score: 0

Accepted

time: 2ms

memory: 10312kb

input:

output:

result:

ok 201 numbers

Test #46:

score: 0

Accepted

time: 195ms

memory: 10544kb

input:

output:

result:

ok 201 numbers

Test #47:

score: 0

Accepted

time: 385ms

memory: 12624kb

input:

output:

result:

ok 201 numbers

Test #48:

score: 0

Accepted

time: 63ms

memory: 8304kb

input:

output:

result:

ok 201 numbers

Test #49:

score: 0

Accepted

time: 13ms

memory: 10264kb

input:

output:

result:

ok 201 numbers

Test #50:

score: 0

Accepted

time: 505ms

memory: 10384kb

input:

output:

result:

ok 201 numbers

Test #51:

score: 0

Accepted

time: 105ms

memory: 10452kb

input:

output:

result:

ok 201 numbers

Test #52:

score: 0

Accepted

time: 149ms

memory: 10308kb

input:

output:

result:

ok 201 numbers

Test #53:

score: 0

Accepted

time: 19ms

memory: 9796kb

input:

output:

result:

ok 201 numbers

Test #54:

score: 0

Accepted

time: 15ms

memory: 10176kb

input:

output:

result:

ok 201 numbers

Test #55:

score: 0

Accepted

time: 95ms

memory: 10836kb

input:

output:

result:

ok 201 numbers

Test #56:

score: 0

Accepted

time: 63ms

memory: 9860kb

input:

output:

result:

ok 201 numbers

Test #57:

score: 0

Accepted

time: 32ms

memory: 9744kb

input:

output:

result:

ok 201 numbers

Test #58:

score: 0

Accepted

time: 45ms

memory: 10328kb

input:

output:

result:

ok 201 numbers

Test #59:

score: 0

Accepted

time: 22ms

memory: 10492kb

input:

output:

result:

ok 201 numbers

Test #60:

score: 0

Accepted

time: 12ms

memory: 8268kb

input:

output:

result:

ok 201 numbers

Test #61:

score: 0

Accepted

time: 41ms

memory: 10548kb

input:

output:

result:

ok 201 numbers

Test #62:

score: 0

Accepted

time: 58ms

memory: 10024kb

input:

output:

result:

ok 201 numbers

Test #63:

score: 0

Accepted

time: 73ms

memory: 8532kb

input:

output:

result:

ok 201 numbers

Test #64:

score: 0

Accepted

time: 43ms

memory: 8248kb

input:

output:

result:

ok 201 numbers

Test #65:

score: 0

Accepted

time: 29ms

memory: 10120kb

input:

output:

result:

ok 201 numbers

Test #66:

score: 0

Accepted

time: 198ms

memory: 11888kb

input:

output:

result:

ok 201 numbers

Test #67:

score: 0

Accepted

time: 780ms

memory: 21088kb

input:

output:

result:

ok 201 numbers

Test #68:

score: 0

Accepted

time: 552ms

memory: 10192kb

input:

output:

result:

ok 201 numbers

Test #69:

score: 0

Accepted

time: 225ms

memory: 8628kb

input:

output:

result:

ok 201 numbers

Test #70:

score: 0

Accepted

time: 161ms

memory: 10340kb

input:

output:

result:

ok 201 numbers

Test #71:

score: 0

Accepted

time: 233ms

memory: 10032kb

input:

output:

result:

ok 201 numbers

Test #72:

score: 0

Accepted

time: 5ms

memory: 8268kb

input:

output:

result:

ok 201 numbers

Test #73:

score: 0

Accepted

time: 34ms

memory: 9964kb

input:

output:

395281256
483636032
44470315
764274255
768052736
172694762
50838859
156746114
244891434
863727019
813260101
485593277
478254883
518976274
641070905
996965890
5686802
768465347
1559198
841243941
58707679
454112478
223277062
223885387
907437049
795048480
596043388
423066416
865205173
44024428
65729859...

result:

ok 201 numbers

Test #74:

score: 0

Accepted

time: 98ms

memory: 14880kb

input:

output:

result:

ok 201 numbers

Test #75:

score: 0

Accepted

time: 57ms

memory: 10356kb

input:

output:

result:

ok 201 numbers

Test #76:

score: 0

Accepted

time: 69ms

memory: 8360kb

input:

output:

result:

ok 201 numbers

Test #77:

score: 0

Accepted

time: 17ms

memory: 10640kb

input:

output:

result:

ok 201 numbers

Test #78:

score: 0

Accepted

time: 37ms

memory: 10212kb

input:

output:

result:

ok 201 numbers

Test #79:

score: 0

Accepted

time: 22ms

memory: 10280kb

input:

output:

result:

ok 201 numbers

Test #80:

score: 0

Accepted

time: 9ms

memory: 9876kb

input:

output:

result:

ok 201 numbers

Test #81:

score: 0

Accepted

time: 48ms

memory: 10512kb

input:

output:

result:

ok 201 numbers

Test #82:

score: 0

Accepted

time: 127ms

memory: 10520kb

input:

output:

result:

ok 201 numbers

Test #83:

score: 0

Accepted

time: 18ms

memory: 10176kb

input:

output:

47475654
6487663
698179434
32467313
910556719
105080631
70504102
988140147
93709742
185078941
653271014
878067535
198144013
387766498
25783505
914674612
119067257
733211621
32730486
658348483
920709040
157915195
703709826
615976595
603974535
172801509
67871532
455367125
770452155
473168244
215381567...

result:

ok 201 numbers

Test #84:

score: 0

Accepted

time: 73ms

memory: 10508kb

input:

output:

result:

ok 201 numbers

Test #85:

score: 0

Accepted

time: 25ms

memory: 10288kb

input:

output:

result:

ok 201 numbers

Test #86:

score: 0

Accepted

time: 0ms

memory: 10728kb

input:

output:

result:

ok 201 numbers

Test #87:

score: 0

Accepted

time: 2ms

memory: 8600kb

input:

output:

result:

ok 201 numbers

Test #88:

score: 0

Accepted

time: 2ms

memory: 8364kb

input:

output:

result:

ok 201 numbers