Haidora və qəribə massivlər (Həll təhlili)

Həll Verilmiş sorğu dəyərləri S_{\max}=\max s-a qədər, x>1 üçün \sigma(x)\ge 1+x olduğunu qeyd edin, buna görə də əgər \sigma(x)\le S_{\max} isə, onda x\le S_{\max}-1 olmalıdır, beləliklə x\in[1,S_{\max}]-ni saymaq kifayətdir; 1\le x\le S_{\max} üçün bütün $\sigma (x)$-i klassik bölənlərin cəmi süzgəci ilə hesablayın (hər bir bölən $d$ üçün, $d$-ni bütün $kd$ çoxluqlarına əlavə edin), sonra primalığı \sigma(p)=p+1 ilə xarakterizə edin (və kompozit x>1 üçün \sigma(x)>x+1), beləliklə icazə verilən dəyərlər tam olaraq x=1 və ya \sigma(x)\ne x+1 olanlardır;

hər 1\le v\le S_{\max} üçün müəyyən edin və toplam bölən cəmi ilə massivləri saymaq üçün bir DP istifadə edin: f[0]=1 qoyun və t\ge 1 üçün

çünki son elementi bölən cəmi $v$ olanı seçmək (c_v yollarında) müstəqil bir prefiks t-v-ni təmin edir; sonra bir sorğu $s$-ə cavab $f[s]$-dir.

Komplekslik \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;   
}