^^^转载请注明出处,谢谢合作O(∩_∩)O~
功夫不负有心人,终于把这道题推出来了:
即用排列组合加二项式定理,0-n/2个 A或C,剩下的填B、D,i和j都是偶数C(n,i)*C(n-i,j)*2^(n-i-j,);
先计算当i=0时,C(n-i,j)*2^(n-i-j,)的值,得C(n,0)*2^n+C(n,2)*(2^n-2)+……+C(n,n-2)*2^2+C(n,n)*2^0;
由于(2+1)^n和(2-1)^n有二项式展开定理分别展开再相加,再除以2,即得C(n,j)*2^(n-j,)的值为(3^n+1)/2;
然后再求i=2,4……时C(n-i,j)*2^(n-i-j,)的值,最后得到表达式:C(n,0)*(3^n+1)/2+C(n,2)*(3^(n-2)+1)/2+……+C(n,n-2)/(3^2)+C(n,n)/(3^0);
先提取1/2,再展开,又由二项式定理得C(n,0)+C(n,2)+……+C(n,n-2)+C(n,n)=C(n,1)+C(n,3)+……+C(n,n-3)+C(n,n-1)=2^n-1;
又由(3+1)^n+(3-1)^n化简展开式得最终结果4^(n-1)+2^(n-1),然后再对100求余即可。
此题的结果是从n=2之后,一个以20个结果为1次的循环,从1到60测试一下数据就知道了,如图:(还有当1时等于2),
AC代码如下,注意输出格式:
// Note:Your choice is C++ IDE #include <iostream> using namespace std; int main() { int t; int a[3]={0,2,6}; int b[20]={20,72,72,56,60,12,92,56,0,52,12,56,40,92,32,56,80,32,52,56}; while(scanf("%d",&t)!=EOF) { if(t==0)break; __int64 n; int N,k; N=t; while(t--) { scanf("%I64d",&n); if(n<3) k=a[n]; else { k=b[(n-3)%20]; } printf("Case %d: %d\n",N-t,k); } printf("\n"); } return 0; }
OK,结束!