lightOJ 1299 Fantasy Cricket

제목 링크:http://lightoj.com/volume_showproblem.php?problem=1299
제목:문자열 S 는 UDE 세 글자 만 포함 되 어 있 습 니 다.문자열 길 이 를 n,S[1,n]으로 설정 합 니 다.n 의 전체 배열 중 몇 개가 다음 조건 을 만족 시 키 는 지 구 합 니 다(특정한 전체 배열 을 A[1,n]로 설정 합 니 다):S[A[i]를 U 로 설정 하면 A[i]i;S[A[i]를 E 로 하면 A[i]=i.다시 말 하면 원래 문자열 의 알파벳 D 는 모두 앞으로 이동 해 야 하고 U 는 모두 뒤로 이동 해 야 하 며 E 는 변 하지 않 는 다 는 것 이다.
사고방식:분명히 E 에 대해 우 리 는 직접 무시 하면 된다.f[i][j]를 설정 하면 앞 i 개의 위치 에 j 개의 자모 가 배치 되 지 않 은 위치 가 있다 는 것 을 나타 낸다.그러면:
(1)현재 알파벳 이 D 이면 f[i][j]=f[i-1][j]*j(앞에서 위 치 를 찾 아 이 D 를 내 려 놓 고),f[i][j-1]=f[i][j]*j*j(앞에서 놓 지 않 은 U 를 이 자리 에 놓 고 이 자리 D 를 내 려 놓 는 것);
(2)현재 알파벳 은 D,f[i][j+1]=f[i-1][j](놓 지 않 은 것 이 하나 더 생 겼 다),f[i][j]=f[i-1][j]*j(앞 에 놓 지 않 은 것 을 찾 아 여기에 놓 은 다음 이 위치의 U 를 놓 지 않 았 다).

char s[N];

i64 n,f[N][N];



void up(i64 &x,i64 y)

{

    x=(x+y%mod)%mod;

}





int cal()

{

    clr(f,0); f[0][0]=1;

    int i,j;

    FOR1(i,n)

    {

        if(s[i]=='D')

        {

            FOR0(j,i)

            {

                up(f[i][j],f[i-1][j]*j);

                if(j) up(f[i][j-1],f[i-1][j]*j*j);

            }

        }

        else

        {

            FOR0(j,i)

            {

                up(f[i][j+1],f[i-1][j]);

                up(f[i][j],f[i-1][j]*j);

            }

        }

    }

    return f[n][0];

}





int main()

{

    int num=0;

    rush()

    {

        RD(s+1);

        n=0;

        int i,L=strlen(s+1);

        FOR1(i,L) if(s[i]!='E') s[++n]=s[i];

        printf("Case %d: ",++num);

        PR(cal());

    }

}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

ant design vue에서 표 형식 렌더링 방식 지정

주의점: 정의된columns는 반드시 데이터에 써야 합니다. 그렇지 않으면 불러오는 과정에서 렌더링 순서로 인해 렌더링 함수를 식별할 수 없습니다. 렌더링 방법 1: 렌더 함수를 지정합니다. 렌더링 방법 2: 해당 ...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

lightOJ 1299 Fantasy Cricket

좋은 웹페이지 즐겨찾기