글 읽기 - 시간초과

gudrbscse 7년 전 0

헤비사이드 부분분수 분해법으로 구현하였는데,,

그 시간초과가 발생합니다. O(nm) 을 어떻게 줄일수 있을지를 모르겠네요..ㅠ

#include<iostream>
#include<vector>
#include<stack>
#include<queue>
#include<algorithm>
#include<math.h>
#include<utility>
using namespace std;
int arr[1001];
double q[1001];
int p(int a, int n) {
	int t = 1;
	for (int i = 1; i <= n; i++) {
		t *= a;
		t %= 1000000007;
	}
	return t;
}
int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
		cin >> arr[i];
	for (int i = 1; i <= m; i++) {
		double sum = 1;
		for (int j = 1; j <= m; j++) {
			int u = arr[i];
			int d = arr[i] - arr[j];
			if (d != 0) {
				sum *= ((double)u / d);
				sum = fmod(sum, 1000000007.0);
			}
		}
		q[i] = sum;
	}
	double r = 0;
	for (int i = 1; i <= m; i++) {
		r += q[i] * p(arr[i], n);
		r = fmod(r  , 1000000007);
	}
	cout <<r << endl;
	return 0;
}

pichulia 7년 전 0

일단 int p(int a, int n);

이 함수 내용물을 O(lg n)으로 줄일 수 있습니다.

a^n mod m 을 O(lg n)만에 구하는 방법은 여기저기 많이 널려있을 테지만...일단 현제 코드에 맞게 변형해보자면

int p(int a, int n) {
long long int t = 1;

long long int z = a;

while(n) {

if(n%2){ t = (t*z)%1000000007;}

z = (z*z)%1000000007;

}
return t;
}

일단 이렇게 고쳐도 "틀렸습니다"를 받게 되는데요...

sum *= ((double)u / d);

이 부분에서 정확도와 관련한 어떤 문제가 발생하지 않을까 하는 조심스러운 추측을 합니다..

gudrbscse 7년 전 0

어떤 문제가 발생하는 건지를 모르겠네요 ㅠ

#include<iostream>
#include<vector>
#include<stack>
#include<queue>
#include<algorithm>
#include<math.h>
#include<utility>
using namespace std;
int arr[1001];
double q[1001];
int p(int a, int n) {
	long long int t = 1;
	long long int z = a;
	while (n) {
		if (n % 2) { t = (t*z) % 1000000007; }
		z = (z*z) % 1000000007;
		n /= 2;
	}
	return t;
}
int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
		cin >> arr[i];
	for (int i = 1; i <= m; i++) {
		int down = 1;
		for (int j = 1; j <= m; j++) {
			int d = arr[i] - arr[j];
			if (d != 0) {
				down *= d;
				down %= 1000000007;
			}
		}
		int up = p(arr[i], m - 1);
		q[i] = (double)up / down;
	}
	double r = 0;
	for (int i = 1; i <= m; i++) {
		r += q[i] * p(arr[i], n);
		r = fmod(r  , 1000000007);
	}
	cout <<r << endl;
	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간초과

gudrbscse 7년 전 0

pichulia 7년 전 0

gudrbscse 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말