SP6286-SUMMUL - Sum of products
题目:
题目描述:
One boy Petya decided to practice in addition and multiplication of numbers. For this he chose some positive integer n, and ordered all the ways to decompose it into two or more terms of positive integers, and the ways in different order terms are considered to be different (for example, for n = 3 there are three ways: 1 + 2, 2 + 1 and 1 + 1 + 1). Then he replaced all the plus signs with multiplication, and added the results (for n = 3: 1 × 2 + 2 × 1 + 1 × 1 × 1 = 5). After practicing for the day he decided to check the correctness of his calculations. Help Petya find the right answers.
输入格式:
The first line contains T (1 <= T <= 1000) - the number of tests. Following T lines contain n (1 <= n <= 10 ^ 9).
输出格式:
For each n from the input print the result Petya should get modulo 1000000007.
样例:
样例输入1:
样例输出1:
思路:
实现:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
| // Problem: SP6286 SUMMUL - Sum of products
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/SP6286
// Memory Limit: 1.46 MB
// Time Limit: 170 ms
// Author: Ybw051114
//
// Powered by CP Editor (https://cpeditor.org)
#include "ybwhead/ios.h"
#define il inline
#define mem(p) memset(&p, 0, sizeof(p))
const ll mod = 1000000007;
ll n, m;
struct mat
{
ll a[3][3], r, c;
};
il mat mul(mat x, mat y)
{
mat p;
mem(p);
for (int i = 0; i < x.r; i++)
for (int j = 0; j < y.c; j++)
for (int k = 0; k < x.c; k++)
p.a[i][j] = (p.a[i][j] + x.a[i][k] * y.a[k][j]) % mod;
p.r = x.r, p.c = y.c;
return p;
}
il void fast(ll k)
{
mat p, ans;
mem(p), mem(ans);
p.r = p.c = 2;
p.a[0][0] = p.a[0][1] = p.a[1][0] = 1;
p.a[1][1] = 2;
ans.r = 2, ans.c = 2;
ans.a[0][0] = ans.a[1][1] = 1;
while (k)
{
if (k & 1)
ans = mul(ans, p);
p = mul(p, p);
k >>= 1;
}
p.r = 2;
p.c = 1;
p.a[0][0] = 0;
p.a[1][0] = 1;
ans = mul(ans, p);
yout << (ans.a[0][0] - n + mod) % mod << endl;
}
il ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
int main()
{
int TTT;
yin >> TTT;
while (TTT--)
{
yin >> n;
fast(n);
}
return 0;
}
|