1
如何計算n mod 1e9+7
的分區數,其中n<=50000
。如何計算n的分區數?
這裏是源問題http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1259(在中國)
簡單應用下列公式:a(n) = (1/n) * Sum_{k=0..n-1} d(n-k)*a(k)
給了我一個O(n^2)
解決方案。
typedef long long ll;
ll MOD=1e9+7;
ll qp(ll a,ll b)
{
ll ans=1;
while(b)
{
if(b&1) ans=ans*a%MOD;
a=a*a%MOD;
b>>=1;
}
return ans;
}
ll a[50003],d[50003];
#define S 1000
int main()
{
for(int i=1; i<=S; i++)
{
for(int j=1; j<=S; j++)
{
if(i%j==0) d[i]+=j;
}
d[i]%=MOD;
}
a[0]=1;
for(int i=1; i<=S; i++)
{
ll qwq=0;
for(int j=0; j<i; j++) qwq=qwq+d[i-j]*a[j]%MOD;
qwq%=MOD;
a[i]=qwq*qp(i,MOD-2)%MOD;
}
int n;
cin>>n;
cout<<a[n]<<"\n";
}
我提出了一個爲O(n^2)的解決方案。但是由於n <= 50000,這還不夠。 – newbie
請向我們展示O(n^2)解決方案。你在尋找所有n≤50000,還是隻是一些未知的n?另外,這聽起來像是比賽類型問題。請告訴我們你從哪裏得到問題,併發布問題的全文。 – Teepeemm
@鍾子倩你的解決方案有效嗎?請展示您的解決方案,以及您嘗試改進的內容。 –