寝癖頭の解法

勉強中の覚え書きを投稿、更新していきます。

AtCoder Problems in C, C++ #F - Many Many Paths

AtCoder Beginner Contest(ABC)の過去問から、その提出コードの解答例です。
AtCoderとは、コンテストを通じて、プログラミングやアルゴリズムを学習するサービスです。
atcoder.jp
プログラミングコンテストとは、「与えられた問題をいかに素早く、正確に」解くことができるかを競うものです。
競技プログラミング」を略して、「競プロ」などと呼ばれています。

#F - Many Many Paths
atcoder.jp

僕が作成、提出したコードは、以下のとおりです。

/*
AtCoder Problems in C
#F - Many Many Paths
https://atcoder.jp/contests/abc154/tasks/abc154_f
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<stdio.h>
#define MOD 1000000007
long powll(long a, int x){
	if(x==0){
      return 1;
    }
	long b=powll(a,x/2);
	if(x%2==0){
		b=b*b%MOD;
	}else{
		b=b*b%MOD*a%MOD;
	}
	return b;
}
long rec(long a){
	return powll(a,MOD-2);
}
long fact(long a){
	long b=1;
	while(a>0){
		b=b*a%MOD;
		a--;
	}
	return b;
}
long fra_fac(int a,int b){
	return rec(fact(a))*rec(fact(b))%MOD*fact(a+b)%MOD;
}
int main(void){
	int r1,r2,c1,c2;
	scanf("%d %d %d %d",&r1,&c1,&r2,&c2);
	long ans=fra_fac(c2+1,r2+1)+fra_fac(c1,r1)-fra_fac(c2+1,r1)-fra_fac(c1,r2+1)+MOD*2;
    printf("%ld\n",ans%MOD);
    return 0;
}
/*
AtCoder Problems in C++
#F - Many Many Paths
https://atcoder.jp/contests/abc154/tasks/abc154_f
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<stdio.h>
#define MOD 1000000007
long powll(long a, int x){
	if(x==0){
      return 1;
    }
	long b=powll(a,x/2);
	if(x%2==0){
		b=b*b%MOD;
	}else{
		b=b*b%MOD*a%MOD;
	}
	return b;
}
long rec(long a){
	return powll(a,MOD-2);
}
long fact(long a){
	long b=1;
	while(a>0){
		b=b*a%MOD;
		a--;
	}
	return b;
}
long fra_fac(int a,int b){
	return rec(fact(a))*rec(fact(b))%MOD*fact(a+b)%MOD;
}
int main(void){
	int r1,r2,c1,c2;
	scanf("%d %d %d %d",&r1,&c1,&r2,&c2);
	long ans=fra_fac(c2+1,r2+1)+fra_fac(c1,r1)-fra_fac(c2+1,r1)-fra_fac(c1,r2+1)+MOD*2;
    printf("%ld\n",ans%MOD);
    return 0;
}

AtCoder Beginner Contest(ABC)は、オンラインジャッジによるプログラミングコンテストです。
日本語と英語に対応していて、週末ごとに実施されているみたいです。
https://practice.contest.atcoder.jp/tutorial
アカウントを登録すれば、誰でも参加できます。