tty的方程math

Time Limit: 50 Sec Memory Limit: 128 MB

Description

给定n、m、k、p。

a+b+c=n, a^2+b^2+c^2=m, a^3+b^3+c^3=k。

求a^p+b^p+c^p。

Input

输入n、m、k、p

Output

以A/B形式表示答案。

Sample Input

5 7 11 4

Sample Output

27/1

HINT

0<=n,m,k <=20，0<=p<=10

Solution

img

Code

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
#include<bits/stdc++.h>
using namespace std;
typedef long long s64;

const int ONE = 1000005;
const int MOD = 1e9 + 7;

int get()
{
    int res = 1, Q = 1; char c;
    while( (c = getchar()) < 48 || c > 57)
        if(c == '-') Q = -1;
    if(Q) res = c - 48;
    while( (c = getchar()) >= 48 && c <= 57)
        res = res * 10 + c - 48;
    return res * Q;
}

s64 gcd(s64 a, s64 b)
{
    while(s64 r = a % b) {a = b; b = r;}
    return b;
}

int n, m, k, p;
struct power
{
    s64 fz, fm;
}Ans[ONE], A, B, C, now;

power Deal(power a, power b)
{
    s64 fz = a.fz * b.fm + b.fz * a.fm, fm = a.fm * b.fm;
    int p1 = fz > 0, p2 = fm > 0;
    fz = abs(fz), fm = abs(fm);
    s64 r = gcd(fz, fm);
    return (power){p1 * fz / r, p2 * fm / r};
}

int main()
{
    cin >> n >> m >> k >> p;
    if(p == 0) {printf("3"); return 0;}
    Ans[1] = (power){n, 1};
    Ans[2] = (power){m, 1};
    Ans[3] = (power){k, 1};

    A = (power){n, 1};
    B = (power){n * n - m, 2};
    C = (power){2 * k + 3 * n * (n * n - m) - 2 * n * n * n, 6};

    for(int i = 4; i <= p; i++)
    {
        power now = (power){A.fz * Ans[i-1].fz, A.fm * Ans[i-1].fm};
        now = Deal(now, (power){C.fz * Ans[i-3].fz, C.fm * Ans[i-3].fm});
        now = Deal(now, (power){-B.fz * Ans[i-2].fz, B.fm * Ans[i-2].fm});

        Ans[i] = now;
    }

    printf("%d/%d", Ans[p].fz, Ans[p].fm);
}