hdu1005--(Number Sequence)

성 경기 가 끝 난 후 에는 매일 문 제 를 연습 하고 컨디션 을 유지 하 며 지속 적 으로 진보 해 야 한다.
    제목:제목 링크:http://acm.hdu.edu.cn/showproblem.php?pid=1005。
    대체적인 사고방식:처음에 타 표를 사용 하여 규칙 을 찾 으 려 고 시 도 했 고 여러 조 의 수 를 입력 했다.각 조 의 수 는 일정한 규칙 이 있 었 다.제목 에 따라 f[n]=(A*f[n-1]+B*f[n-2])%7 을 알 수 있다.A 와 B 가 모두 7 의 배수 일 때 f[n](n>=2)는 0 으로 정 해 졌 기 때문에 이런 상황 은 단독으로 열거 할 수 있다.기본적으로 각 조 의 규칙 은 두 개의 연속 적 인 1 로 시작한다.그래서 시 계 를 치면(충분히 길 면 된다)연속 적 인 두 개의 1 의 위 치 를 판단 하고 기록 주기 가 길다.
다음은 ac 코드:
#include
int main(){
    int A,B,i;
    long n;
    int f[201];
    f[1]=f[2]=1;
    while(scanf("%d %d %ld",&A,&B,&n)){
        if(A==0&&B==0&&n==0)
            break;
        int ans;
        if(A%7==0&&B%7==0){
            if(n<=2)
                ans=1;
            else
                ans=0;
        }
        else{
            for(int i=3;i<=200;i++)
                f[i]=(A*f[i-1]+B*f[i-2])%7;
            int cnt;                      //        cnt=1 wa,      。。。
            for(int i=2;i<=200;i++){
                if(f[i+1]==1&&f[i+2]==1)
                    cnt=i;

            }
            n%=cnt;
            if(n==0)
                n=cnt;
            ans=f[n];
        }
        printf("%d
",ans); } return 0; }

좋은 웹페이지 즐겨찾기