2017「百度の星」プログラムデザインコンテスト-初戦(B)1001 Chess
Chess
Accepts: 175
Submissions: 538
Time Limit: 2000/1000 MS (Java/Others)
Memory Limit: 32768/32768 K (Java/Others)
Problem Description
車は中国将棋の駒の一種で、同じ行や同じ列に他の駒が遮断されていない駒を攻撃することができる.ある日、小度は碁盤の上にたくさんの車を並べました......彼は知りたいと思って、全部でN×M点の長方形の碁盤の中で最も多くの数の車を並べて互いに攻撃しない案数.彼は考えて、答えを得た.しかし、彼はまだ満足していません.どの車Aに対しても、他の車Bがその上にある場合(車Bの行番号が車Aより小さい場合)、車Aは車Bの右側にある必要があります(車Aの列番号が車Bより大きい場合).
今、要求を満たす案の数を聞いてみましょう.
Input
1行目の正の整数Tは、データ群数を表す.
各データのセット:1行に対して、2つの正の整数NとM(N<=1000、M<=1000).
Output
各セットのデータ出力行について、シナリオ数モード100000007(1 e 9+7)を表す.
考え方:各行毎に1つの駒しか置けないため、下の列番号が前より大きいことが要求されます.これは配列の組み合わせの問題になります.大きな数の中から小さい数を選ぶ組み合わせに相当し、答えの個数はC(min(m,n),max(m,n))が1 e 9+7に対して余剰を取ります...明らかに直接計算すると必ず溢れ出します.承徳の過程で余剰を取ればいいのですが、もう一つの問題は(A/B)%Cの転化で、A*B^(1 e 9+5)%Cになることができます(なぜか聞かないでください.私も知りません.ただ覚えています.牛が通りかかったら説明できるのが一番いいです)
Accepts: 175
Submissions: 538
Time Limit: 2000/1000 MS (Java/Others)
Memory Limit: 32768/32768 K (Java/Others)
Problem Description
車は中国将棋の駒の一種で、同じ行や同じ列に他の駒が遮断されていない駒を攻撃することができる.ある日、小度は碁盤の上にたくさんの車を並べました......彼は知りたいと思って、全部でN×M点の長方形の碁盤の中で最も多くの数の車を並べて互いに攻撃しない案数.彼は考えて、答えを得た.しかし、彼はまだ満足していません.どの車Aに対しても、他の車Bがその上にある場合(車Bの行番号が車Aより小さい場合)、車Aは車Bの右側にある必要があります(車Aの列番号が車Bより大きい場合).
今、要求を満たす案の数を聞いてみましょう.
Input
1行目の正の整数Tは、データ群数を表す.
各データのセット:1行に対して、2つの正の整数NとM(N<=1000、M<=1000).
Output
各セットのデータ出力行について、シナリオ数モード100000007(1 e 9+7)を表す.
考え方:各行毎に1つの駒しか置けないため、下の列番号が前より大きいことが要求されます.これは配列の組み合わせの問題になります.大きな数の中から小さい数を選ぶ組み合わせに相当し、答えの個数はC(min(m,n),max(m,n))が1 e 9+7に対して余剰を取ります...明らかに直接計算すると必ず溢れ出します.承徳の過程で余剰を取ればいいのですが、もう一つの問題は(A/B)%Cの転化で、A*B^(1 e 9+5)%Cになることができます(なぜか聞かないでください.私も知りません.ただ覚えています.牛が通りかかったら説明できるのが一番いいです)
/** , LL**/
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long LL;
const LL MOD=1000000007;
LL sum_z,sum_m;
LL Powe(LL a, LL b, LL c) /// ,a b C
{
LL ans = 1;
a = a % c;
while(b>0)
{
if(b % 2 == 1)
ans = (ans * a) % c;
b = b/2;
a = (a * a) % c;
}
return ans;
}
LL solve(LL zi,LL mu)
{
sum_z=sum_m=1;
for(int i=1,j=mu; i<=zi; i++,j--)
{
sum_z=sum_z*i; /// C(m,n)
sum_m=sum_m*j; /// 。
if(sum_m>=MOD) ///
sum_m=sum_m%MOD;
if(sum_z>=MOD)
sum_z=sum_z%MOD;
}
return ((sum_m%MOD)*(Powe(sum_z,MOD-2,MOD)%MOD)%MOD);
}
int main()
{
LL m,n;
int T;
scanf("%d",&T);
while(T--)
{
cin>>m>>n;
cout<