Submission #1832697
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define rept(i,n) for(int (i)=0;(i)<=(int)(n);(i)++)
#define reps(i,s,n) for(int (i)=(s);(i)<(int)(n);(i)++)
#define repst(i,s,n) for(int (i)=(s);(i)<=(int)(n);(i)++)
#define repr(i,n) for(int (i)=(n);(i)>=0;(i)--)
#define each(itr,v) for(auto (itr):(v))
#define all(c) c.begin(),c.end()
#define pb push_back
#define mp(x,y) make_pair((x),(y))
#define fi first
#define se second
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define ln << "\n"
#define show(x) cout << #x << " = " << x ln
#define dbg(x) cout<<#x"="<<x ln
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int inf = (int)1e9;
const ll linf = (ll)1e18;
const int mod = (int)(1e9+7);
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
const int ddx[] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[] = {1, 1, 0, -1, -1, -1, 0, 1};
struct oreno_initializer {
oreno_initializer() {
cin.tie(0);
ios::sync_with_stdio(0);
}
} oreno_initializer;
// ⊂ニニニニニニニニニニニニニ( ^ω^)ニニニニニニニニニニニニニ⊃
unsigned long long a, b, c, R, C, pR[30], pC[30], gR = 1, gC = 1;
int main() {
cin >> a >> b >> c;
/*
* r+c = kとおくと
* a = kCc = k! / c!(k-c)!
* b = (k+1)Cc = (k+1)! / c!(k+1-c)!
* c = (k+1)C(c+1) = (k+1)! / (c+1)!(k-c)!
*
* これらをいい感じに変形していくとCを下のC/pC[0]って形で表せることがわかる
* 変形はこんな感じ↓ 別にこの流れじゃなくてもとにかくK消してC=の形作ればいいだけ
* https://drive.google.com/open?id=1fMwjqFWHoLeyzFxbUE2Qqdg-_ph_h4Id
* あとはフェルマーの小定理X^-1 = X^P-2 (modP, P=1e9+7) と繰り返し2乗法でpR[0], gC[0]の逆元を求めて掛け算する
*/
R = (b*c%mod + mod - a*c%mod) % mod;
C = (b*c%mod + mod - a*b%mod) % mod;
pR[0] = (a*b%mod + mod - b*c%mod + a*c%mod) % mod;
pC[0] = (a*c%mod + mod - b*c%mod + a*b%mod) % mod;
// pR[k]: pR[0]を2^k乗して%=modしたもの 繰り返し2乗法
reps(k,1,30) {
pR[k] = (pR[k-1] * pR[k-1]) % mod;
pC[k] = (pC[k-1] * pC[k-1]) % mod;
}
// ↑のテーブルから逆元を求める
rep(k,30) {
if (((mod-2)>>k)&1) {
gR = (gR * pR[k]) % mod;
gC = (gC * pC[k]) % mod;
}
}
R = (R * gR) % mod;
C = (C * gC) % mod;
cout << R << " " << C ln;
}
Submission Info
Submission Time |
|
Task |
D - 動的計画法 |
User |
creep04 |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
2554 Byte |
Status |
AC |
Exec Time |
2 ms |
Memory |
256 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
100 / 100 |
Status |
|
|
Set Name |
Test Cases |
Sample |
sample_01.txt, sample_02.txt, sample_03.txt |
All |
sample_01.txt, sample_02.txt, sample_03.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt, subtask2_13.txt, subtask2_14.txt, subtask2_15.txt, subtask2_16.txt, subtask2_17.txt, subtask2_18.txt, subtask2_19.txt, subtask2_20.txt, subtask2_21.txt, subtask2_22.txt, subtask2_23.txt, subtask2_24.txt, subtask2_25.txt, subtask2_26.txt, subtask2_27.txt, subtask2_28.txt, subtask2_29.txt, subtask2_30.txt, subtask2_31.txt, subtask2_32.txt, subtask2_33.txt, subtask2_34.txt, subtask2_35.txt, subtask2_36.txt, subtask2_37.txt, subtask2_38.txt, subtask2_39.txt, subtask2_40.txt, subtask2_41.txt, subtask2_42.txt, subtask2_43.txt, subtask2_44.txt, subtask2_45.txt, subtask2_46.txt, subtask2_47.txt, subtask2_48.txt, subtask2_49.txt |
Case Name |
Status |
Exec Time |
Memory |
sample_01.txt |
AC |
2 ms |
256 KB |
sample_02.txt |
AC |
1 ms |
256 KB |
sample_03.txt |
AC |
1 ms |
256 KB |
subtask2_01.txt |
AC |
1 ms |
256 KB |
subtask2_02.txt |
AC |
1 ms |
256 KB |
subtask2_03.txt |
AC |
1 ms |
256 KB |
subtask2_04.txt |
AC |
1 ms |
256 KB |
subtask2_05.txt |
AC |
1 ms |
256 KB |
subtask2_06.txt |
AC |
1 ms |
256 KB |
subtask2_07.txt |
AC |
1 ms |
256 KB |
subtask2_08.txt |
AC |
1 ms |
256 KB |
subtask2_09.txt |
AC |
1 ms |
256 KB |
subtask2_10.txt |
AC |
1 ms |
256 KB |
subtask2_11.txt |
AC |
1 ms |
256 KB |
subtask2_12.txt |
AC |
1 ms |
256 KB |
subtask2_13.txt |
AC |
1 ms |
256 KB |
subtask2_14.txt |
AC |
1 ms |
256 KB |
subtask2_15.txt |
AC |
1 ms |
256 KB |
subtask2_16.txt |
AC |
1 ms |
256 KB |
subtask2_17.txt |
AC |
1 ms |
256 KB |
subtask2_18.txt |
AC |
1 ms |
256 KB |
subtask2_19.txt |
AC |
2 ms |
256 KB |
subtask2_20.txt |
AC |
1 ms |
256 KB |
subtask2_21.txt |
AC |
1 ms |
256 KB |
subtask2_22.txt |
AC |
1 ms |
256 KB |
subtask2_23.txt |
AC |
1 ms |
256 KB |
subtask2_24.txt |
AC |
1 ms |
256 KB |
subtask2_25.txt |
AC |
1 ms |
256 KB |
subtask2_26.txt |
AC |
1 ms |
256 KB |
subtask2_27.txt |
AC |
1 ms |
256 KB |
subtask2_28.txt |
AC |
1 ms |
256 KB |
subtask2_29.txt |
AC |
1 ms |
256 KB |
subtask2_30.txt |
AC |
1 ms |
256 KB |
subtask2_31.txt |
AC |
1 ms |
256 KB |
subtask2_32.txt |
AC |
1 ms |
256 KB |
subtask2_33.txt |
AC |
1 ms |
256 KB |
subtask2_34.txt |
AC |
1 ms |
256 KB |
subtask2_35.txt |
AC |
1 ms |
256 KB |
subtask2_36.txt |
AC |
1 ms |
256 KB |
subtask2_37.txt |
AC |
1 ms |
256 KB |
subtask2_38.txt |
AC |
1 ms |
256 KB |
subtask2_39.txt |
AC |
1 ms |
256 KB |
subtask2_40.txt |
AC |
1 ms |
256 KB |
subtask2_41.txt |
AC |
1 ms |
256 KB |
subtask2_42.txt |
AC |
1 ms |
256 KB |
subtask2_43.txt |
AC |
1 ms |
256 KB |
subtask2_44.txt |
AC |
1 ms |
256 KB |
subtask2_45.txt |
AC |
1 ms |
256 KB |
subtask2_46.txt |
AC |
1 ms |
256 KB |
subtask2_47.txt |
AC |
1 ms |
256 KB |
subtask2_48.txt |
AC |
1 ms |
256 KB |
subtask2_49.txt |
AC |
1 ms |
256 KB |