Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

Beta Round #53 C問題 - Array (この記事を編集する[管理者用])

Source

Codeforces Beta Round #53 C問題
Problem description
Beta Round #53の自分の参加記録

問題概要

nが与えられる.(nは100000以下)
要素数nの数列で,各要素1以上n以下で,単調非減少,または単調非増加なものは何通りあるかmod 1000000007で求める問題.

解法

包除原理より,
 単調非減少の数 + 単調非増加の数 - 単調非減少かつ単調非増加の数
となる.
1項目と2項目は等しく,3項目は自明にn個.
1項目は,どこで増やすかを考えると,重複組合せの数に落ち着く.

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

#define ll long long
#define M 1000000007

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

ll f[210000], fi[210000],res;

int main(){
  int i,j,k,l,m,n;

  f[0]=fi[0]=1;
  REP(i,1,210000){
    f[i] = (f[i-1]*i)%M;
    fi[i] = pw(f[i],M-2);
  }

  while(scanf("%d",&n)==1){
    res = f[2*n-1];
    res = (res * fi[n-1])%M;
    res = (res * fi[n])%M;
    res = (res*2 - n)%M;
    if(res < 0) res += M;
    printf("%d %d\n",n,(int)res);
    if(res<0)break;
  }

  return 0;
}

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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