#include <bits/stdc++.h>
#include "hexagon.h"
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
const ll INV2 = 500000004;
const ll INV3 = 333333336;
const int xx[]={0, 1, 1, 0, -1, -1}, yy[]={2, 1, -1, -2, -1, 1};
ll A, B;
namespace basicMath{ /// �⺻���� ����� ����ϴ� �Լ����� ���� �̸������̴�.
ll sum_1b (ll b){ /// 0���� b������ ������ ���� ��ȯ�Ѵ�.
return (b * (b+1) % MOD * INV2 % MOD);
}
ll sum_ab (ll a, ll b){ /// a���� b������ ������ ���� ��ȯ�Ѵ�.
return (sum_1b(b) - sum_1b(a-1) + MOD) % MOD;
}
ll sum_1b2 (ll b){ /// 0���� b������ ������ ������ ���� ��ȯ�Ѵ�.
return (b * (b+1) % MOD * (b+b+1) % MOD * INV2 % MOD * INV3 % MOD);
}
ll sum_ab2 (ll a, ll b){ /// a���� b������ ������ ������ ���� ��ȯ�Ѵ�.
return (sum_1b2(b) - sum_1b2(a-1) + MOD) % MOD;
}
ll sum_mult(ll s, ll e, ll d, ll l){
/// �Ա��� �β��� s, �ⱸ�� �β��� e�̴�.
/// �Ա��� �ⱸ ������ �Ÿ��� l�̰�, �������� �Ա� ������ �Ÿ��� d�̴�.
ll numberOfPoints = 0; /// ���� ������, ��� A�� ���ؾ� �Ѵ�.
ll distanceSum = 0; /// �Ÿ� ������, ��� B�� ���ؾ� �Ѵ�.
if(s < e){ /// �β��� ���� Ŀ���� ��츦 ����Ѵ�.
numberOfPoints = sum_ab(s+1, e-1);
distanceSum = (sum_ab2(s+1, e-1) + (d-s)*sum_ab(s+1, e-1)%MOD + MOD) % MOD;
}
else if(s == e){ /// �β��� ������ ��츦 ����Ѵ�.
numberOfPoints = (l-1) * s % MOD;
distanceSum = sum_ab(d+1, d+l-1);
}
else{
numberOfPoints = sum_ab(e+1, s-1);
distanceSum = (s*s%MOD*(s-e-1)%MOD - sum_1b2(s-e+1)%MOD + (d-s)*sum_ab(e+1, s-1)%MOD + MOD + MOD) % MOD;
}
return (A * numberOfPoints + B * distanceSum) % MOD;
}
}
using namespace basicMath;
namespace Calculator{
struct Node { /// Ʈ���� ��� ����ü�� �����Ѵ�.
ll weight; /// ����� ����ġ (�ش� ���� ���� �����ϴ� �� ����)�� �����Ѵ�.
struct Edge{ /// Ʈ���� ���� ����ü�� �����Ѵ�.
Node* cur; /// ���� ������ �ǹ��ϴ� ��� ������ �����̴�.
Node* nxt; /// ��ǥ ������ �ǹ��ϴ� ��� ������ �����̴�.
ll slope; /// ������ �β� ��ȭ�� �ǹ��ϴ� �����̴�.
ll len; /// ������ ���̸� �ǹ��ϴ� �����̴�.
Edge(Node* cur, Node* nxt, ll slope, ll len): cur(cur), nxt(nxt), slope(slope), len(len){} /// ������ �������̴�.
};
vector<Edge> link; /// Ʈ�� ����� ���� ����Ʈ�̴�.
Node(ll weight): weight(weight){} /// ����� �������̴�.
ll calculateAnswer(Node* prv = nullptr, ll dist = 0){ /// Ʈ�� ������ dfs�� ���� ���� ����ϴ� �Լ��̴�.
ll returnValue = (A * weight + B * dist % MOD * weight) % MOD;
for(Edge edge: link){ /// ���� �������� ��ȸ�Ѵ�.
if(edge.nxt == prv) continue; /// �̹� �湮�� ������ �湮���� �ʴ´�.
if(edge.len >= 2){
returnValue += sum_mult(weight, edge.nxt->weight, dist, edge.len); /// ���� ������ ���� �����Ѵ�.
returnValue %= MOD;
}
returnValue += edge.nxt->calculateAnswer(this, dist + edge.len); /// ���� �������� �̵��Ѵ�.
returnValue %= MOD;
}
return returnValue; /// ���� ��ȯ�Ѵ�.
}
};
vector<Node*> makeTree(int N, vector<int> D, vector<int> L){ /// Ʈ���� �����ϴ� �Լ��̴�.
Node* node1 = new Node(1);
Node* node2 = new Node(L[0]+1);
node1->link.push_back(Node::Edge(node1, node2, 1, L[0]));
node2->link.push_back(Node::Edge(node2, node1, -1, L[0]));
return vector<Node*> {node1, node2};
}
ll calc(int N, vector<int> D, vector<int> L){
/// Ǯ�̴� ũ�� �� �ܰ�� ���� �� �ִ�.
/// ù ��° �ܰ�: Ʈ���� �����ϱ�
/// �� ��° �ܰ�: Ʈ�� ������ Ʈ�� DP�� �����ؼ� ������ ���
vector<Node*> nodeList = makeTree(N, D, L); /// Ʈ���� �����Ѵ�.
ll returnValue = nodeList[0]->calculateAnswer(); /// Ʈ�� ������ ���� ����Ѵ�.
for(Node* pnt: nodeList){ /// ����� �� ������ �ش�.
delete pnt;
}
return returnValue; /// ���� ��ȯ�Ѵ�.
}
}
int draw_territory(int N, int _A, int _B, vector<int> D, vector<int> L){
A = _A * 2 * INV3 % MOD, B = _B;
for(int i=0; i<N; i++) D[i]--;
ll Answer = 0;
Answer += Calculator::calc(N, D, L);
for(int i=0; i<N; i++) D[i] = (D[i] + 1) % 6;
Answer += Calculator::calc(N, D, L);
for(int i=0; i<N; i++) D[i] = (D[i] + 1) % 6;
Answer += Calculator::calc(N, D, L);
Answer %= MOD;
Answer *= INV2;
Answer %= MOD;
return Answer;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Incorrect |
1 ms |
276 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
288 KB |
Output is correct |
3 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
288 KB |
Output is correct |
3 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |