51nod-원숭이가 바나나를 먹는다[dp]

20274 단어 dp51nod

본제


제목 링크: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); } }

좋은 웹페이지 즐겨찾기