Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2445-22a2ef47
この記事にトラックバックする(FC2ブログユーザー)

ARC 012 D - Don't worry. Be Together (この記事を編集する[管理者用])

Source

AtCoder Regular Contest #012
問題文

問題概要

$N$ 人の人が,二次元平面上の格子点 $(x_i, y_i)$ にいる.
各ターン,各自が上下左右のいずれかの方向に $1$ だけ進む.
$T$ ターン後に,全員が $(0,0)$ にいるような進み方は何通りあるかを ${\rm modulo}$ で割った余りで求める問題.
$N \leq 100000 = 10^5$
$T \leq 100000 = 10^5$
${\rm modulo} \leq 1000000007 = 10^9 + 7$
部分点もあるが,略.

解法

各人が動く方法のパターン数をかければ良い.
まず,初期位置 $(x_i,y_i)$ と $(0,0)$ までの距離の偶奇が $T$ と一致しないなら $0$.
一致していれば,パターン数は\[ \begin{pmatrix}T \\ (T+x_i-y_i)/2 \end{pmatrix} \begin{pmatrix}T \\ (T+x_i+y_i)/2 \end{pmatrix} \]となることが観察できる.
(証明には,無駄な移動を上下か左右にいくら割り振るかで場合分けして,二項係数の積の和などに持ち込んで,Vandermonde's identityを使う)
${\rm modulo}$が素数の時(部分点にある)は,階乗の値を前計算しておいて,二項係数を求めれば良い.
満点を狙うには,$N$ 人通して累計で,各数字の階乗が何回使われたをメモる.(割り算は $-1$ 回とカウント)
後は,各階乗から,累積和を使って,各整数を何回かければ良いかを,求め,
各整数について,素因数分解したものを前計算しておいて,各素数を何回かければ良いか,まで落とす.
後は,かけていきながら,${\rm modulo}$ で余りを取る.

C言語によるスパゲッティなソースコード
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define ll long long

int getPrime(int n,int p[]){int i,j,n2=n/2;rep(i,n2)p[i]=1;for(i=3;i*i<n;i+=2)if(p[i>>1])for(j=(i*i)>>1;j<n2;j+=i)p[j]=0;j=1;p[0]=2;REP(i,1,n2)if(p[i])p[j++]=i*2+1;return j;}
int p[200000], ps;


ll pw(ll a,ll b, ll md){
  ll r;
  if(!b) return 1;
  r = pw(a,b/2,md);
  r = (r*r)%md;
  if(b%2) r = (r*a)%md;
  return r;
}

int num[200000];
int yaku[200000][20], yaku_size[200000];
ll fact[200000];
ll dame;

void add(int a, int b, int fg){
  fact[a]+=fg;
  fact[b]-=fg;
  fact[a-b]-=fg;
}

void solve(int x, int y, int T, int mod){
  int px, py, amari;

  if(x < 0) x = -x;
  if(y < 0) y = -y;
  if( (x+y)%2 != T%2 ){ dame = 1; return; }
  if( x+y > T){ dame = 1; return; }

  amari = (T - x - y) / 2;
  px = x + amari;
  py = y + amari;

  add(T, px, 1);
  add(T, amari, 1);
}



int main(){
  int i,j,k,l,m;
  int N, T, mod;
  int x, y;
  ll res = 1, tmp;

  ps = getPrime(200000, p);
  rep(i,200000) yaku_size[i] = 0, num[i] = i;
  rep(i,ps){
    for(j=p[i];j<200000;j+=p[i]){
      while(num[j]%p[i]==0){
        num[j] /= p[i];
        yaku[j][yaku_size[j]++] = p[i];
      }
    }
  }

  rep(i,200000) fact[i] = 0;
  dame = 0;

  scanf("%d%d%d",&N,&T,&mod);
  while(N--){
    scanf("%d%d",&x,&y);
    solve(x,y,T,mod);
  }

  if(dame){
    res = 0;
  } else {
    for(i=199998; i>=0; i--) fact[i] += fact[i+1];
    for(i=199999; i>=0; i--) if(yaku_size[i] > 1){
      rep(j,yaku_size[i]) fact[yaku[i][j]] += fact[i];
      fact[i] = 0;
    }
    
    
    REP(i,2,200000){
      res = (res * pw(i,fact[i],mod)) % mod;
/*      if(fact[i]) printf("%d %lld\n",i,fact[i]);*/
    }
  }

  printf("%lld\n",res);

  return 0;
}

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2445-22a2ef47
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。