1
n mod 1e9+7
のパーティション数を計算するにはどうすればいいですか?n<=50000
です。nのパーティション数を計算する方法は?
http://oeis.org/A000041を参照してください。ここで
は、単に式を適用し、ソースの問題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";
}
。しかし、n≦50000なので、まだ十分ではありません。 – newbie
私たちにO(n^2)ソリューションを教えてください。あなたはすべてn≦50000か、まったく不明なnを探していますか?また、これはコンテストの種類の問題のように聞こえる。どこから問題があるのか教えてください。質問の全文を投稿してください。 – Teepeemm
@ZhongZiqianあなたのソリューションは機能しますか?あなたの解決策と、正確に何を改善しようとしているのかを示してください。 –