HDU 5117 Fluorescent 수학적 배치 DP
먼저 기대치가 E(x)*2^m인 상황을 고려하면 0으로 불이 꺼진 것을 표시하고 1로 불이 켜진 것을 나타내는 간단한 상압의 사상을 고려하여 각각 불이 켜진 상황에 몇 가지 방법이 있는지 추측하기 어렵지 않다.
기대치가 E(x^3)*2^m인 확장, 즉 원제가 요구하는 것은 사실 수학 전개 모델이 될 수 있다.
X=(X0+X1+X2+X3+...+Xn-1), Xi는 i호등이 꺼졌는지 켜졌는지 표시한다.
X^3=(X0+X1+X2+X3+...+Xn-1)^3 수학이 전개된 후 사실은 모든 Cijk*Xi*Xj*Xk(0<=i, j, k
13532250
2015-04-23 09:02:28
Accepted
5117
187MS
1572K
1585 B
G++
howardcn
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
const int mod = 1000000007;
typedef long long LL;
LL dp[2][8];
int f[51][51];
int main()
{
// freopen("data.in","r",stdin);
int T,N,M,K,l,now;
LL tmp;
scanf("%d",&T);
for(int cas=1;cas<=T;cas++){
LL ans=0;
scanf("%d%d",&N,&M);
memset(f,0,sizeof f);
for(int i=0;i<M;i++){
scanf("%d",&K);
for(int j=0;j<K;j++){
scanf("%d",&l);
f[i][l-1]++;
}
}
for(int i=0;i<N;i++){
for(int j=i;j<N;j++){
for(int k=j;k<N;k++){
memset(dp,0,sizeof dp);
dp[0][0]=1;
now=1;
for(int s=0;s<M;s++,now^=1){
tmp=0;
if(f[s][i]) tmp|=1;
if(f[s][j]) tmp|=2;
if(f[s][k]) tmp|=4;
for(int t=0;t<8;t++){
dp[now][t]=dp[now^1][t];
dp[now][t]+=dp[now^1][t^tmp];
dp[now][t]%=mod;
}
}
#define u dp[now^1][7]
tmp = u;
if(i!=j&&j!=k) u*=6;
else if(i==j&&j==k) ;
else u*=3;
ans=(ans+u)%mod;
}
}
}
printf("Case #%d: %I64d
",cas,ans);
}
return 0;
}13532250
2015-04-23 09:02:28
Accepted
5117
187MS
1572K
1585 B
G++
howardcn
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Cognos 보고서 PDF 출력의 성능 튜닝 매개 변수 검증 결과보고서를 PDF로 출력할 때 Report Service 또는 Batch Report Service 매개변수에서 PDF 출력의 글꼴과 압축을 조정할 수 있는 Cognos Administration 매개변수가 있습니다....
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
