2010-1073

从 Trac 迁移的文章

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

原文章内容如下：

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

题目大意：构造n进制下长度为l，且包含偶数个1的数串，问这样的数串有多少个，输出 (ans*2)mod 10[[BR]][[BR]]
方法：[[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]][[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]]
      据此，题目转化为快速求a^b^ mod m，采用快速幂取模求a的b次方余m算法即可解决该问题。
代码：[[BR]]
    {{{
#!cpp
#include<cstdio>
#define MODNUM 10
long exp_mod( long a, long b )
{                       
    long m = 1;
    while( b )
    {
        if( b & 1 )     m = ( ( a % MODNUM ) * ( m % MODNUM ) ) % MODNUM;
        b >>= 1;
        a = ( ( a % MODNUM ) * ( a % MODNUM ) ) % MODNUM;
    }
    return m;
}
int main()
{
    long n, m, ans;
    while( scanf("%ld%ld", &n, &m) != EOF )
    {
        ans = exp_mod(n,m)%10 + exp_mod(n-2,m)%10;
        printf("%ld\n", ans%10 );
    }
    return 0; 
}
}}}
[[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)*x⁰*y^m + C(m,1)*x¹*y^(m-1) + ... + C(m,m)*x^m*y⁰

令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

据此，题目转化为快速求a^b mod m，采用快速幂取模求a的b次方余m算法即可解决该问题。

代码：

{{{

#!cpp

#include

#define MODNUM 10

long exp_mod( long a, long b )

{

long m = 1;

while( b )

{

if( b & 1 ) m = ( ( a % MODNUM ) * ( m % MODNUM ) ) % MODNUM;

b >>= 1;

a = ( ( a % MODNUM ) * ( a % MODNUM ) ) % MODNUM;

}

return m;

}

int main()

{

long n, m, ans;

while( scanf("%ld%ld", &n, &m) != EOF )

{

ans = exp_mod(n,m)%10 + exp_mod(n-2,m)%10;

printf("%ld\n", ans%10 );

}

return 0;

}

}}}

---