hihoCoder#1143 : 骨牌覆盖问题·一

向右看齐 2022-08-21 03:26 140阅读 0赞

快速幂需要注意一个地方，就是别超了数字的范围，及时longlong也很容易爆炸，及时取余才是王道

http://hihocoder.com/problemset/problem/1143

#include<iostream>
    using namespace std;
    long long di[4] ;
    void solve(long long a[4], long long b[4], long long *cc)
    {
    	long long aa[4] = {a[0],a[1],a[2],a[3]};
    	long long bb[4] = { b[0], b[1], b[2], b[3] };
    	cc[0] = (aa[0] * bb[0] + aa[1] * bb[2]) % 19999997;//重点啊~~~~
    	cc[1] = (aa[0] * bb[1] + aa[1] * bb[3]) % 19999997;
    	cc[2] = (aa[2] * bb[0] + aa[3] * bb[2]) % 19999997;
    	cc[3] = (aa[2] * bb[1] + aa[3] * bb[3]) % 19999997;
    	int i = 0;
    }
    void ji(long long n, long long *answer)
    {
    	while (n)
    	{
    		if (n & 1)
    		{
    			solve(answer, di, answer);
    		}
    		solve(di, di, di);
    		n = n >> 1;
    	}
    }
    int main()
    {
    	long long n;
    
    	while (cin >> n){
    		di[0] = 0;
    		di[1] = 1;
    		di[2] = 1;
    		di[3] = 1;
    		long long answer[4] = { 1, 0, 0, 1 };
    		ji(n, answer);
    		cout << answer[3]  << endl;
    	}
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，140人围观）

还没有评论，来说两句吧...

相关阅读

相关 hihoCoder 1081 : 最短路径·一

\1081 : 最短路径·一时间限制: 10000ms 单点时限: 1000ms 内存限制: 256MB <table></table> 描述万圣节的早

分手后的思念是犯贱/ 2024年02月17日 21:36/ 0 赞/ 76 阅读

相关多米诺骨牌问题

> 现有n块”多米诺骨牌”s1,s2,s3,…sn水平放成一排,每次骨牌si包含左右两个部分,每个部分赋予一个非负整数值,如下图所示为包含6块骨牌的序列.骨牌可做180度旋转,

超、凢脫俗/ 2022年12月24日 09:57/ 0 赞/ 165 阅读

相关 hihoCoder#1143 : 骨牌覆盖问题·一

快速幂需要注意一个地方，就是别超了数字的范围，及时longlong也很容易爆炸，及时取余才是王道 http://hihocoder.com/problemset/pro

向右看齐/ 2022年08月21日 03:26/ 0 赞/ 141 阅读

相关 hihoCoder#1044 : 状态压缩·一

http://hihocoder.com/problemset/problem/1044 include <iostream> using n

叁歲伎倆/ 2022年08月21日 03:24/ 0 赞/ 191 阅读

相关 hihocoder #1176 : 欧拉路·一

欧拉路径：无向图存在欧拉路径的条件是：图是联通的（并查集判断pre\[ \]数组根节点的个数）、度数（入度加出度）为奇数的点有且仅有2个或者有0个。

╰半橙微兮°/ 2022年08月02日 15:00/ 0 赞/ 160 阅读

相关骨牌铺方格

Problem Description 在2×n的一个长方形方格中,用一个1× 2的骨牌铺满方格,输入n ,输出铺放方案的总数. 例如n=3时,为2× 3方格，骨牌的铺放

女爷i/ 2022年07月12日 12:36/ 0 赞/ 187 阅读

相关骨牌铺方格

1.知识点：递推 2.题意：在2×n的一个长方形方格中,用一个1× 2的骨牌铺满方格(可横铺或竖铺),输入n ,输出铺放方案的总数 3.递推关系方程：a\[i\] =

缺乏、安全感/ 2022年05月30日 08:45/ 0 赞/ 259 阅读

相关 hihoCoder--#1712

\1712 : 字符串排序时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述一般我们在对字符串排序时，都会按照字典序排序。当字符

迈不过友情╰/ 2022年05月27日 09:59/ 0 赞/ 307 阅读

相关 hihocoder-1720

[A - 小数数字][A -] 给定一个真分数P/Q(P < Q)，请你求出它的小数部分都

ゞ浴缸里的玫瑰/ 2022年05月27日 03:45/ 0 赞/ 228 阅读

相关 [hihoCoder] 骨牌覆盖问题·一

时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述骨牌，一种古老的玩具。今天我们要研究的是骨牌的覆盖问题：我们有一个2xN的长条形

缺乏、安全感/ 2021年09月17日 14:48/ 0 赞/ 286 阅读