- 浏览: 308688 次
- 性别:
- 来自: 珠海
文章分类
最新评论
-
xialluyouyue:
Ubuntu下搭建nodejs+express+mongodb环境简单教程 -
k317544294:
Good 陈迪峰
(开源游戏) DOTA音效版 俄罗斯方块 -
基德KID.1412:
su1216 写道竖线代表或者,不代表替换
对哦~ 谢谢你的提 ...
正则表达式中特殊字符的用法(收藏) -
su1216:
竖线代表或者,不代表替换
正则表达式中特殊字符的用法(收藏) -
qiqijianglu:
基德KID.1412 写道qiqijianglu 写道基德KI ...
【高斯消元 求期望】HDU 4418 Time travel
http://acm.hdu.edu.cn/showproblem.php?pid=1575
Problem Description
A为一个方阵,则Tr A表示A的迹(就是主对角线上各项的和),现要求Tr(A^k)%9973。
Input
数据的第一行是一个T,表示有T组数据。
每组数据的第一行有n(2 <= n <= 10)和k(2 <= k < 10^9)两个数据。接下来有n行,每行有n个数据,每个数据的范围是[0,9],表示方阵A的内容。
Output
对应每组数据,输出Tr(A^k)%9973。
Sample Input
2
2 2
1 0
0 1
3 99999999
1 2 3
4 5 6
7 8 9
Sample Output
2
2686
简化&小技巧 模板:
Problem Description
A为一个方阵,则Tr A表示A的迹(就是主对角线上各项的和),现要求Tr(A^k)%9973。
Input
数据的第一行是一个T,表示有T组数据。
每组数据的第一行有n(2 <= n <= 10)和k(2 <= k < 10^9)两个数据。接下来有n行,每行有n个数据,每个数据的范围是[0,9],表示方阵A的内容。
Output
对应每组数据,输出Tr(A^k)%9973。
Sample Input
2
2 2
1 0
0 1
3 99999999
1 2 3
4 5 6
7 8 9
Sample Output
2
2686
#include <iostream> #include <fstream> #include <algorithm> #include <string> #include <set> //#include <map> #include <queue> #include <utility> #include <stack> #include <list> #include <vector> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <ctime> #include <ctype.h> using namespace std; #define L __int64 #define inf 0x3fffffff int res[15][15], n; void mul (int a[][15], int b[][15], int c, int res[][15]) //矩阵乘法 { int s[15][15] = {0}, y, i, j; for (i = 0; i < n; i++) for (j = 0; j < n; j++) for (y = 0; y < n; y++) s[i][j] = (s[i][j] + a[i][y] * b[y][j]) % c; //乘的同时模 memcpy (res, s, sizeof(s)); } void qpow (int a[][15], int b, int c) //快速取幂模 { while (b) { if (b & 1) mul (res, a, c, res); mul (a, a, c, a); b >>= 1; } } int main() { int t, k, i, j, a[15][15], ans; scanf ("%d", &t); while (t--) { scanf ("%d%d", &n, &k); for (i = 0; i < n; i++) for (j = 0; j < n; j++) res[i][j] = (i==j); for (i = 0; i < n; i++) for (j = 0; j < n; j++) scanf ("%d", a[i]+j); qpow (a, k, 9973); ans = 0; for (i = 0; i < n; i++) ans += res[i][i]; //主对角线上元素之和 printf ("%d\n", ans%9973); } return 0; }
简化&小技巧 模板:
#include <iostream> #include <fstream> #include <algorithm> #include <string> #include <set> #include <map> #include <queue> #include <utility> #include <stack> #include <list> #include <vector> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> //#include <ctime> #include <ctype.h> using namespace std; #define L long long #define inf 0x3fffffff #define FF(i, n) for (i = 0; i < n; i++) #define M 11 //阶数 int ret[M][M]; //结果矩阵 int init[M][M]; //初始矩阵 int tp[M][M]; //中间变量矩阵 void matmul (int a[][M], int b[][M], int n, int mod) { int i, j, k; FF(i, n) FF(j, n) tp[i][j] = 0; FF(i, n) FF(k, n) if (a[i][k]) FF(j, n) if (b[k][j]) tp[i][j] = (tp[i][j] + a[i][k] * b[k][j]) % mod; memcpy (a, tp, sizeof(tp)); } void qmod (int n, int b, int mod) { int i, j; FF(i, n) FF(j, n) ret[i][j] = (i==j); for ( ; b; b >>= 1) { if (b & 1) matmul (ret, init, n, mod); matmul (init, init, n, mod); } } int main() { int t, n, k, i, j, sum; scanf ("%d", &t); while (t--) { scanf ("%d%d", &n, &k); for (i = 0; i < n; i++) for (j = 0; j < n; j++) scanf ("%d", init[i]+j); qmod (n, k, 9973); sum = 0; for (i = 0; i < n; i++) sum = (sum + ret[i][i]) % 9973; printf ("%d\n", sum); } return 0; }
发表评论
-
HDU 3893 Drawing Pictures
2013-05-08 13:28 1601/* * [题意] * 有n个格子需要填色,有6 ... -
HDU 3483 A Very Simple Problem
2013-05-08 11:50 2454/* * [题意] * 输入n, x, m * ... -
HDU 3369 Robot
2013-05-07 10:35 1590/* * [题意] * 给出第一天是星期几,给出n ... -
HDU 3306 Another kind of Fibonacci
2013-05-04 13:54 1503/* * [题意] * 已知: * ... -
HDU 3221 Brute-force Algorithm
2013-05-04 13:31 1660/* * [题意] * 略 * [解题方法] ... -
HDU 2855 Fibonacci Check-up
2013-05-03 23:05 1390/* * [题意] * F(0) = 0; F(1 ... -
HDU 2294 Pendant
2013-05-01 16:50 1456/* * [题意] * 有k种珍珠,每种珍珠N个, ... -
HDU 2842 Chinese Rings
2013-04-30 10:57 1549/* * [题意] * 有n个灯,初始时是全亮的 ... -
HDU 2604 Queuing
2013-04-30 08:50 1384/* * [题意] * 对于只由数字1和0构成的 ... -
HDU 1588 Gauss Fibonacci
2013-04-29 10:38 1593/* * [题意] * g(i) = k*i + ... -
HDU 2254 奥运
2013-04-29 10:36 1270/* * [题意] * 给出n条道路,k个询问,每 ... -
【高斯消元 求期望】HDU 4418 Time travel
2012-10-01 21:10 4409KIDx的解题报告 题目链接:http://a ... -
【高斯消元 求期望】ZJUT 1423 地下迷宫 + ZJUT 1317 掷飞盘
2012-09-26 20:10 1410KIDx的解题报告 1、地 ... -
hdu 4170 Supply Mission
2012-09-22 10:03 1206KIDx的解题报告 ... -
UVA 10202 + HDU 1270 小希的数表
2012-09-15 20:01 2696KIDx的解题报告 题目链接:http://ac ... -
HDU 1979 Fill the blanks
2012-08-20 12:40 1076KIDx的解题报告 题目链接:http://ac ... -
【生成树计数】HDU 4305 Lightning
2012-08-16 15:45 2627KIDx的解题报告 题 ... -
【数学】HDU 1719 Friend
2012-03-02 16:44 1163KIDx的解题报告 好久没写博客了,来题数学提提神 ... -
【BKDR_hash】HDU 2648 Shopping
2011-12-10 19:35 1780KIDx 的解题报告 题目链接:http://acm. ... -
Codeforces Beta Round #97 (Div. 2) 【完整题解】
2011-12-10 14:23 1499KIDx 的解题报告 题目链接:http://codeforc ...
相关推荐
可以达到10^100000,我们只能用字符串读这个数,这样的话我们肯定不能直接用快速幂算,其实有一个性质,2^N模一个质数,它的结果是具有周期性的,周期长度为mod-1,这道题就利用这个周期 性,具体步骤就是:先把N...
本人准备2020年保研机试时刷的题目(虽然最后机试取消了,...来自某中流985,在HDU和vjudge平台上大概刷了400道。本文件地图(excel表格)包含了绝大部分我刷过的题目,笔记中具有思路、代码、总结和心得。 大佬勿入!
现在,给你两个正的小数A和B,你的任务是代表大明计算出A+B的值。 Input 本题目包含多组测试数据,请处理到文件结束。 每一组测试数据在一行里面包含两个长度不大于400的正小数A和B。 Output 请在一行里面...
背包问题的模板,可以解决各类背包问题,根据问题需要修改参数即可。试用于ACM初学者。
acm hdu as easy as a+b
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
300+ AC 代码 。 大数 , 线段树 , 字符串 , dp.....
hdu2101AC代码
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
hdu_2102_passed_sorce