先写一个完全背包，然后找规律，然后打表。

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;int a[2000000 + 100];int Zhong[2000000 + 100];int tot;int MOD = 1000000;int main(){    a[0] = 1;    a[1] = 1;    a[2] = 2;    a[3] = 2;    int i = 4;    tot = 0;    int k = 0;    Zhong[tot] = 2;    while (1)    {        if (i > 2000000) break;        a[i] = (a[i - 1] + Zhong[k]) % MOD;        a[i + 1] = (a[i - 1] + Zhong[k]) % MOD;        tot++; Zhong[tot] = a[i + 1] % MOD;        a[i + 2] = (a[i + 1] + Zhong[k]) % MOD;        a[i + 3] = (a[i + 1] + Zhong[k]) % MOD;        tot++; Zhong[tot] = a[i + 3] % MOD;        k++;        i = i + 4;    }    int n;    int T;    scanf("%d", &T);    while (T--)    {        scanf("%d", &n);        printf("%d\n", a[n] % MOD);    }    return 0;}