QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#267425#7677. Easy Diameter ProblemCrysflyWA 31ms496264kbC++174.3kb2023-11-27 11:25:022023-11-27 11:25:02

Judging History

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

  • [2023-11-27 11:25:02]
  • 评测
  • 测评结果:WA
  • 用时:31ms
  • 内存:496264kb
  • [2023-11-27 11:25:02]
  • 提交

answer

// what is matter? never mind. 
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,sse4,popcnt,abm,mmx,avx,avx2") 
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
#define ull unsigned long long
using namespace std;
inline int read()
{
	char c=getchar();int x=0;bool f=0;
	for(;!isdigit(c);c=getchar())f^=!(c^45);
	for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
	if(f)x=-x;return x;
}
 
#define mod 1000000007
struct modint{
	int x;
	modint(int o=0){x=o;}
	modint &operator = (int o){return x=o,*this;}
	modint &operator +=(modint o){return x=x+o.x>=mod?x+o.x-mod:x+o.x,*this;}
	modint &operator -=(modint o){return x=x-o.x<0?x-o.x+mod:x-o.x,*this;}
	modint &operator *=(modint o){return x=1ll*x*o.x%mod,*this;}
	modint &operator ^=(int b){
		modint a=*this,c=1;
		for(;b;b>>=1,a*=a)if(b&1)c*=a;
		return x=c.x,*this;
	}
	modint &operator /=(modint o){return *this *=o^=mod-2;}
	friend modint operator +(modint a,modint b){return a+=b;}
	friend modint operator -(modint a,modint b){return a-=b;}
	friend modint operator *(modint a,modint b){return a*=b;}
	friend modint operator /(modint a,modint b){return a/=b;}
	friend modint operator ^(modint a,int b){return a^=b;}
	friend bool operator ==(modint a,int b){return a.x==b;}
	friend bool operator !=(modint a,int b){return a.x!=b;}
	bool operator ! () {return !x;}
	modint operator - () {return x?mod-x:0;}
	bool operator <(const modint&b)const{return x<b.x;}
};
inline modint qpow(modint x,int y){return x^y;}

vector<modint> fac,ifac,iv;
inline void initC(int n)
{
	if(iv.empty())fac=ifac=iv=vector<modint>(2,1);
	int m=iv.size(); ++n;
	if(m>=n)return;
	iv.resize(n),fac.resize(n),ifac.resize(n);
	For(i,m,n-1){
		iv[i]=iv[mod%i]*(mod-mod/i);
		fac[i]=fac[i-1]*i,ifac[i]=ifac[i-1]*iv[i];
	}
}

modint C[605][605];

#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;

#define maxn 2000005
#define inf 0x3f3f3f3f

int n,m;
vi e[maxn];
modint f[605][305][305],g[605][305][305];
// what edge, diameter, rest cnt

int u[605],v[605];
int cnt[605][305];
int id[305][305];
void dfs(int u,int pa,int d,int*c){
	++c[d];
	for(auto v:e[u])if(v!=pa)dfs(v,u,d+1,c);
}

int s,t,mx,par[maxn],d[maxn],len;
void dfs(int u,int pa,int d){
	par[u]=pa;
	if(d>mx)mx=d,t=u;
	for(auto v:e[u])if(v!=pa)dfs(v,u,d+1);
}
void find(){
	s=1,t=1,mx=0,dfs(1,0,0);
	s=t,mx=0,dfs(s,0,0);
	for(int u=t;u;u=par[u]) d[++len]=u;
}

