2010-1005

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

Contest 2 by CC98 1005 Strange Coding System解题报告[[BR]]
题目大意：构造n进制下长度为l，且包含偶数个1的数串，问这样的数串有多少个，输出 (ans*2)mod 10[[BR]]
方法：不难想到n进制下长为l的数串个数为 ans=C(n,0)*(n-1)^(l)+C(n,2)*(n-1)^(l-2)+C(n,4)*(n-1)^(l-4)+...[[BR]]
     考虑二项式定理：(x+y)^m=C(m,0)*x^0*y^m + C(m,1)*x^1*y^(m-1) + ... + C(m,m)*x^m*y^0 [[BR]]
     令x=n-1, y=1, m=l, n^l=((n-1)+1)^l=C(n,0)*(n-1)^(l)+C(n,1)*(n-1)^(l-1)+C(n,2)*(n-1)^(l-2)+... -----式1[[BR]]
     令x=n-1, y=-1, m=l, (n-2)^l=((n-1)-1)^l=C(n,0)*(n-1)^(l)-C(n,1)*(n-1)^(l-1)+C(n,2)*(n-1)^(l-2)+... -----式2[[BR]]
     式1＋式2得 2*ans=n^l+(n-2)^l[[BR]]
     输出结果即为 求 (n^l+(n-2)^l)%10= n^l%10 + (n-2)^l%10[[BR]]


[[BR]]______________________________________________________________________________________________________________________[[BR]]

    

Contest 2 by CC98 1005 Strange Coding System解题报告

题目大意：构造n进制下长度为l，且包含偶数个1的数串，问这样的数串有多少个，输出 (ans*2)mod 10

方法：不难想到n进制下长为l的数串个数为 ans=C(n,0)*(n-1)^{(l)+C(n,2)*(n-1)}(l-2)+C(n,4)*(n-1)^(l-4)+...

考虑二项式定理：(x+y)^m=C(m,0)*x0*y^{m + C(m,1)*x}1*y^{(m-1) + ... + C(m,m)*x}m*y^0

令x=n-1, y=1, m=l, n^l=((n-1)+1)l=C(n,0)*(n-1)^{(l)+C(n,1)*(n-1)}(l-1)+C(n,2)*(n-1)^(l-2)+...

---

式1

令x=n-1, y=-1, m=l, (n-2)^l=((n-1)-1)l=C(n,0)*(n-1)^{(l)-C(n,1)*(n-1)}(l-1)+C(n,2)*(n-1)^(l-2)+...

---

式2

式1＋式2得 2*ans=n^l+(n-2)l

输出结果即为 求 (n^l+(n-2)l)%10= n^{l%10 + (n-2)}l%10

______________________________________________________________________________________________________________________