网址如下：

OpenJudge - 3872:Library

这玩意的dp公式应该很明显吧？

和斐波纳契数列一个样

就是n太大了，最高有十亿，不能用普通的dp来做

经验丰富的可能已经知道了

就是用快速幂加上斐波那契数列通项就行了，虽然f（2）= 2，但是设f（0）= 1就没差了

（斐波纳契数列的通项公式，把A^(n - 1)改成A^(n)就是本题的公式）

想要了解快速幂的，可以看看我之前写的博客：

快速幂算法的一种解决思路-CSDN博客

看其他大佬的也行

代码如下：

#include<cstdio>const int mol = 9901;struct Martix{bool have_val;int n[2][2];Martix():have_val(false){}Martix operator*(const Martix &tmp)const;
}m[1000000];Martix Martix::operator*(const Martix &tmp)const{Martix ans;for(int i = 0; i < 2; i++)for(int j = 0; j < 2; j++)ans.n[i][j] = (n[i][0] * tmp.n[0][j] + n[i][1] * tmp.n[1][j]) % mol;ans.have_val = true;return ans;
}void init(void){m[0].have_val = true;m[0].n[0][0] = m[0].n[1][0] = m[0].n[0][1] = 1;m[0].n[1][1] = 0;
}
void update(int n){if(!m[n - 1].have_val) update(n - 1);m[n] = m[n - 1] * m[n - 1];
}
int get_ans(int n){Martix sum; sum.have_val = false;int cnt = 0;while(n){if(n & 1){if(!m[cnt].have_val) update(cnt);if(sum.have_val) sum = sum * m[cnt];else sum = m[cnt];}n >>= 1; cnt++;}return sum.n[0][0];
}int main(void)
{int n; init();while(scanf("%d", &n) == 1 && n != -1) printf("%d\n", get_ans(n));return 0;
}

饿昏了，干饭干饭