f[n] += 1 + f[i] * (n - i);

这个公式可以利用sum(前n项和)进行O(1)的递推。也可以自己根据结果总结规律f[i] = 3 * f[i -1] - f[i - 2];

但是快速幂会超时。所以想到有循环节，写个程序找循环节，发现为75000，所以只需要求出前75000个即可。

#include 
      
        #include 
       
         #include 
        
          #include 
         
           using namespace std; #define maxn 100005 #define w 100000 int f[maxn]; int n; int main() {
    //freopen("t.txt", "r", stdin);     f[0] = 1;     f[1] = 1; for (int i = 2; i < 75000; i++)         f[i] = (3 * f[i - 1] - f[i - 2] + w) % w; int t;     scanf("%d", &t); while (t--)     {
            scanf("%d", &n);         printf("%d\n", f[n % 75000]);     } return 0; }