Submission #19337

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
19337	2016-02-24T10:07:40 Z	gs14004	Ω (kriii4_P3)	C++14	100 / 100	5 ms	1808 KB

P3

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <limits.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <numeric>
#include <deque>
#include <utility>
#include <bitset>
#include <assert.h>
#include <iostream>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;
const int mod = 1e9 + 7;

lint arr[105][105];
int n;

lint ipow(lint x, lint p){
    lint ret = 1, piv = x % mod;
    while(p){
        if(p&1) ret *= piv;
        piv *= piv;
        ret %= mod;
        piv %= mod;
        p >>= 1;
    }
    return ret;
}
 
vector<lint> gauss_jordan(vector<int> &x){ // solve Ax = B. thanks to 프로그래밍 콘테스트 챌린징
	for(int i=0; i<n; i++) arr[i][n] = x[i];
	for(int i=0; i<n; i++){
		int piv = i;
		for(int j=i; j<n; j++){
			if(abs(arr[j][i]) > abs(arr[piv][i])){
				piv = j;
			}
		}
		swap(x[i], x[piv]);
		if(abs(arr[i][i]) == 0){
			while(1);
		}
		for(int j=i+1; j<=n; j++){
			arr[i][j] = (arr[i][j] * ipow(arr[i][i], mod - 2)) % mod;
		}
		for(int j=0; j<n; j++){
			if(i != j){
				for(int k=i+1; k<=n; k++){
					arr[j][k] += mod - arr[j][i] * arr[i][k] % mod;
					arr[j][k] %= mod;
				}
			}
		}
	}
	vector<lint> ret;
	for(int i=0; i<n; i++) ret.push_back(arr[i][n]);
	return ret;
}

int main(){
	int p, q, k;
	cin >> p >> q >> n >> k;
	vector<int> v(n+1);
	v[n] = 1;
	arr[0][0] = arr[n][n] = 1;
	for(int i=1; i<n; i++){
		arr[i][i-1] = q;
		arr[i][i] = mod-p;
		arr[i][i+1] = p-q;
	}
	n++;
	vector<lint> ret = gauss_jordan(v);
	printf("%lld",ret[k]);
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	1808 KB	Output is correct
2	Correct	0 ms	1808 KB	Output is correct
3	Correct	5 ms	1808 KB	Output is correct
4	Correct	4 ms	1808 KB	Output is correct
5	Correct	3 ms	1808 KB	Output is correct
6	Correct	0 ms	1808 KB	Output is correct
7	Correct	0 ms	1808 KB	Output is correct
8	Correct	0 ms	1808 KB	Output is correct
9	Correct	0 ms	1808 KB	Output is correct
10	Correct	0 ms	1808 KB	Output is correct
11	Correct	3 ms	1808 KB	Output is correct
12	Correct	0 ms	1808 KB	Output is correct
13	Correct	3 ms	1808 KB	Output is correct
14	Correct	5 ms	1808 KB	Output is correct
15	Correct	0 ms	1808 KB	Output is correct
16	Correct	5 ms	1808 KB	Output is correct
17	Correct	0 ms	1808 KB	Output is correct
18	Correct	5 ms	1808 KB	Output is correct
19	Correct	0 ms	1808 KB	Output is correct
20	Correct	5 ms	1808 KB	Output is correct
21	Correct	0 ms	1808 KB	Output is correct
22	Correct	5 ms	1808 KB	Output is correct
23	Correct	0 ms	1808 KB	Output is correct
24	Correct	0 ms	1808 KB	Output is correct
25	Correct	3 ms	1808 KB	Output is correct
26	Correct	2 ms	1808 KB	Output is correct
27	Correct	0 ms	1808 KB	Output is correct
28	Correct	0 ms	1808 KB	Output is correct
29	Correct	0 ms	1808 KB	Output is correct
30	Correct	5 ms	1808 KB	Output is correct