[DP]hihoCoder #1147 시공진 문제 해결
1862 단어 기타 문제 라이브러리일반 DPHihocoderDP
제목의 대의.
nn개의 점의 그림을 보여 줍니다. 현재 임의의 두 점 사이에 길이가 1인 무방향변 (중변을 허용하지 않음) 을 만들 수 있습니다. 1에서 nn까지의 최단거리 거리가 KK인지 물어보십시오.n , K ≤ 100 n,K\le100 n,K≤100
문제 풀이 분석
묘한 DP!이 그림에 대해 층을 나누는 것을 고려할 수 있다. ii i층에 있는 모든 점의 최단거리 거리는 ii i이다. 그러면 1은 0층에 있고 n은 KK층에 있으며 각 층은 상층 또는 이 층의 노드와만 연결될 수 있다.f[i][j][k]f[i][j][k]f[i][j][k]를 설정하여 전 ii층을 위해 모두 jj개 노드를 사용하는데 그 중에서 제 ii층은 kk개 노드의 합법적인 방안이 있다.매거진 전 층에 xx개가 있으면 뚜렷한 전이 방정식은 f[i][j][k]=∑f[i-31][j-k][x][x]∗Cn-j+k+1k∗(2x-1)k∗2;2Ck2f[i][j]=\sumf[i-1][j-k][x]*C{n-j+k+1} {{{} * (2^x-1) ^k* 2^ {+ j+k^2} [j] [k] = ∑ f[i-1] [j-k] [x] [Cn-j+k+1k (2[j] [j] [[k] [k] [k] = ∑f[i[i[i[i] [j] [k] [x] [x] [x] [x] [x] [Cnn-k] [x] [x] [x] [x] [x] [x] [x] [x] [x] [x] [x] [x]]] [x] [x]] [x] [x]]] [x] [x]]]] [x] [x]]] [xK, K 층의 노드가 연결되어 있습니다.
예제 코드
제목 전송문
#include
using namespace std;
typedef long long LL;
const int tt=1e9+7;
int n,K,C[105][105],pw[10005];
LL ans,f[105][105][105];
void maken(){
for (int i=0;i<=n;i++) C[i][0]=1;
for (int i=1;i<=n;i++)
for (int j=1;j<=i;j++)
C[i][j]=(C[i-1][j]+C[i-1][j-1])%tt;
pw[0]=1; for (int i=1;i<=n*n;i++) pw[i]=pw[i-1]*2%tt;
}
LL ksm(LL x,int y){
LL sum=1,w=x;
for (;y;y>>=1,w=w*w%tt) if (y&1) sum=sum*w%tt;
return sum%tt;
}
int main()
{
freopen("portal.in","r",stdin);
freopen("portal.out","w",stdout);
scanf("%d%d",&n,&K); maken(); f[0][1][1]=1;
for (int i=1;i<=K;i++)
for (int j=i+1;j<=n-K+i;j++)
for (int k=1;k<=j-i;k++){
LL tem=(i==K)?C[n-j+k-1][k-1]:C[n-j+k-1][k];
for (int x=1;x<=j-k-i+1;x++)
f[i][j][k]=(f[i][j][k]+f[i-1][j-k][x]*tem%tt*ksm(pw[x]+tt-1,k)%tt*pw[C[k][2]]%tt)%tt;
if (i==K) ans=(ans+f[i][j][k]*pw[k*(n-j)+C[n-j][2]]%tt)%tt;
}
printf("%lld",ans);
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【UVa】【DP】10934 Dropping water balloons똑같은 수구가 KK개가 있고, N층 높이의 고층 건물에서 테스트가 진행된다.그러나 당신은 매우 게으르기 때문에 가장 적은 실험 횟수를 사용하여 수구의 경도가 도대체 얼마나 되는지 알고 싶다(어떤 층에서 던져서 마침 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
