Гайдора та дивні масиви (Розбір)

Рішення Задано значення запитів до S_{\max}=\max s, зверніть увагу, що для будь-якого x>1 ми маємо \sigma(x)\ge 1+x, отже, якщо \sigma(x)\le S_{\max}, то x\le S_{\max}-1, тому достатньо перерахувати x\in[1,S_{\max}]; обчисліть всі $\sigma (x)$ для 1\le x\le S_{\max} за допомогою класичного решета для суми дільників (для кожного дільника $d$ додайте $d$ до всіх кратних $kd$), потім охарактеризуйте простоту, використовуючи \sigma(p)=p+1 (а для складного x>1 ми маємо \sigma(x)>x+1), тому дозволені значення - це точно ті, для яких x=1 або \sigma(x)\ne x+1; визначте

для кожного 1\le v\le S_{\max}, і підрахуйте масиви за загальною сумою дільників, використовуючи один DP за сумою: нехай f[0]=1 і для t\ge 1 нехай

тому що вибір останнього елемента з сумою дільників $v$ (в c_v способами) залишає незалежний префікс, що вносить t-v; тоді відповідь на запит $s$ - це $f[s]$.

Складність \mathcal{O}(s^2).

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int M=1000000007;
ll divsum[20005];
ll countt[20005];
ll ans[10005];
int main(){
    countt[0]=1;
 for(int i=1;i<=20000;i++)
 {
     for(int j=1;j*i<=20000;j++)
     {
         divsum[i*j]+=i;
     }
     if(divsum[i]!=i+1&&divsum[i]<=10000)
     {
         countt[divsum[i]]++;
     }
 }
 ans[0]=1;
 for(int i=1;i<=10000;i++)
 {
     for(int j=1;j<=i;j++)
     {
         ans[i]+=(ans[i-j]*countt[j])%M;
         ans[i]%=M;
     }
 }
 int t;
 cin>>t;
 while(t--)
 {
     int s;
     cin>>s;
     cout<<ans[s]<<'\n';
 }
 return 0;   
}