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
AC × 3
AC × 52
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