QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#267425 | #7677. Easy Diameter Problem | Crysfly | WA | 31ms | 496264kb | C++17 | 4.3kb | 2023-11-27 11:25:02 | 2023-11-27 11:25:02 |
Judging History
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;
}
/*
*/
Details
Tip: Click on the bar to expand more detailed information
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'