数学--数论--HDU 2802 F(N) 公式推导或矩阵快速幂
2024-10-20 18:58:31
Giving the N, can you tell me the answer of F(N)?
Input
Each test case contains a single integer N(1<=N<=10^9). The input is terminated by a set starting with N = 0. This set should not be processed.
Output
For each test case, output on a line the value of the F(N)%2009.
Sample Input
1
2
3
0
Sample Output
1
7
20
打了个表 4018一循环
#include <bits/stdc++.h>
using namespace std;
int f[6000];
int main()
{
f[1] = 1;
f[2] = 7;
for (int i = 3; i < 4020; i++)
{
f[i] = f[i - 2] + 3 * i * i - 3 * i + 1;
f[i] %= 2009;
}
int n;
while (scanf("%d", &n), n)
{
printf("%d\n", f[n % 4018]);
}
}
或者矩阵快速幂分奇数偶数
#include "bits/stdc++.h"
using namespace std;
const int MOD = 2009;
const int MAT[][4] = {
{1, 3, 3, 1},
{0, 1, 4, 4},
{0, 0, 1, 2},
{0, 0, 0, 1}
};
const int TABLE1[] = {1, 4, 2, 1};
const int TABLE2[] = {7, 9, 3, 1};
struct Mat {
int mat[4][4];
Mat() {
memset(mat, 0, sizeof(mat));
}
friend Mat operator * (Mat n, Mat m) {
Mat res;
for (int k = 0; k < 4; k++)
for (int i = 0; i < 4; i++)
for (int j = 0; j < 4; j++)
res.mat[i][j] = (res.mat[i][j] + n.mat[i][k] * m.mat[k][j]) % MOD;
return res;
}
} m;
Mat mat_pow(Mat n, int k) {
Mat res;
for (int i = 0; i < 4; i++) {
res.mat[i][i] = 1;
}
while (k) {
if (k & 1) {
res = res * n;
}
n = n * n;
k >>= 1;
}
return res;
}
int main() {
int n;
while (scanf("%d", &n) && n) {
if (n == 1) {
puts("1");
continue;
}
if (n == 2) {
puts("7");
continue;
}
memmove(m.mat, MAT, sizeof(m.mat));
m = mat_pow(m, n - 1 >> 1);
int res = 0;
if (n & 1) {
for (int i = 0; i < 4; i++) {
res = (res + m.mat[0][i] * TABLE1[i]) % MOD;
}
} else {
for (int i = 0; i < 4; i++) {
res = (res + m.mat[0][i] * TABLE2[i]) % MOD;
}
}
printf("%d\n", res);
}
return 0;
}
最新文章
- [APUE]UNIX进程的环境(下)
- SalesForce 记录级别安全性
- Servlet入门笔记
- c#语言-高阶函数
- EXCEL科学计数法转为文本格式
- if语句
- vpython初探
- 2005 TCO Online Round 1 - RectangleError
- js与C++交互及C++解析json
- 二模 （1） day2
- 微软发布屏蔽Win10升级的官方办法
- Android（java）学习笔记264：Android下的属性动画高级用法（Property Animation）
- [转]javascript指定事件处理程序包括三种方式：
- Openjudge-计算概论（A）-计算书费
- Developing a Custom Membership Provider from the scratch, and using it in the FBA (Form Based Authentication) in SharePoint 2010
- Mysql SQL注入漏洞
- pytest自动化3：fixture之conftest.py实现setup
- 立足中国，走向世界（Made in China, Go to World）
- JUnit4 单元测试
- pygame系列_小球完全弹性碰撞游戏_源码下载