QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#103366#5010. Squaring the TrianglejoesmittyAC ✓2516ms3560kbC++204.5kb2023-05-05 14:37:082023-05-05 14:37:11

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-05 14:37:11]
  • 评测
  • 测评结果:AC
  • 用时:2516ms
  • 内存:3560kb
  • [2023-05-05 14:37:08]
  • 提交

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