31. Uva-927 Integer Sequences from Addition of Terms

문제

 

<그림1: 문제 설명>

 

문제는 크게 어렵지 않다. a₁이 d개, a₂가 2d개, .... a_n이 nd개씩, 차례대로 있는 새로운 행렬 b를 생각할 때 주어진 an과 d에 대해 b의 k번째 원소를 구하는 것이다.

따라서 k가 어떤 m에 대해 m*(m+1)d/2<k<(m+1)*(m+2)d/2를 만족할 때, am이 bk가 된다. 

문제는 쉬운데, 범위가 넓어서 overflow가 나는 것 때문에 WA가 많이 날 것 같다. long long을 쓰자.

 

#define _CRT_SECURE_NO_WARNINGS
#include<cstdio>
#include<cstdlib>
#include<iostream>
long long mypow(long long x, long long y) {
	if (y == 0)  return 1;
	if (y & 1)
		return x * mypow(x * x, y / 2);
	else
		return mypow(x * x, y / 2);
}

long long calcPolynom(long long* pl, int n,int m) {
	//n:size of coefficient
	//have to calc a_m
	long long sum = 0;
	for (int i = 0; i <= n; i++) {
		sum+=pl[i]*mypow(m,i);
	}
	return sum;
}



int main() {
	long long C=0,n=0,d=0,k=0,m=0;
	/*
	C: the number of test case
	n: degree of polynomial
	d: occurrences of ai is d*i
	k:  kth element of new array
	*/
	long long polynomial[31];	//save coefficient of polynomial
	scanf("%lld", &C);
	while (C--) {
		scanf("%lld", &n);
		for (int i = 0; i <= n; i++) scanf("%lld", &polynomial[i]);
		scanf("%lld %lld", &d,&k);
		m = 0;
		while (k > m * (m + 1) * d / 2) m++;	//searching part
		printf("%lld\n", calcPolynom(polynomial, n, m));

	}

	return 0;
}