hdu 4651 Partition && hdu 4658 Integer Partition——拆分数与五边形定理

时间:2023-03-09 13:29:29
hdu 4651 Partition && hdu 4658 Integer Partition——拆分数与五边形定理

题目:http://acm.hdu.edu.cn/showproblem.php?pid=4651

参考:https://blog.****.net/u013007900/article/details/42365823

   https://blog.****.net/visit_world/article/details/52734860

好像这样复杂度就是 \( O(n\sqrt{n} \) 的了。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int rdn()
{
int ret=;bool fx=;char ch=getchar();
while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}
while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();
return fx?ret:-ret;
}
const int N=1e5+,mod=1e9+;
int upt(int x){if(x>=mod)x-=mod;if(x<)x+=mod;return x;}
int n,a[N];
void init()
{
int n=1e5; a[]=;
for(int i=;i<=n;i++)
for(int j=;;j++)
{
int k0=j*(*j-)>>, k1=j*(*j+)>>;
int fx=(j&)?:-;
if(k0>i&&k1>i)break;
if(k0<=i)a[i]=upt(a[i]+fx*a[i-k0]);
if(k1<=i)a[i]=upt(a[i]+fx*a[i-k1]);
}
}
int main()
{
int T=rdn(); init();
while(T--)
n=rdn(),printf("%d\n",a[n]);
return ;
}

关于 hdu 4658 :https://blog.****.net/u013368721/article/details/45827909

大概就是原来是 \( P(x)*\phi(x) = 1 \) ,现在是 \( P_k(x) = \frac{\phi(x^k)}{\phi(x)} = \phi(x^k)*P(x) \)

每次想求 \( P_k(x) \) 的第 n 项系数,所以先把 \( P(x) \) 预处理出来,然后每次暴力算 \( P_k(x) \) 的第 n 项,就是 \( O(n\sqrt{n}) \) 了。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int rdn()
{
int ret=;bool fx=;char ch=getchar();
while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}
while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();
return fx?ret:-ret;
}
const int N=1e5+,mod=1e9+;
int upt(int x){if(x>=mod)x-=mod;if(x<)x+=mod;return x;}
int p[N];
void init()
{
int n=1e5; p[]=;
for(int i=;i<=n;i++)
for(int j=;;j++)
{
int k0=j*(*j-)>>, k1=j*(*j+)>>;
int fx=(j&)?:-;
if(k0>i&&k1>i)break;
if(k0<=i)p[i]=upt(p[i]+fx*p[i-k0]);
if(k1<=i)p[i]=upt(p[i]+fx*p[i-k1]);
}
}
int solve()
{
int n=rdn(),k=rdn(),ans=p[n];
for(int i=;;i++)
{
int k0=k*i*(*i-)>>, k1=k*i*(*i+)>>;
int fx=(i&)?-:;
if(k0>n&&k1>n)break;
if(k0<=n)ans=upt(ans+fx*p[n-k0]);
if(k1<=n)ans=upt(ans+fx*p[n-k1]);
}
printf("%d\n",ans);
}
int main()
{
init(); int T=rdn();
while(T--)solve();
return ;
}