QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#103366 | #5010. Squaring the Triangle | joesmitty | AC ✓ | 2516ms | 3560kb | C++20 | 4.5kb | 2023-05-05 14:37:08 | 2023-05-05 14:37:11 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned int uint;
typedef vector<int> vi;
typedef vector< vector <int> > vvi;
typedef pair<int, int> pii;
typedef pair < pair < int, int >, int > piii;
typedef pair < pair <int, int > , pair <int, int> > piiii;
typedef pair<ll, ll> pll;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
#define FOR(i,a,b) for(int i = a; i < b; i ++)
#define RFOR(i,a,b) for(int i = a-1; i >= b; i --)
#define all(a) a.begin(), a.end()
#define endl '\n';
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define ff first
#define ss second
template <typename T>
void pr(vector<T> &v) {
FOR(i, 0, sz(v)) cout << v[i] << " ";
cout << endl;
}
template <typename T>
void pr(vector<vector<T> > &v) {
FOR(i, 0, sz(v)) { pr(v[i]); }
}
template <typename T>
void re(T &x) {
cin >> x;
}
template <typename T>
void re(vector<T> &a) {
FOR(i, 0, sz(a)) re(a[i]);
}
template <class Arg, class... Args>
void re(Arg &first, Args &... rest) {
re(first);
re(rest...);
}
template <typename T>
void pr(T x) {
cout << x << endl;
}
template <class Arg, class... Args>
void pr(const Arg &first, const Args &... rest) {
cout << first << " ";
pr(rest...);
cout << endl;
}
void ps() { cout << endl; }
template<class T, class... Ts>
void ps(const T& t, const Ts&... ts) {
cout << t; if (sizeof...(ts)) cout << " "; ps(ts...);
}
const ll MOD = 1000000007;
#define inf 1e18;
#define INF INT_MAX;
long double PI = 4*atan(1);
long double eps = 1e-12;
template<int MOD, int RT> struct mint {
static const int mod = MOD;
static constexpr mint rt() { return RT; } // primitive root for FFT
int v; explicit operator int() const { return v; } // explicit -> don't silently convert to int
mint():v(0) {}
mint(ll _v) { v = int((-MOD < _v && _v < MOD) ? _v : _v % MOD);
if (v < 0) v += MOD; }
bool operator==(const mint& o) const {
return v == o.v; }
friend bool operator!=(const mint& a, const mint& b) {
return !(a == b); }
friend bool operator<(const mint& a, const mint& b) {
return a.v < b.v; }
// friend void re(mint& a) { ll x; re(x); a = mint(x); }
// friend str ts(mint a) { return ts(a.v); }
mint& operator+=(const mint& o) {
if ((v += o.v) >= MOD) v -= MOD;
return *this; }
mint& operator-=(const mint& o) {
if ((v -= o.v) < 0) v += MOD;
return *this; }
mint& operator*=(const mint& o) {
v = int((ll)v*o.v%MOD); return *this; }
mint& operator/=(const mint& o) { return (*this) *= inv(o); }
friend mint mpow(mint a, ll p) {
mint ans = 1; //assert(p >= 0);
for (; p; p /= 2, a *= a) if (p&1) ans *= a;
return ans; }
friend mint inv(const mint& a) { //assert(a.v != 0);
return mpow(a,MOD-2); }
mint operator-() const { return mint(-v); }
mint& operator++() { return *this += 1; }
mint& operator--() { return *this -= 1; }
friend mint operator+(mint a, const mint& b) { return a += b; }
friend mint operator-(mint a, const mint& b) { return a -= b; }
friend mint operator*(mint a, const mint& b) { return a *= b; }
friend mint operator/(mint a, const mint& b) { return a /= b; }
};
using mi = mint<MOD,5>; // 5 is primitive root for both common mods
mi choose(mi a, mi b) {
mi ans = 1;
FOR(i,0,b) ans *= (a-i);
FOR(i,1,b+1) {
mi im = i;
ans *= inv(im);
}
return ans;
}
void solve() {
ll n,p,q; cin >> n >> p >> q;
mi pmi = p;
mi qmi = q;
mi pp = pmi * inv(qmi);
mi pp3 = pp * pp * pp;
mi pp5 = pp3 * pp * pp;
mi pp6 = pp5 * pp;
mi ans = 0;
ans += pp3 * choose(n,3);
ans += pp5 * choose(n,2) * (n-2) * (n-3);
ans += pp6 * n * choose(n-1, 2) * choose(n-3,2);
ans += pp6 * choose(n, 3) * choose(n-3, 3);
cout << ans.v << endl;
}
int main() {
//auto start = chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);cin.tie(0);
// ofstream cout("pieaters.out");
// ifstream cin("pieaters.in");
#ifdef DEBUG
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int T; cin >> T;
FOR(tcase,0,T) {
solve();
}
// auto stop = chrono::high_resolution_clock::now();
// auto duration = chrono::duration_cast<chrono::microseconds>(stop - start);
// cout << duration.count() << endl;
//cin.close();
//cout.close();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3560kb
input:
2 3 50 100 7 8 9
output:
125000001 655855196
result:
ok 2 lines
Test #2:
score: 0
Accepted
time: 2453ms
memory: 3396kb
input:
999999 3 1 2 4 1 2 5 1 2 6 1 2 7 1 2 8 1 2 9 1 2 3 1 3 4 1 3 5 1 3 6 1 3 7 1 3 8 1 3 9 1 3 3 2 3 4 2 3 5 2 3 6 2 3 7 2 3 8 2 3 9 2 3 3 1 4 4 1 4 5 1 4 6 1 4 7 1 4 8 1 4 9 1 4 3 2 4 4 2 4 5 2 4 6 2 4 7 2 4 8 2 4 9 2 4 3 3 4 4 3 4 5 3 4 6 3 4 7 3 4 8 3 4 9 3 4 3 1 5 4 1 5 5 1 5 6 1 5 7 1 5 8 1 5 9 1 5...
output:
125000001 875000007 343750006 250000013 781250035 250000070 562500147 370370373 975308649 251028809 2743486 920438968 813443087 563786029 962962970 654320995 646090553 323731188 895747739 406035992 748971902 140625001 417968753 718261724 208984377 86425783 679687507 911132823 125000001 875000007 343...
result:
ok 999999 lines
Test #3:
score: 0
Accepted
time: 2516ms
memory: 3420kb
input:
1000000 1000000 999999 1000000 999999 999999 1000000 999998 999999 1000000 999997 999999 1000000 999996 999999 1000000 999995 999999 1000000 999994 999999 1000000 1000000 999998 1000000 999999 999998 1000000 999998 999998 1000000 999997 999998 1000000 999996 999998 1000000 999995 999998 1000000 9999...
output:
112253835 701761079 349518786 868366206 252126467 178242672 778060341 80518498 444381291 491596475 447249465 709569221 611034113 421880396 989494981 128189446 236409900 737936440 850457457 732652878 298538080 105292233 451862471 551350495 763135644 109062607 585000938 211657268 878389934 612625293 2...
result:
ok 1000000 lines
Test #4:
score: 0
Accepted
time: 2514ms
memory: 3408kb
input:
999999 580338 567570 771599 849374 254320 648710 294247 519647 778129 175578 37558 43641 930792 232247 973689 311595 254460 479336 771543 695991 790279 926261 242587 318913 497711 478909 488229 695166 545903 900437 839170 503654 510553 411035 643411 988558 158734 658081 853134 868826 118499 657149 1...
output:
682373032 350605083 926364233 226482485 528609609 289243086 326392175 299790923 759233583 570263274 244353989 216506553 703899770 882129831 441069452 435589640 743423747 704378839 71519676 606228874 260893259 530635798 578864442 448024625 155124544 439009149 794249639 432767462 657395511 620995593 9...
result:
ok 999999 lines
Test #5:
score: 0
Accepted
time: 2497ms
memory: 3408kb
input:
1000000 810898 197872 351928 639903 364602 480613 535419 639396 779039 911443 220061 255224 326056 260332 290774 968889 55593 801771 744090 435131 476495 462818 1826 992667 851307 93466 252170 847306 121145 757666 149951 59429 770060 341104 710636 998232 91826 265767 670814 220739 18766 305224 63530...
output:
200502342 551061024 175009435 625737104 946301341 999717039 924047115 673162328 407174920 434418276 348871683 499270751 722901487 741638468 144487827 571460742 248756068 489560390 489873990 33799994 61365587 211599177 491798047 457731423 82125740 126966275 277601188 4263598 412467126 748869963 26184...
result:
ok 1000000 lines