http://acm.hust.edu.cn/vjudge/contest/view.action?cid=30506#problem/U

fib数列对2^m取模的循环节为3*（2^(m-1)）

#include<map>
#include<set>
#include<list>
#include<cmath>
#include<ctime>
#include<deque>
#include<stack>
#include<bitset>
#include<cstdio>
#include<vector>
#include<cstdlib>
#include<cstring>
#include<iomanip>
#include<numeric>
#include<sstream>
#include<utility>
#include<iostream>
#include<algorithm>
#include<functional>

using namespace std ;
const int maxn = 1000005 ;

long long f[ 25 ][ maxn ] ;

void Union()
{
	for( int i = 1 ; i <= 20 ; ++i )
	{
		f[ i ][ 0 ] = 0 ;
		f[ i ][ 1 ] = 1 ;
		long long temp = 1 << i ;
		for( long long j = 2 ; j < 3 * ( 1 << ( i - 1 ) ) ; ++j )
		{
			f[ i ][ j ] = ( f[ i ][ j - 1 ] % temp + f[ i ][ j - 2 ] % temp ) % temp ;
		}
	}
} 

int main()
{
	Union() ;
	int m , n ;
	while( scanf( "%d%d" , &n , &m ) != EOF )
	{
		if( !m )
			printf( "0\n" ) ;
		else
			printf( "%lld\n" , f[ m ][ n % ( 3 * ( 1 << ( m - 1 ) ) ) ] ) ;
	}
    return 0;
}

优质内容筛选与推荐>>
1、mix
2、python之路_day6
3、redis 一直写aof 文件、rabbitmq 问题，消费者报错后，服务会当掉 ，不会继续消费？？！！为什么！！
4、慕课网-Java入门第一季-7-5 Java 中带参无返回值方法的使用
5、打乱数组顺序

赞赏

长按二维码向我转账

受苹果公司新规定影响，微信 iOS 版的赞赏功能被关闭，可通过二维码转账支持公众号。

阅读

已发送

发送中