signed main()
{
	n=read();
	initC(305);
	For(i,0,300){
		C[i][0]=1;
		For(j,1,i)C[i][j]=C[i-1][j]+C[i-1][j-1];
	}
	For(i,2,n){
		int u=read(),v=read();
		e[u].pb(v);
		::u[(i-1)*2-1]=u,::v[(i-1)*2-1]=v;
		e[v].pb(u);
		::u[(i-1)*2]=v,::v[(i-1)*2]=u;
	}
	m=(n-1)*2;
	For(i,1,m){
		id[u[i]][v[i]]=i;
		dfs(v[i],u[i],0,cnt[i]);
	}
	find();
	if(len%2==0){
		int u=d[len/2],v=d[len/2+1];
		int t=cnt[id[v][u]][len/2-1];
		f[len-2][id[u][v]][t]=fac[t];
		t=cnt[id[u][v]][len/2-1];
		f[len-2][id[v][u]][t]=fac[t];
	}else{
		int u=d[len/2+1];
	//	cout<<"u: "<<u<<"\n";
		for(auto v:e[u]){
			int t=cnt[id[v][u]][len/2];
		//	cout<<"u,v "<<v<<" "<<len-1<<" "<<id[u][v]<<" "<<t<<" "<<fac[t].x<<"\n";
			g[len-2][id[u][v]][t]=fac[t];
		}
	}
	Rep(i,len-1,1) For(j,1,m) For(k,1,n) {
		int u=::u[j],v=::v[j];
		if(f[i][j][k].x){
		//	cout<<"f: "<<i<<" "<<j<<" "<<k<<" "<<f[i][j][k].x<<"\n";
			// point, from u-->v, now is v
			int t=cnt[id[u][v]][i/2];
			For(x,1,t) g[i-1][id[v][u]][x]+=f[i][j][k]*fac[t]*C[k-1+t-x][t-x];
			for(auto w:e[v]){
				if(u==w) continue;
				if(!cnt[id[v][w]][i/2-1]) continue;
				// k before tu
				int tu=cnt[id[v][u]][i/2-1];
				int tt=cnt[id[u][v]][i/2]-cnt[id[v][w]][i/2-1];
				g[i-1][id[v][w]][k+tu+tt]+=f[i][j][k]*fac[tu]*fac[tt]*C[k+tu+tt][tt];
			}
		}
		if(g[i][j][k].x){
		//	cout<<"g: "<<i<<" "<<j<<" "<<k<<" "<<g[i][j][k].x<<"\n";
			// edge
			int t=cnt[id[v][u]][i/2];
			f[i-1][id[u][v]][k+t]+=fac[t]*g[i][j][k];
			t=cnt[id[u][v]][i/2];
			For(x,1,t) f[i-1][id[v][u]][x]+=g[i][j][k]*fac[t]*C[k-1+t-x][t-x];
		}
	}
	modint res=0;
	For(j,1,m) For(k,1,n) res+=f[0][j][k];
	cout<<res.x;
	return 0;
}
/*

*/

詳細信息

Test #1:

score: 100
Accepted
time: 19ms
memory: 495584kb

input:

3
1 2
3 2

output:

4

result:

ok 1 number(s): "4"

Test #2:

score: 0
Accepted
time: 23ms
memory: 496264kb

input:

5
4 1
4 5
1 2
1 3

output:

28

result:

ok 1 number(s): "28"

Test #3:

score: 0
Accepted
time: 31ms
memory: 495660kb

input:

7
5 7
2 5
2 1
1 6
3 6
4 1

output:

116

result:

ok 1 number(s): "116"

Test #4:

score: 0
Accepted
time: 28ms
memory: 494780kb

input:

100
89 60
66 37
59 74
63 49
69 37
9 44
94 22
70 30
79 14
25 33
23 4
78 43
63 30
95 7
6 59
56 31
21 56
58 43
95 28
81 19
63 40
58 87
81 38
100 55
78 23
37 78
86 70
33 11
52 17
42 19
19 13
70 100
97 79
66 67
66 27
82 55
15 27
68 33
97 26
46 20
70 93
1 10
69 79
81 45
58 95
24 63
79 51
85 11
12 43
41 64...

output:

748786623

result:

ok 1 number(s): "748786623"

Test #5:

score: -100
Wrong Answer
time: 15ms
memory: 495976kb

input:

300
109 123
221 101
229 22
114 101
110 258
50 79
26 1
238 47
140 271
77 213
140 125
19 179
111 96
194 114
57 101
1 251
19 13
92 238
114 116
193 140
153 238
1 173
252 220
1 22
124 197
196 214
196 224
1 138
201 90
184 56
266 154
71 184
46 15
256 27
1 69
1 32
22 182
237 196
111 1
279 91
139 196
114 80
...

output:

434631172

result:

wrong answer 1st numbers differ - expected: '47013557', found: '434631172'