Submission #1829385
Source Code Expand
#include <iostream> #include <cstdio> #include <cstring> #define NDEBUG #include <cassert> #include <cctype> using namespace std; typedef long long lint; #define cout cerr #define ni (next_num<int>()) template<class T>inline T next_num(){ T i=0;char c; while(!isdigit(c=getchar())&&c!='-'); bool flag=c=='-'; flag?c=getchar():0; while(i=i*10-'0'+c,isdigit(c=getchar())); return flag?-i:i; } template<class T1,class T2>inline void apmax(T1 &a,const T2 &b){if(a<b)a=b;} template<class T1,class T2>inline void apmin(T1 &a,const T2 &b){if(b<a)a=b;} const int O=1000000007; int gcd(int a,int b){ return b?gcd(b,a%b):a; } inline int fpow(int x,int n){ int a=1; for(;n;n>>=1,x=(lint)x*x%O){ if(n&1){ a=(lint)a*x%O; } } return a; } inline int inv(int x){ return fpow(x,O-2); } const int N=210; int c[N][N]; int k,f[N],g[N],pw[N],ans=1; namespace G{ const int N=55,E=110*2; int to[E],bro[E],head[N],e=0; int dfn[N],tim=0; int efa[E],esize[E],estat[E]; int estk[N],ss=0; inline void init(){ memset(head,-1,sizeof(head)); memset(dfn,0,sizeof(dfn)); memset(efa,0,sizeof(efa)); memset(estat,0,sizeof(estat)); } inline void ae(int u,int v){ to[e]=v,bro[e]=head[u],esize[e]=1,head[u]=e++; } inline void add(int u,int v){ ae(u,v),ae(v,u); } int root(int x){ return efa[x]?efa[x]=root(efa[x]):x; } void dfs(int x,int fa){ dfn[x]=++tim; for(int i=head[x],v;~i;i=bro[i]){ if((v=to[i])!=fa){ if(dfn[v]==0){ estk[ss++]=i; ans=(lint)ans*k%O; dfs(v,x); if(stk[ss-1]==i){ ss--; } }else if(dfn[v]<dfn[x]){ int last=i,e,stat=1; do{ e=estk[--ss]; if(estat[e]){ stat=2; ans=(lint)ans*inv((estat[e]==1?f:g)[esize[e]])%O; }else{ ans=(lint)ans*inv(k)%O; } efa[last]=e,esize[e]+=esize[last],last=e; }while(dfn[v]<dfn[to[e^1]]); estat[e]=stat; estk[ss++]=e; ans=(lint)ans*(stat==1?f:g)[esize[e]]%O; } } } } } inline void gmath(int n,int k){ pw[0]=1; for(int i=1;i<=n;i++){ pw[i]=(lint)pw[i-1]*k%O; } for(int i=1;i<=n;i++){ lint tmp=0; for(int j=0;j<i;j++){ tmp+=pw[gcd(i,j)]; } f[i]=tmp%O*inv(i)%O; } memset(c,0,sizeof(c)); for(int i=0,ti=n+k;i<=ti;i++){ c[i][0]=1; for(int j=1;j<=i;j++){ c[i][j]=(c[i-1][j-1]+c[i-1][j])%O; } } for(int i=1;i<=n;i++){ g[i]=c[i+k-1][k-1]; } } int main(){ int n=ni,m=ni; G::init(); gmath(m,k=ni); for(int i=1;i<=m;G::add(ni,ni),i++); for(int i=1;i<=n;i++){ if(G::dfn[i]==0){ G::dfs(i,0); } } printf("%d\n",ans); return 0; }
Submission Info
Submission Time | |
---|---|
Task | F - Painting Graphs with AtCoDeer |
User | sshockwave |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 2680 Byte |
Status | CE |
Compile Error
./Main.cpp: In function ‘void G::dfs(int, int)’: ./Main.cpp:69:9: error: ‘stk’ was not declared in this scope if(stk[ss-1]==i){ ^