没打，简单补档
C.Edgy Trees
容斥，把黑边断掉数联通块，每个联通块贡献$siz^k$
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 const int N=200005,mod=1e9+7; 6 int n,k,t1,t2,t3,tot,aset[N],siz[N]; 7 int Finda(int x) 8 { 9 return x==aset[x]?x:aset[x]=Finda(aset[x]); 10 } 11 int Qpow(int x,int k) 12 { 13 if(k<=1) return k?x:1; 14 int tmp=Qpow(x,k>>1); 15 return 1ll*tmp*tmp%mod*((k&1)?x:1)%mod; 16 } 17 int main() 18 { 19 scanf("%d%d",&n,&k); 20 for(int i=1;i<=n;i++) aset[i]=i,siz[i]=1; 21 for(int i=1;i<n;i++) 22 { 23 scanf("%d%d%d",&t1,&t2,&t3); 24 if(!t3) 25 { 26 int nx=Finda(t1),ny=Finda(t2); 27 aset[nx]=ny,siz[ny]+=siz[nx]; 28 } 29 } 30 for(int i=1;i<=n;i++) 31 if(aset[i]==i) (tot+=Qpow(siz[i],k))%=mod; 32 printf("%d",(Qpow(n,k)-tot+mod)%mod); 33 return 0; 34 }
D.Steps to One
我写的辣鸡的$O(nlog nsqrt n)$(其实并不能跑满)，太菜了
设dp[i]表示当前为i的期望步数，暴力DP即枚举1->m从gcd转移，改为枚举gcd(指所有因子)，然后莫比乌斯函数统计1->n中和某个数互质的数的个数
1 #include<cstdio> 2 #include<vector> 3 #include<cstring> 4 #include<algorithm> 5 #define vint vector<int> 6 #define vit vector<int>::iterator 7 using namespace std; 8 const int N=100005,mod=1e9+7; 9 int dp[N],pri[N],npr[N],mul[N]; 10 int n,t,in,cnt,ans; vint fac[N]; 11 void Add(int &x,int y) 12 { 13 x+=y; 14 if(x>=mod) x-=mod; 15 } 16 int Qpow(int x,int k) 17 { 18 if(k<=1) return k?x:1; 19 int tmp=Qpow(x,k>>1); 20 return 1ll*tmp*tmp%mod*((k&1)?x:1)%mod; 21 } 22 void Pre() 23 { 24 in=Qpow(n,mod-2); 25 for(int i=1;i<=n;i++) 26 for(int j=2*i;j<=n;j+=i) 27 fac[j].push_back(i); 28 npr[1]=true,mul[1]=1; 29 for(int i=2;i<=n;i++) 30 { 31 if(!npr[i]) pri[++cnt]=i,mul[i]=-1; 32 for(int j=1;j<=cnt&&(t=i*pri[j])<=n;j++) 33 { 34 npr[t]=true; 35 if(i%pri[j]==0) break; 36 else mul[t]=-mul[i]; 37 } 38 } 39 } 40 int Count(int x,int y)//Count:for i=1 to n,gcd(i,x)==y 41 { 42 int N=n/y,X=x/y,ret=0; 43 for(int i=1;i*i<=X;i++) 44 if(X%i==0) 45 { 46 ret+=N/i*mul[i]; 47 if(i*i!=X) ret+=N/(X/i)*mul[X/i]; 48 } 49 return ret; 50 } 51 int main() 52 { 53 scanf("%d",&n),Pre(),dp[1]=1; 54 for(int i=2;i<=n;i++) 55 { 56 int tmp=n/i; 57 for(vit it=fac[i].begin();it!=fac[i].end();it++) 58 t=*it,Add(dp[i],1ll*dp[t]*Count(i,t)%mod*in%mod); 59 dp[i]=1ll*(dp[i]+1)*Qpow(n-tmp,mod-2)%mod*n%mod; 60 } 61 for(int i=1;i<=n;i++) Add(ans,dp[i]); 62 printf("%lld",1ll*ans*in%mod); 63 return 0; 64 }
呃，发现题解也不怎么快，他是用2^质因子个数容斥算的，$2^6*6$怕不是跟非常跑不满的根号差不多
E.Maximize Mex
显然答案单调不升，把每种潜力值和每个club看做左右部点，倒着加边，每次在上次的基础上继续二分图匹配到没有增广路为止
注意潜力值是从零开始的，还有每次跑完记得更新dfn
1 #include<cstdio> 2 #include<vector> 3 #include<cstring> 4 #include<algorithm> 5 #define vint vector<int> 6 #define vit vector<int>::iterator 7 using namespace std; 8 const int N=5005; 9 int n,m,q,t1,t2,dfn; 10 int val[N],bel[N],lft[N]; 11 int del[N],vis[N],mth[N],ans[N]; vint ve[N]; 12 bool DFS(int nde) 13 { 14 int t; 15 for(vit it=ve[nde].begin();it!=ve[nde].end();it++) 16 if(vis[t=*it]!=dfn) 17 { 18 vis[t]=dfn; 19 if(mth[t]==-1||DFS(mth[t])) 20 {mth[t]=nde; return true;} 21 } 22 return false; 23 } 24 int main() 25 { 26 scanf("%d%d",&n,&m); 27 for(int i=1;i<=n;i++) scanf("%d",&val[i]); 28 for(int i=1;i<=n;i++) scanf("%d",&bel[i]); 29 for(int i=1;i<=m;i++) mth[i]=-1; dfn=1; 30 scanf("%d",&q); 31 for(int i=1;i<=q;i++) 32 scanf("%d",&lft[i]),del[lft[i]]=true; 33 for(int i=1;i<=n;i++) 34 if(!del[i]) ve[val[i]].push_back(bel[i]); 35 for(int i=q,mex=-1;i;i--) 36 { 37 while(DFS(mex+1)) mex++,dfn++; ans[i]=mex+1,dfn++; 38 ve[val[lft[i]]].push_back(bel[lft[i]]); 39 } 40 for(int i=1;i<=q;i++) printf("%d ",ans[i]); 41 return 0; 42 }
F.Dish Shopping
