意甲冠军：

给你一个数列：

f(0) = 0

f(n) = g(n,f(n-1))

g(x,y) = ((y-1)*x^5+x^3-xy+3x+7y)%9973

让你求f(n)  n <= 1e8

思路：

令m = 9973

easy观察g(x,y) = g(x%m,y)

f(x+m) = g( (x+m) %m , f(x+m-1))........

能够得到 f(x+m) = (A*f(x)+B)%m

f(x+2m) = (A*f(x+m)+B)%m

,.....

令x+km = n

先求出f(x) 在求出A,B然后算出f(n)

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

const int m = 9973;

int A,B;

int n;

int x,cnt;

int getX5(int x){

    int ret = 1;

    for(int i = 1; i <= 5; i++) {

        ret = (x*ret)%m;

    }

    return ret;

}

int getX3(int x) {

    int ret = 1;

    for(int i = 1; i <= 3; i++) {

        ret = (ret*x)%m;

    }

    return ret;

}

int getPos(int x) {

    return (x%m+m)%m;

}

int func(int n) {

    if(n==0) return 0;

    return getPos((getPos(getX5(n)-n+7)*func(n-1))%m+getPos((-getX5(n)+getX3(n)+3*n)));

}

void solve() {

    A = 1;

    B = 0;

    int ret = func(x);

    for(int i = x+m; i >= x+1; i--) {

        int k = i%m;

        B = (B+A*getPos((-getX5(k)+getX3(k)+3*k)))%m;

        A = (A*getPos(getX5(k)-k+7))%m;

    }

    for(int i = 1; i <= cnt; i++) {

        ret = (A*ret+B)%m;

    }

    printf("%d\n",ret);

}

int main() {

    while(~scanf("%d",&n)) {

        x = n%m;

        cnt = n/m;

        solve();

    }

    return 0;

}