保存されている過去のバージョンの一覧

2014年05月18日19時09分36秒

AtCoder Regular Contest #023 C問題 - タコヤ木

Source

AtCoder Regular Contest #023
問題文

問題概要

$N$ 要素の数列 $\{A_{k}\}_{k=1}^N$ が与えられる．
$A_k = -1$ となる要素 $A_k$ を正整数に置き換えることで，何通りの非減少数列が得られるかを ${\rm mod}\ 1000000007\ (10^9+7)$ 求める問題．
作れる非減少列の数は $1$ 個以上であることが保証されている．

解法

$A_k = -1$ となる連続する部分の割り当て方を別々に求めて，後で積を取れば良い．
各部分では，$a \leq A_1 \leq A_2 \leq \cdots \leq A_k \leq b$ なる $A_k$ の割り当て方のパターン数を求めれば良い．
これは，$B_i = A_i+i$ と置き換えて考えれば，$c \leq B_1 < B_2 < \cdots < B_k \leq d$ と同値になるように書けるので，コンビネーション（二項係数）を求めれば良いことになる．
${\rm mod}\ p$ での逆元（例えば $x^{-1} = x^{p-2}$）を用いて計算すれば $O(N)$ か $O(N \log M), \;\; M=10^9+7$ 程度．

C++によるスパゲッティなソースコード

#include<bits/stdc++.h>
using namespace std;

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)

#define ll long long
#define M 1000000007

void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void writer(int x, char c){int i,sz=0,m=0;char buf[10];if(x<0)m=1,x=-x;while(x)buf[sz++]=x%10,x/=10;if(!sz)buf[sz++]=0;if(m)mypc('-');while(sz--)mypc(buf[sz]+'0');mypc(c);}
template<class T> void getInverseList(int n, T res[], int p){int i;res[1]=1;REP(i,2,n)res[i]=p-((ll)(p/i)*res[p%i]%p);}

int N, A[2222];
int S[2222], D[2222], ss;
int inv[2222];

ll solve(int s, int m){
  int i;
  ll res = 1;
  rep(i,m){
    res = (res * (s+i))%M;
    res = (res * inv[i+1])%M;
  }
  return res;
}

int main(){
  int i, j, k;
  ll res = 1;

  reader(&N);
  rep(i,N) reader(A+i);

  getInverseList(N+2, inv, M);

  ss = 0;
  rep(i,N) if(A[i]!=-1) S[ss]=A[i], D[ss]=i, ss++;
  REP(i,1,ss) res = (res * solve(S[i]-S[i-1]+1, D[i]-D[i-1]-1)) % M;

  writer((int)res, '\n');

  return 0;
}

Current time: 2024年04月25日20時39分12秒
Last modified: 2014年05月18日19時09分36秒 (by laycrs)
Tags: Competitive_Programming AtCoder AtCoder_Regular_Contest ARC023 ARC_C
トップページに戻る

Logged in as: unknown user (not login)

ログイン：