هايدورا والمصفوفات الغريبة (شرح الحلول)

الحل بالنظر إلى قيم الاستعلام حتى 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;   
}