[[AHOI2009] 중국 장기!]
보아하니 아무런 사고방식도 없는 데다가 문제풀이에 눌린 라벨에 현혹되어 문제풀이에 디자인된 상태를 한 번 보았다
그다음에 잘 돼요.
우선 이 문제의 본질을 알아야 한다. 즉, 어떤 줄의 포에 대해서도 개수를 초과해서는 안 된다는 것이다. (2\)
우리가\(dp[i][j][k]\)를 설정하면 제\(i\)줄에 모두\(j\)열이 있는 포의 개수는\(2\)이고\(k\)열이\(1\)열인 총방안의 개수가 있음을 나타냅니다.
그렇다면 대포 한 개도 쏘지 않은 열수는 자연히\(m-k-j\)이다
그다음에 막 해도 돼요.
한 줄에 세 가지 선택이 있어요.
모두 다섯 가지 이동이 있는데, 바로 간단한 계수 원리와 조합 수학들이다
코드
#include
#include
#include
#define re register
#define maxn 105
#define LL long long
const LL P=9999973;
const LL inv=4999987;//2 P
int n,m;
LL dp[maxn][maxn][maxn];
int main()
{
scanf("%d%d",&n,&m);
dp[1][0][0]=1;
dp[1][0][1]=m;
dp[1][0][2]=m*(m-1)*inv%P;
for(re int i=1;im) continue;
int p=m-k-j;
if(!dp[i][j][k]) continue;
dp[i+1][j][k]=(dp[i+1][j][k]+dp[i][j][k])%P;//
if(j+1<=m&&k-1>=0)
dp[i+1][j+1][k-1]=(dp[i+1][j+1][k-1]+dp[i][j][k]*k%P)%P;// 1
if(p&&k+1<=m&&j+k+1<=m)
dp[i+1][j][k+1]=(dp[i+1][j][k+1]+dp[i][j][k]*p%P)%P;// 0
if(j+2<=m&&k-2>=0)
dp[i+1][j+2][k-2]=(dp[i+1][j+2][k-2]+(dp[i][j][k]*(k-1)*k%P)*inv)%P;// 1
if(p>=2&&k+2<=m&&j+k+2<=m)
dp[i+1][j][k+2]=(dp[i+1][j][k+2]+(dp[i][j][k]*(p-1)*p)%P*inv)%P;// 0
if(p&&j+1<=m&&k&&j+1+k<=m)
dp[i+1][j+1][k]=(dp[i+1][j+1][k]+dp[i][j][k]*k*p%P)%P;// 0， 1
}
LL ans=0;
for(re int i=0;i<=m;i++)
for(re int j=0;j<=m;j++)
if(i+j<=m) ans=(ans+dp[n][i][j])%P;
std::cout< 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
