HDU 4506 샤 오 밍 시리즈 이야기-사형 도움(빠 른 속도)
3058 단어 쾌속 멱
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others) Total Submission(s): 5361 Accepted Submission(s): 1445
Problem Description
샤 오 밍 은 ACM/ICPC 와 작별 한 후부 터 수학 문 제 를 연구 하기 시작 했다.하 나 는 다음 의 대학원 시험 준 비 를 할 수 있 고 이 기 회 를 빌려 일부 학우,특히 예 쁜 사 매 를 도 울 수 있다.아니,반 에서 유일한 여학생 이 또 하나의 수학 문 제 를 가지 고 샤 오 밍 에 게 물 었 는데 샤 오 밍 은 당연히 기뻐 서 받 아 들 였 다.그러나 그 가 문 제 를 자세히 읽 은 후에 자신 도 할 줄 모른다 는 것 을 알 게 되 었 다.이번 에는 샤 오 밍 이 멘 붕 이 왔 다.만약 에 자신 이 모른다 고 대답 하면 체면 이 없 지 않 겠 는가?
그래서 그 는 지금 개인 적 으로 너 에 게 이 문 제 를 해결 해 달라 고 부탁 하고 있다.문 제 는 이렇다.
n 개의 숫자 를 드 리 겠 습 니 다.각각 a1,a2,a3,a4,a5.
지금 문 제 는 t 단위 의 시간 을 구 할 때 이 n 개의 숫자 가 뭐 가 되 었 느 냐 는 것 이다.숫자 가 많 을 수 있 으 므 로 10^9+7 의 결 과 를 출력 하기 만 하면 됩 니 다.
Input
입력 데이터 의 첫 줄 은 T 조 테스트 데이터 가 있 음 을 나타 내 는 정수 T 입 니 다.
각 조 의 데 이 터 는 두 줄 이 있 고 첫 번 째 줄 은 세 개의 정수 n,t,k 를 입력 하 는 것 을 포함한다.그 중에서 n 은 숫자 개 수 를 대표 하고 t 는 두 번 째 단위 시간,k 대표 계 수 를 대표 한다.두 번 째 줄 에 n 개의 숫자 ai 를 입력 하면 모든 숫자 가 시 작 될 때 얼마나 되 는 지 를 나타 낸다.
[Technical Specification]
T <= 100
1 <= n <= 10 ^ 4
0<=t<=10^9 그 중 t=0 은 초기 상 태 를 나타 낸다.
1 <= k <= 10 ^ 9
1 <= ai<= 10 ^ 9
Output
각 그룹의 데이터 에 대해 t 단위 시간 을 출력 한 후 이 n 개의 숫자 가 무엇 으로 변 했 는 지 출력 할 때
두 숫자 사이 에 빈 칸 을 출력 하고 줄 끝 에 남 은 빈 칸 을 출력 하지 마 십시오.구체 적 인 예 는 다음 과 같 습 니 다.
Sample Input
2
3 2 5
1 2 3
3 0 5
1 2 3
Sample Output
50 75 25
1 2 3
t 차 변환 이 필요 한 후 각 수의 앞 계 수 는 k^t 이 고 변 경 된 수 는 계수*특정한 수 입 니 다.예 를 들 어 최초의 세 수 는 a,b,c 입 니 다.
t 차 변환 후,예 를 들 어 k^t*b,k^t*c,k^t*a
계수 뒤의 수도 규칙 적 이다.
한 마디 로 계 수 를 찾 아 규칙 을 찾 아 두 개 를 곱 하면 된다.
본 문 제 는 빠 른 멱 을 사용 하여 쉽게 말 하면 구원 이 끊임없이 t 에 대해 2 분 상승 을 한다.
<span style="font-family:Arial;">#include <iostream>
#include <cstring>
#include <algorithm>
#define LL __int64
using namespace std;
const int mod = 1000000007;
LL powmod(LL k,LL t){ //
LL ans=1;
while(t)
{
if(t&1) // t, k，
ans=(ans*k)%mod;
k=((k%mod)*(k%mod))%mod;
t>>=1;//
}
return ans%mod;
}
int main()
{
int i,j,k,kk;
int N;
int a,b,t;
int cnt,n;
int ary[10005];
scanf("%d",&N);
while(N--)
{
scanf("%d%d%d",&n,&t,&k);
for(i=1;i<=n;i++)
{
scanf("%d",&ary[i]);
}
LL sum = powmod(k,t);
k = (n-t+1)%n;
if(k<0)
k += n;
else
if(k==0)
k = n;
for(i=1,j=k;i<=n;i++,j++)
{
if(j==n+1)
j=1;
if(i==1)
printf("%d",(sum*ary[j])%mod);
else
printf(" %d",(sum*ary[j])%mod);
}
printf("
");
}
return 0;
}</span>좋은 웹페이지 즐겨찾기
