結果

問題 No.612 Move on grid
ユーザー 夕叢霧香(ゆうむらきりか)夕叢霧香(ゆうむらきりか)
提出日時 2017-12-12 10:36:57
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 995 ms / 2,500 ms
コード長 2,268 bytes
コンパイル時間 1,441 ms
コンパイル使用メモリ 71,732 KB
実行使用メモリ 7,512 KB
最終ジャッジ日時 2023-08-22 22:13:45
合計ジャッジ時間 10,081 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 3 ms
4,380 KB
testcase_02 AC 3 ms
4,376 KB
testcase_03 AC 17 ms
4,376 KB
testcase_04 AC 993 ms
7,320 KB
testcase_05 AC 995 ms
7,320 KB
testcase_06 AC 989 ms
7,292 KB
testcase_07 AC 992 ms
7,296 KB
testcase_08 AC 779 ms
7,300 KB
testcase_09 AC 12 ms
7,512 KB
testcase_10 AC 187 ms
5,956 KB
testcase_11 AC 17 ms
4,508 KB
testcase_12 AC 352 ms
6,312 KB
testcase_13 AC 45 ms
4,944 KB
testcase_14 AC 610 ms
6,788 KB
testcase_15 AC 13 ms
4,524 KB
testcase_16 AC 559 ms
7,400 KB
testcase_17 AC 85 ms
5,048 KB
testcase_18 AC 469 ms
6,924 KB
testcase_19 AC 318 ms
6,120 KB
testcase_20 AC 742 ms
7,152 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
typedef long long lint;
typedef vector<int>vi;
typedef pair<int,int>pii;
#define rep(i,n)for(int i=0;i<int(n);++i)

const lint MOD=1000000007;
const int N=2000;
lint fact[N];
lint invfact[N];

static lint powerMod(lint x, lint exponent) {
  lint prod = 1;
  for (int i = 63; i >= 0; --i) {
    prod = (prod * prod) % MOD;
    if ((exponent & 1L << i) != 0) {
      prod = (prod * x) % MOD;
    }
  }
  return prod;
}
static void initialize() {
  fact[0] = invfact[0] = 1;
  for (int i = 1; i < N; ++i) {
    fact[i] = (i * fact[i - 1]) % MOD;
    invfact[i] = powerMod(fact[i], MOD - 2);
  }
}
static lint comb(int x, int y) {
  if (x < 0) {
    return 0;
  }
  if (y < 0 || y > x) {
    return 0;
  }
  lint r= fact[x] * ((invfact[x - y] * invfact[y]) % MOD) % MOD;
  return r;
}

const int T=501;
lint prec[T+1][2*T+2];

int main(){
  int t;
  cin>>t;
  int a[3];
  for(int i=0;i<3;++i)cin>>a[i];
  int d,e;
  cin>>d>>e;
  if(a[2]<0){
    for(int i=0;i<3;++i)a[i]=-a[i];
    int tmp=d;
    d=-e;
    e=-tmp;
  }
  initialize();
  for(int i=0;i<=t;++i){
    for(int z=-t;z<=t;++z){
      int az=abs(z);
      if((az+i)%2!=0)continue;
      int j=(i-z)/2;
      prec[i][z+t+1]=j>=0&&j+z>=0?invfact[j]*invfact[j+z]%MOD:0;
    }
    for(int j=0;j<2*t+1;++j)
      prec[i][j+1]=(prec[i][j+1]+prec[i][j])%MOD;
  }
  long wa=0;
  for(int x=-t;x<=t;++x){
    int ax=abs(x);
    int tx=t-ax;
    for(int y=-tx;y<=tx;++y){
      int ay=abs(y);
      int ty=tx-ay;
      int zMin=-ty,zMax=ty;
      if(a[2]!=0){
	zMin=max(zMin,(d-a[0]*x-a[1]*y+100000*a[2]+a[2]-1)/a[2]-100000);
	zMax=min(zMax,(e-a[0]*x-a[1]*y+100000*a[2])/a[2]-100000);
      }else if(d-a[0]*x-a[1]*y>0||e-a[0]*x-a[1]*y<0)
	continue;
      if(zMin>zMax)continue;
      //System.err.println("x = "+x+" y = "+y);
      //System.err.println("zMin = "+zMin+" zMax = "+zMax);
      //System.err.println(Arrays.toString(d2));
      long tmp=0;
      for(int i=ax+ay;i<=t;i+=2){
	long adden=prec[t-i][t+zMax+1]-prec[t-i][t+zMin]+MOD;
	adden%=MOD;
	long d2=comb(i,(i-ax-ay)/2)*comb(i,(i-ax+ay)/2)%MOD;
	d2=d2*invfact[i]%MOD;
	adden=adden*d2%MOD;
	tmp=(tmp+adden)%MOD;
      }
      wa=(wa+tmp)%MOD;
    }
  }
  cout<<wa*fact[t]%MOD<<endl;
}
0