hdu4623:crime 수학 최적화 dp
12470 단어 HDU
제목 대의:
n개수의 배열에서 서로 인접한 두 수의 상호질적인 배열의 수량을 만족시키고 모형을 취하도록 구하다
그때 생각이 상압 dp였는데...dp[i][state]state는 2진법으로 어떤 수가 가져갔는지 기록합니다. i는 현재 서열의 끝에 있는 숫자를 나타냅니다.
그리고 gcd 상태 이동
그런데 n은 28인데 몇 억 개의 상태가 있는지 계산해 보세요.할 수 없다.
돌아온 후에 문제풀이를 찾았는데 수학 방법으로 최적화할 수 있다는 것을 발견하여 반나절 만에 마침내 ac가 되었다
우선 이 질문에서
두 수의 상호질 여부는 단지 그들의 질인수와 관계가 있기 때문에 질인수가 같은 수는 등가이다. 이 문제의 등가류라고 부른다
질인수는 이런 등가류를 찾아서 모든 종류의 수의 수량을 얻는 것이 매우 쉽다.
그래서 이런 등가류를 처리하고 마지막으로 모든 등가류에 수량의 배열수를 곱하면 답을 얻을 수 있다.
그러나 이때 수량이 생기면 2진법으로 압력을 가할 수 없으니 하히로 압력을 가해야 한다.
연구를 해보니 해시상압과 이진상압의 차이가 많지 않고 기수를 (1+1)^n에서 (num[1]+1)*(num[2]+1)으로...이해하기 쉬워요.
이러한 상태를 처리한 결과 n=28에 대해 560000개 상태만 있고 등가류수는 17이기 때문에 복잡도는 17*5600000이다
MLE가 생겼어.모드가 최대 30000이기 때문에, 그룹을 short로 바꾸었습니다. 중간 결과 int는 넘침을 방지하고 메모리가 터지지 않습니다.
그리고 시한 30s, 넘길 수 있을 줄 알았는데 또 T가 생겼어요.
그래서 잠시 생각해 보니 17, 19, 23 이 세 개의 수와 다른 임의의 수의 상호질이 발견되었다.그래서 그들은 1과 등가이다
이 최적화를 추가한 후 복잡도가 약 14*1800000으로 떨어졌다
8800ms AC...
코드는 다음과 같다.
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int prime[]={2,3,5,7,11,13,17,19,23};
const int np=9;
int state[30];
int g[300][300];
int vi[300];
int num[30];
int base[30];
short dp[19][2000000];
bool ok[29];
int n,m,ns,st;
void ini()
{
scanf("%d%d",&n,&m);
memset(g,0,sizeof(g));
memset(vi,0,sizeof(vi));
memset(num,0,sizeof(num));
ns=0;
state[++ns]=0;
num[ns]=1;
for(int i=2;i<=n;i++)
{
st=0;
if(ok[i])
{
num[1]++;
continue;
}
for(int j=0;j<np;j++)
{
if(i%prime[j]==0)
{
st|=(1<<j);
}
}
if(!vi[st])
{
state[++ns]=st;
num[ns]=1;
vi[st]=ns;
}
else
{
num[vi[st]]++;
}
}
for(int i=1;i<=ns;i++)
{
for(int j=1;j<=ns;j++)
{
if((state[i]&state[j])==0)
g[i][j]=1;
}
}
base[1]=1;
st=0;
for(int i=1;i<=ns;i++)
{
base[i+1]=base[i]*(num[i]+1);
st+=base[i]*num[i];
}
}
int getnum(int i,int x)
{
int res=(x%base[i+1])/(base[i]);
return res;
}
int getstate(int i,int num)
{
return num*base[i];
}
void dfs(int t,int x)
{
if(t==0)
{
dp[x][0]=1;
return ;
}
if(dp[x][t]!=-1)
return;
dp[x][t]=0;
for(int i=1;i<=ns;i++)
{
if(g[x][i]&&getnum(i,t)>=1)
{
dfs(t-base[i],i);
dp[x][t]=((int)dp[x][t]+dp[i][t-base[i]])%m;
}
}
return;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif // ONLINE_JUDGE
int T;
scanf("%d",&T);
memset(ok,0,sizeof(ok));
ok[17]=1;
ok[19]=1;
ok[23]=1;
while(T--)
{
ini();
memset(dp,-1,sizeof(dp));
int ans=0;
for(int i=1;i<=ns;i++)
{
dfs(st-base[i],i);
ans=((int)ans+dp[i][st-base[i]])%m;
}
for(int i=1;i<=ns;i++)
{
while(num[i]>1)
{
ans=((int)ans*num[i])%m;
num[i]--;
}
}
printf("%d
",ans);
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[HDU] 4089 활성화 확률 DPdp[i][j]를 모두 i개인의 대기열인 Tomato가 j위 서버가 마비될 확률로 역추를 사용하면 우리는 상태 이동 방정식을 얻을 수 있다. i == 1 : dp[1][1] = dp[1][1] * p1 + dp[1]...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.