牛客96场B题n层满k叉树

#include<bits/stdc++.h>
using namespace std ;
const int N =2e6+50;
long long  a[N];
long long  n,k;
long long   s [N];
const int mod =1e9+7;
/*

考虑每条边的贡献，对于同一层的边的贡献肯定是相同的，
假设共有 n 层边，总的节点数为 all=1+k+k2+⋯+kn，
对于第 i 层的每一条边，
下面有 now=1+k+⋯+kn−i 个点，上面共有 all−now 个点，
则该层的贡献即为 ki×now×(all−now)



*/
int main ()
{
  cin >>n >>k;
  n-- ;
  a[0]=1,s[0]=1;	
	for(int i =1;i<=n;i++)
	{
		
		a[i]=1ll*a[i-1]*k%mod ;
		s[i]=(1ll*a[i]+s[i-1])%mod ;
		
		// 计算 总共的 节点数目；
		 
		
	}
	int res=0;
	for(int  i=1;i<=n;i++)
	{
		
		res=(res+(s[n]-s[n-i]+mod)%mod*s[n-i]%mod*a[i]%mod)%mod ;
		
	}
	
	
	cout <<res ;
	
	return  0;
	
    
  
	
}

考虑每条边的贡献，对于同一层的边的贡献肯定是相同的，假设共有 n 层边，总的节点数为 all=1+k+k2+⋯+kn，对于第 i 层的每一条边，下面有 now=1+k+⋯+kn−i 个点，上面共有 all−now 个点，则该层的贡献即为 ki×now×(all−now)

也就是all 节点 圆圈的个数

上面下面ki 就是所有的 长度