NC247066. 233的树
描述
输入描述
第一行一个正整数
输出描述
输出一行一个数代表答案
示例1
输入:
3
输出:
9
C++(g++ 7.5.0) 解法, 执行用时: 49ms, 内存消耗: 12100K, 提交时间: 2022-12-09 21:16:45
//233的树 #include<iostream> using namespace std; const int mod = 1e9+7 , N = 1e6+10; int C[N] , D[N] , inv[N]; int main() { int n; cin >> n; if(n < 3) { cout << n << '\n'; return 0; } C[0] = D[0] = inv[0] = inv[1] = 1; for(int i = 2 ; i <= n ; ++i) inv[i] = (mod - 1ll * inv[mod % i] * (mod / i) % mod) % mod; for(int i = 1 ; i <= n ; ++i) C[i] = 1ll * C[i-1] * (n - i + 1) % mod * inv[i] % mod; for(int i = 1 ; i <= n - 3 ; ++i) D[i] = 1ll * D[i-1] * (n - 3 - i + 1) % mod * inv[i] % mod; int Ans = 0; for(int i = 2 ; i <= n ; ++i) { Ans = (Ans + 1ll * C[i] * D[n-i-1] % mod * (n - i + 2) % mod) % mod; } cout << Ans << '\n'; return 0; }
C++(clang++ 11.0.1) 解法, 执行用时: 267ms, 内存消耗: 8312K, 提交时间: 2022-12-09 22:08:12
#include<bits/stdc++.h> #define ll long long using namespace std; const int maxn=1e6+10; const int mod=1e9+7; ll inv(ll x){ ll y=mod-2,ans=1; while(y){ if(y&1) ans=ans*x%mod; x=x*x%mod; y>>=1; } return ans; } ll jc[maxn],n,ans; ll C(ll n,ll m){ return jc[n]*inv(jc[m]*jc[n-m]%mod)%mod; } int main(){ jc[0]=1;for(int i=1;i<maxn;i++) jc[i]=jc[i-1]*i%mod; cin>>n; if(n<=2){ cout<<n; return 0; } for(int i=2;i<=n-1;i++){ ans+=(n-i+2)*C(n,i)%mod*C(n-3,n-i-1)%mod; } printf("%lld",ans%mod); }