题目链接
https://atcoder.jp/contests/abc178/tasks/abc178_d
题意
将一个整数n划分成若干个组，每个组的数必须大于等于3，问有多少种划分方法？
思路
考虑最多划分为k组， 很明显(k == n div 3)，我们只要对长度为(left[ 1,k ight])的组进行计算，最后把每组的答案数累加即可。由于每组最小为3，所以k组最低需要(k cdot 3)，将剩下 (n-kcdot3)个数放进k个组里,组可以为空，这就是个经典的组合数学题，答案为$$C_{n-3k+k-1}^{k-1} = C_{n-2k-1}^{k-1} $$
AC代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 50;
const int mod = 1e9 + 7;
ll fac[maxn];
ll qpow(ll a,ll b){
ll ans = 1;a %= mod;
for(ll i = b;i;i >>= 1,a = a * a % mod)
if(i & 1) ans = ans * a % mod;
return ans % mod;
}
ll C(ll n,ll m){
if(m > n || m < 0) return 0;
ll s1 = fac[n],s2 = fac[n - m] * fac[m] %mod;
return s1 * qpow(s2,mod - 2) % mod;
}
void init(){
fac[0] = 1;
for(int i = 1;i < maxn;i++)
fac[i] = fac[i-1] * i % mod;
}
int main()
{
std::ios::sync_with_stdio(false);
ll n;
init();
cin >> n;
ll k = n / 3;
ll cnt = n % 3;
ll ans = 0;
while(k >= 1){
ans += C(cnt + k - 1, k - 1);
ans %= mod;
cnt += 3;
k--;
}
cout << ans << endl;
return 0;
}