Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

ARC 009 C - 高橋君、24歳 (この記事を編集する[管理者用])

Source

AtCoder Regular Contest #009
問題文

問題概要

要素数Nの置換Sで,S[i]=iとならないものがちょうどK個であるものの数をmod 1,777,777,777 (素数) で求める問題.
N, Kは2以上,8以下で40点.
Nは777,777,777,777,777,777以下,Kは777,777以下で100点.

解法

どの集合がS[i]=iとなってないかを選ぶ方法はC(N, K)で,これはN, N-1, ..., N-K+1をかけて,1, 2, ..., K で割ればよいのでO(K)で求められる.
すべてのiについて,S[i]=iとならない要素数Kの置換の数A[k]は漸化式があって,A[k] = (k-1) * (A[k-1] + A[k-2])などを用いればO(K).

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
#define M 1777777777

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;
}

ll arr[1000000];

int main(){
  int i, j, K;
  ll N, res;

  scanf("%lld%d\n",&N,&K);

  res = 1;
  rep(i,K){
    res = (res * ((N-i)%M)) % M;
    res = (res * pw(i+1, M-2, M)) % M;
  }

  arr[0] = 1; arr[1] = 0; arr[2] = 1; arr[3] = 2;
  REP(i,4,1000000){
    arr[i] = ((i-1) * ((arr[i-1] + arr[i-2])%M))%M;
  }

  res = (res * arr[K])%M;
  printf("%lld\n",res);

  return 0;
}

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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