HDU4651 Partition 【多项式求逆】

题目分析：

这题的做法是一个叫做五边形数定理的东西，我不会。

我们不难发现第$n$项的答案其实是：

$$\prod_{i=1}^{\infty}\frac{1}{1-x^i}$$

我们要对底下的东西求逆，可以尝试打表找一下这个的规律，就会发现底下那个函数，系数要么是$1$，要么是$-1$，要么是$0$。

而且这个函数是稀疏的，前$100000$项只有$515$项非$0$。可以打出表后暴力求逆。

所以这道题我们有了一个$O(515*n)$的做法。

代码：

 #include<bits/stdc++.h>

 using namespace std;

 const int maxn = ;

 const int mod = ;

 int num = ;

 int a[] ={,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,};

 int b[] = {,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,};

 int n,iv[maxn],res[maxn];

 void work(){

     iv[] = ;for(int i=;i<num;i++) res[a[i]]=,res[b[i]] = mod-;

     for(int i=;i<=n;i++){

         if(res[i] != ){

             iv[i] = mod-res[i];

             for(int j=;j<num;j++){

                 if(a[j] + i > n) break;

                 res[a[j]+i] += iv[i];

                 if(res[a[j]+i] >= mod) res[a[j]+i]-=mod;

             }

             for(int j=;j<num;j++){

                 if(b[j] + i > n) break;

                 res[b[j]+i] -= iv[i];

                 if(res[b[j]+i] < ) res[b[j]+i] += mod;

             }

         }

     }

 }

 int main(){

     n = ;

     work();

     int T; scanf("%d",&T);

     while(T--){

         scanf("%d",&n);

         printf("%d\n",iv[n]);

     }

     return ;

 }