#if 0
#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 % MOD + B * dist % MOD * weight % MOD) % 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]));
if(D[0] % 3) swap(node1, node2);
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;
}
#else
#include <bits/stdc++.h>
#include "hexagon.h"
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
int xx[]={0, 1, 1, 0, -1, -1}, yy[]={2, 1, -1, -2, -1, 1};
int n;
ll A, B;
ll ans = 0;
int draw_territory(int N, int _A, int _B, vector<int> D, vector<int> L) {
n = N;
A = _A, B = _B;
ll ans = 0;
ll l = L[0];
ans += (l+1) * (l+2) / 2 % MOD * (A) % MOD;
ans += (l+1) * (l) / 2 % MOD * (B) % MOD;
ans += l * (l+1) % MOD * (l+l+1) % MOD * 500000004 % MOD * 333333336 % MOD * B % MOD;
return ans%MOD;
}
#endif
# |
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 |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
0 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 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
292 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
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 |
204 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 |
0 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 |
Incorrect |
1 ms |
288 KB |
Output isn't correct |
6 |
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 |
- |