Codeforces Round \ # 191 (Div. 2) C. Magic Five 등비 수열 의 빠 른 속도
1856 단어 알고리즘
이 문 제 는 POJ 3233 의 기본 적 인 사고방식 과 같다.
이 문 제 는 빠 른 멱 으로 구 해 야 한다. 만약 에 항수 가 많은 등비 수열 이 있다 면 구 와 공식 에 나 누 기 번 호 를 포함 해 야 하기 때문에 직접 mod 를 취 할 수 없고 빠 른 쌀 의 전환 을 해 야 한다.
예 를 들 어 sum = 2 ^ 1 + 2 ^ 2 + 2 ^ 3 + 2 ^ 4 + 2 ^ 5 + 2 ^ 6 + 2 ^ 7.....
모두 n 항 이 있다
이것 은 공식 입 니 다. 약 n% 2 = = 0 입 니 다. T(n)=T(n/2)+T(n/2)*2^(n/2);
만약 n% 2 = = = 1 T(n)=T(n/2)+T(n/2)*2^(n/2)+ 2^n;
이 문제 에 있어 서 먼저 주어진 순환 위치 상의 것 과 구 조 를 바탕 으로 한 다음 에 빠 른 속도 위의 공식 을 이용 하여 연결 하면 된다.
여기 서 나 는 시합 이 끝 난 후에 야 이 문 제 를 여러 번 고 쳤 다. 특히 주의해 야 한다int 64 연산 에 저 장 됩 니 다.
아래 에 제 코드 를 붙 여 주세요.
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<stdlib.h>
using namespace std;
const __int64 mod=1000000007;
__int64 all;
int Pow(__int64 n,int num){ // num^n
if(n==0)return 1;
if(n==1)return num;
__int64 tmp=Pow(n/2,num)%mod;
tmp=tmp*tmp%mod;
if(n%2==1)tmp=tmp*num%mod;
return (int)tmp;
}
__int64 len;
int q;
int fun(int n){ //
if(n==1)return all;
__int64 tmp=fun(n/2);
tmp=(tmp+tmp*Pow(n/2,q))%mod;
if(n%2==1)tmp=( tmp+Pow((n-1)*len,2)*all%mod )%mod;
return (int)tmp;
}
char a[2000000];
int main()
{
int n,ans;
while(scanf("%s",a)!=EOF){
cin>>n;
ans=0;
len=strlen(a);
q=Pow(len,2)%mod;
all=0;
for(int i=0;i<len;i++){
if(a[i]=='0'||a[i]=='5'){
all=(all+Pow(i,2))%mod;
}
//cout<<i<<" "<<ans<<endl;
}
//cout<<"all="<<all<<endl;
ans=fun(n);
cout<<ans<<endl;
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
