网站开发什么开发语言好,网站系统建设开票要开什么,北京网站建设找华网天下,长沙seo代理WCB某天买了非常多的糖果并把它们分成N份#xff0c;依次分别有1#xff0c;2#xff0c;3…,N个糖果。他想拿出其中的3份分给他的室友#xff0c; 为了不让室友们闹意见#xff0c;必须让这三份的糖果总数恰好能被三人均分。请问他一共有多少种不同的组合方案数#xff… WCB某天买了非常多的糖果并把它们分成N份依次分别有123…,N个糖果。他想拿出其中的3份分给他的室友 为了不让室友们闹意见必须让这三份的糖果总数恰好能被三人均分。请问他一共有多少种不同的组合方案数 输入 有多组输入数据每组输入非负整数N(3≤N≤106),如果N0表示输入结束这个样例不需要处理。 输出 每组数据输出一个整数独占一行表示共有多少种方案由于可能会很大最后结果对1097取模。 样例输入 3
4
5
0 样例输出 1
2
4 解题思路这题题目也说了就是一道排列组合题。 有哪些组合可以让三份的糖果总数恰好能被三人均分
1三份糖果 模3余数均为1 的 糖果
2三份糖果 模3余数均为2 的 糖果
3三份糖果 模3余数均为0 的 糖果
4一份糖果 模3余数为1 的 糖果 一份糖果 模3余数均为2 的 糖果 一份糖果 模3余数均为0 的 糖果。
最后对这4种情况的组合数求和就行了。 注意取模 和 爆int
AC代码
#include stdio.hconst int Mod 1e97;
int compute(__int64 s){ // 组合数公式 C(n,3)return (s*(s-1)*(s-2)/6) % Mod;
}int main()
{int n,N;__int64 x,y,z;__int64 ans1,ans2,ans3,ans;while (scanf(%d,N) ! EOF N ! 0){x N/3; // x:3的倍数的 个数y z x;n N%3;if (n 1) y 1; // y:模3余1的数 的个数else if (n 2) y 1, z 1; // z:模3余2的数 的个数ans1 compute(x);ans2 compute(y);ans3 compute(z);ans (ans1ans2ans3x*y*z) % Mod;printf(%I64d\n,ans);}return 0;
}
