意甲冠军：
给你一个数列：
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;
}
版权声明：本文博客原创文章，博客，未经同意，不得转载。