http://acm.hust.edu.cn/problem/show/1698
题目就是要把一个数n分成4段,其中中间两段一定要是奇数。
问有多少种情况。
分类,
奇数 + 奇数 + 奇数 + 奇数
奇数 + 奇数 + 奇数 + 偶数
偶数 + 奇数 + 奇数 + 奇数
偶数 + 奇数 + 奇数 + 偶数
注意看看能否拆成这样的形式,比如x是奇数的话,最后一种就没可能拆成了。
然后奇数表达成 2 * a – 1这个样子,就能列出方程。
然后就是类似于解a1 + a2 + a3 + a4 = x的问题了。
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;#include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <bitset>
LL C(LL n, LL m) {
if (n < m) return ; //防止sb地在循环
if (n == m) return ; //C(0,0)也是1的
LL ans = ;
LL mx = max(n - m, m); //这个也是必要的。能约就约最大
LL mi = n - mx;
for (int i = ; i <= mi; ++i) {
ans = ans * (mx + i) / i;
}
return ans;
}void work() {
int n;
scanf("%d", &n);
LL ans = ;
if ((n + ) % == ) ans += C((n + ) / - , );
if ((n + ) % == ) ans += C((n + ) / - , ) * ;
if ((n + ) % == ) ans += C((n + ) / - , );
static int f = ;
printf("Case #%d: %lld\n", ++f, ans);
}int main() {
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
int t;
scanf("%d", &t);
while (t--) work();
return ;
}