51nod-원숭이가 바나나를 먹는다[dp]
본제
제목 링크:https://www.51nod.com/Contest/Problem.html#contestProblemId=1149
제목의 대의.
nn개수
문제풀이의 방향
분명히 kkk의 질인수는 최대 999개에 불과하다. 우리는 질인수를 dpdpdp로 진행할 것이다.선택한 수의 질인수가 마침 kk의 질인수라면 된다.
편의를 위해서 상태를 1차원으로 눌러주시면 됩니다.
c o d e code code
#include
#include
#include
#define ll long long
using namespace std;
const ll N=1100,XJQ=1e9+7;
struct node{
ll w,v;
}q[N];
bool cmp(node x,node y)
{
return x.w<y.w;}
ll n,K,v[N],sum[N],f[N*N],T,cnt,two;
void dfs(ll x,ll s,ll zs)
{
if(x>cnt){
(f[zs]+=f[s])%=XJQ;
return;
}
for(ll i=q[x].v-v[x];i>=0;i--)
dfs(x+1,s+sum[x-1]*i,zs+sum[x-1]*(i+v[x]));
}
int main()
{
scanf("%lld",&T);
while(T--){
scanf("%lld%lld",&n,&K);cnt=0;
for(ll i=2;i*i<=K;i++){
if(!(K%i)){
q[++cnt].w=i;
q[cnt].v=0;
while(!(K%i))
q[cnt].v++,K/=i;
}
}
if(K!=1) q[++cnt].w=K,q[cnt].v=1;
sort(q+1,q+1+cnt,cmp);
memset(f,0,sizeof(f));
f[0]=sum[0]=two=1;
for(ll i=1;i<=cnt;i++)
sum[i]=sum[i-1]*(q[i].v+1);
for(ll i=1;i<=n;i++){
ll x=0,z=0,l=0,r=1;
bool flag=0;
scanf("%lld",&x);
if(x==1){
two=two*2%XJQ;
continue;
}
memset(v,0,sizeof(v));
for(ll j=2;j*j<=x;j++){
if(!(x%j)){
while(q[l].w<j) r*=v[l],l++;
if(q[l].w!=j){
flag=1;break;}
while(!(x%j))
x/=j,v[l]+=(q[l].w==j);
if(v[l]>q[l].v){
flag=1;break;}
}
}
if(flag) continue;
if(x!=1){
for(l=0,r=1;q[l].w<x;r*=v[l],l++);
if(q[l].w==x)v[l]++;
}
dfs(1,0,0);
}
printf("%lld
",(f[sum[cnt]-1]*two)%XJQ);
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【경쟁 프로 전형적인 90문】008의 해설(python)
의 해설 기사입니다.
해설의 이미지를 봐도 모르는 (이해력이 부족한) 것이 많이 있었으므로, 나중에 다시 풀었을 때에 확인할 수 있도록 정리했습니다.
※순차적으로, 모든 문제의 해설 기사를 들어갈 예정입니다.
문자열...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
#include
#include
#include
#define ll long long
using namespace std;
const ll N=1100,XJQ=1e9+7;
struct node{
ll w,v;
}q[N];
bool cmp(node x,node y)
{
return x.w<y.w;}
ll n,K,v[N],sum[N],f[N*N],T,cnt,two;
void dfs(ll x,ll s,ll zs)
{
if(x>cnt){
(f[zs]+=f[s])%=XJQ;
return;
}
for(ll i=q[x].v-v[x];i>=0;i--)
dfs(x+1,s+sum[x-1]*i,zs+sum[x-1]*(i+v[x]));
}
int main()
{
scanf("%lld",&T);
while(T--){
scanf("%lld%lld",&n,&K);cnt=0;
for(ll i=2;i*i<=K;i++){
if(!(K%i)){
q[++cnt].w=i;
q[cnt].v=0;
while(!(K%i))
q[cnt].v++,K/=i;
}
}
if(K!=1) q[++cnt].w=K,q[cnt].v=1;
sort(q+1,q+1+cnt,cmp);
memset(f,0,sizeof(f));
f[0]=sum[0]=two=1;
for(ll i=1;i<=cnt;i++)
sum[i]=sum[i-1]*(q[i].v+1);
for(ll i=1;i<=n;i++){
ll x=0,z=0,l=0,r=1;
bool flag=0;
scanf("%lld",&x);
if(x==1){
two=two*2%XJQ;
continue;
}
memset(v,0,sizeof(v));
for(ll j=2;j*j<=x;j++){
if(!(x%j)){
while(q[l].w<j) r*=v[l],l++;
if(q[l].w!=j){
flag=1;break;}
while(!(x%j))
x/=j,v[l]+=(q[l].w==j);
if(v[l]>q[l].v){
flag=1;break;}
}
}
if(flag) continue;
if(x!=1){
for(l=0,r=1;q[l].w<x;r*=v[l],l++);
if(q[l].w==x)v[l]++;
}
dfs(1,0,0);
}
printf("%lld
",(f[sum[cnt]-1]*two)%XJQ);
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【경쟁 프로 전형적인 90문】008의 해설(python)의 해설 기사입니다. 해설의 이미지를 봐도 모르는 (이해력이 부족한) 것이 많이 있었으므로, 나중에 다시 풀었을 때에 확인할 수 있도록 정리했습니다. ※순차적으로, 모든 문제의 해설 기사를 들어갈 예정입니다. 문자열...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.