超初心者が競プロに挑む

初心者からの競プロ練習記録

ABC003D解いてみた

ARCは難しすぎるのでABCからやることにしました。ABC003Dが難しく、満点解答は思いつかなかったので、解答を見ました。包除原理というやつです。
今回のでは、A_1をXY区画の左端にものがない並べ方の集合、A_2をXY区画の右端にものがない並べ方の集合、A_3をXY区画の上端にものがない並べ方の集合、A_4をXY区画の下端にものがない並べ方の集合として包除原理を適用してwikiの通りの公式に代入します。そして下のコードになりました。ちなみにMODが10^9ほどまでになるので、intで途中計算すると解答が合わなくなります。
下記のコードで、from~toを二つ目のコードと置き換えたものが正解のコードです

#include <cstdio>
#include <cstring>
#define MOD (1000000000 + 7)
using namespace std;

class FactorialMOD {
  static const int MAX_N = 1000;
  typedef long long MODINT;
public:
  MODINT facTable[MAX_N+10];
  MODINT invTable[MAX_N+10];

  void generate(int n, MODINT p) {
    memset(facTable, 0, sizeof(facTable));
    memset(invTable, 0, sizeof(invTable));
    facTable[0]=1;
    for(int i=1;i<=n;++i) {
      facTable[i] = (facTable[i-1] * i) % p;
    }

    MODINT power = facTable[n];
    MODINT res = 1;
    MODINT index = p-2;

    for(int i=0;(index>>i) != 0;++i) {
      if( ((index >> i) & 1) == 1) {
        res = (res * power) % p;
      }
      power = (power*power) %p;
    }

    invTable[n] = res;
    for(int i=n;i>=1;--i) {
      invTable[i-1] = (invTable[i] * i) % p;
      if((invTable[i] * facTable[i]) %p != 1) printf("Error");
    }

  }

  MODINT factorial(int n) {
    return facTable[n];
  }

  MODINT inverseFactorial(int n) {
    return invTable[n];
  }
};

FactorialMOD factorialMOD;

long long combination(int n,int r) {
  if(n<r) return 0;
  return (((factorialMOD.factorial(n) % MOD) * factorialMOD.inverseFactorial(r) % MOD) * factorialMOD.inverseFactorial(n-r)) % MOD;
}

int main() {
  int R,C,X,Y,D,L;
  scanf("%d%d%d%d%d%d",&R,&C,&X,&Y,&D,&L);
  factorialMOD.generate(1000, MOD);
  long long temp=combination(X*Y, D+L);
  long long temp1a=(combination((X-1)*Y, D+L) * 2) % MOD;
  long long temp1b=(combination(X*(Y-1), D+L) * 2) % MOD;
  long long temp2a=(combination((X-1)*(Y-1), D+L) * 4) % MOD;
  long long temp2b=combination((X-2)*Y, D+L) % MOD;
  long long temp2c=combination(X*(Y-2), D+L) % MOD;
  long long temp3a=(combination((X-2)*(Y-1), D+L) * 2) % MOD;
  long long temp3b=(combination((X-1)*(Y-2), D+L) * 2) % MOD;
  long long temp4=(combination((X-2)*(Y-2), D+L) ) % MOD;
  long long num = combination(D+L, L);
//--from
  temp = (temp - ((temp1a + temp1b) % MOD - ((temp2a + temp2b) % MOD + temp2c) % MOD + (temp3a + temp3b) % MOD -
                  temp4 % MOD)) % MOD;
//--to
  long long answer = ((((R-X+1) * (C-Y+1) *temp ) % MOD) *num)%MOD;
  printf("%lld\n", (answer + MOD)%MOD);

  return 0;
}

ところが、これだとACにはならない(0点)。正解は上記のコードのfrom~toを下のコードと置き換えたものになります。

  if(X*Y > D+L) {
    temp = (temp - ((temp1a + temp1b) % MOD - ((temp2a + temp2b) % MOD + temp2c) % MOD + (temp3a + temp3b) % MOD -
                    temp4 % MOD)) % MOD;
  }

もしくはこう

  if(X==1 && Y ==1) temp4 = 0;
  temp = (temp - ((temp1a + temp1b) % MOD - ((temp2a + temp2b) % MOD + temp2c) % MOD + (temp3a + temp3b) % MOD -
                  temp4 % MOD)) % MOD;

つまり、X==1でY==1の時の端にものがない場合の数の計算ので、第一引数が-1*-1=1となってしまい{}_1C_1で0にならず場合の数が1減ってしまうのが原因です。これに本番気づく人は相当すごいと思う(*_*)。
教訓:マイナスは本当に気をつける