首页 > 代码库 > Yue Fei's Battle(组合计数递推)
Yue Fei's Battle(组合计数递推)
//求一个直径为 k 的树有多少种形态，每个点的度不超过 3
// 非常完美的分析，学到了，就是要细细推，并且写的时候要细心
还有除法取模需要用逆元
#include <iostream>#include <stdio.h>#include <string.h>#include <math.h>#include <stdlib.h>using namespace std;#define MOD 1000000007#define LL long long#define MX 100005LL dp[MX];LL sum[MX];LL inv2;LL inv6;LL quick(LL a,LL b){ LL ret = 1; while (b) { if (b&1) ret = ret*a%MOD; a = a*a%MOD; b/=2; } return ret;}void Init(){ inv2 = quick(2,MOD-2); inv6 = quick(6,MOD-2); dp[0]=1,sum[0]=1; dp[1]=1,sum[1]=2; for (int i=2;i<MX;i++) { dp[i] = dp[i-1]*(dp[i-1]-1)%MOD*inv2%MOD; dp[i] = (dp[i] + dp[i-1])%MOD; dp[i] = (dp[i] + dp[i-1]*sum[i-2]%MOD)%MOD; sum[i]=(sum[i-1]+dp[i])%MOD; }}int main(){ int n; Init(); while (scanf("%d",&n)&&n) { if (n%2==0) { int i = n/2; int ans = (dp[i]+dp[i]*(dp[i]-1)/2)%MOD; printf("%d\n",ans); } else { int i = n/2; int ans = (((dp[i]*(dp[i]+1))%MOD*inv2%MOD)*sum[i-1])%MOD; ans = (ans + dp[i])%MOD; ans = (ans + (dp[i]*(dp[i]-1)%MOD)%MOD)%MOD; ans = (ans + dp[i]*(dp[i]-1)%MOD*(dp[i]-2)%MOD*inv6%MOD )%MOD; printf("%d\n",ans); } } return 0;}
Yue Fei's Battle(组合计数递推)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。