学步园

做ACM题时，经常遇到取模操作，而取模操作是算术操作中最慢的（在当前的计算机硬件中基本都是这样）。

1 对2的幂取模（2^k），实际等同于和(2^k - 1)进行“位与”操作

例如对8取模，因为计算机内部是二进制表示，所以可以对二进制位进行位与操作。

n % 8 == ( n & 7 )  // 因为C语言取模操作会返回负数，所以当n是负数时，它们是同模关系。

2 经常有一些递推式，是加和后求模关系，这时可以利用有限范围的特性，将求模转换为加减法

// 例如dp[0] = dp[1] = 1
dp[i] = ( dp[i-1] + dp[i-2] ) % MOD;
// 注意dp数组都是正数，并且两个元素加和在[0,2*MOD) 范围。
// 公式可以改写为
int  madd[2] = { 0, MOD }, r;
r = dp[i-1] + dp[i-2] - MOD;
dp[i] = r + madd[((unsigned)(r))>>31];

3 有些题目结果是高精度（即用语言提供的类型已经无法表示，必须用数组模拟），通常的做法是用一个32bit的int表示10^9进制的数。

这样做确实很直观，也符合我们十进制的直觉，但是每次进位都不可避免要进行取模和除法操作，非常慢。

可以考虑用2^30进制，这样进位时用的就是“移位”和“位与”运算，可以很大提高运行速度。

当然最后也会产生一个问题，就是2^30进制表示法无法直接打印，这时还需要将2^30进制转换为10^9进制再输出。由于往往只打印一次，所以基本不费什么时间。

// 例如2^30加法
#define  LEN  5  // 每个高精度用几个int
#define  P2  30  // 2^P2 进制
#define  M2  ( (1<<P2) - 1 )  // 取模所用mask
// 高精度c = a + b
inline
void  add( int*  a, int*  b, int*  c ) {
        c[0] = a[0] + b[0];
        for( int i = 1; i < LEN; ++i ) {
                c[i] = a[i] + b[i] + ( c[i-1] >> P2 );
                c[i-1] &= M2;
        }
}

下面是2^30转换为10^9进制并打印的代码：

#define  M10  1000000000
void  convert_print( int* d2 ) {
        int  d10[LEN] = {0};

        int  i = LEN - 1, j, k = 0;
        LL  r;
        while( i >= 0 ) {
                while( d2[i] == 0 ) --i;
                if( i < 0 ) break;
                for( r = 0, j = i; j >= 0; --j ) {
                        r = ( ( r << P2 ) + d2[j] );
                        d2[j] = r / M10;
                        r %= M10;
                }
                d10[k++] = r;
        }

        char  buf[LEN*9+1];
        int  pos = 0;
        for( i = LEN - 1; i > 0; --i ) if( d10[i] ) break;
        pos += sprintf( buf + pos, "%d", d10[i] );
        for( --i; i >= 0; --i ) pos += sprintf( buf + pos, "%09d", d10[i] );
        buf[pos] = 0;
        puts( buf );
}