Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

February 2011 Challenge 3問目 - Counting Terms (この記事を編集する[管理者用])

Source

codechef February 2011 Challenge 3問目
Problem Statement
February 2011 Challengeの参加記録

問題概要

 (x[1] + x[2] + … + x[k])^n mod p
を展開したときの項の数をmod 1000003で求める問題.
k, nは10^15以下,pは100以下.

解法

規則性を探して解いた.
実際に試してみると,nをp進数表示したとき,
 n = (… a[2] a[1] a[0])_p
となったとすれば,答えは
 Comb( k-1+a[0], a[0] ) * Comb( k-1+a[1], a[1] ) * Comb( k-1+a[2], a[2] ) * …
のmod 1000003になることがわかる.
後は,桁ごとに見てやってDPすれば解ける.

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 1000003

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

int p;
ll dp[2][70];
ll in[70];
ll mul[120], len;

ll solve(int fg,int rest){
  int i,j,k;
  ll res=0, add;

  if(dp[fg][rest]>=0) return dp[fg][rest];
  if(rest==0) return dp[fg][rest]=1;

  if(fg){
    rep(i,in[rest-1]){
      add = solve(0,rest-1) * mul[i];
      res = (res+add)%M;
    }
    add = solve(1,rest-1) * mul[i];
    res = (res+add)%M;
  } else {
    rep(i,p){
      add = solve(0,rest-1) * mul[i];
      res = (res+add)%M;
    }
  }

  return dp[fg][rest] = res;
}

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

  scanf("%d",&size);
  while(size--){
    scanf("%lld%lld%d",&n,&k,&p);
    mul[0]=1;
    REP(i,1,p){
      mul[i] = mul[i-1];
      mul[i] *= (k+i-1)%M;     mul[i] %= M;
      mul[i] *= pw(i,M-2); mul[i] %= M;
    }

    len=0;
    while(n) in[len++] = n%p, n/=p;
    rep(k,2) rep(i,len+1) dp[k][i] = -1;
    res = solve(1,len);
    printf("%d\n",(int)res);
  }

  return 0;
}
#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

ll c[60][60][60][60];

char ff[100];

int main(){
  int i,j,k,l,m,n,p;
  ll fact[30], res, cnt, bef;
  ll dp[30][30];
/*
  fact[0]=1; REP(i,1,30) fact[i]=fact[i-1]*i;

  rep(n,12) rep(k,12){
    dp[n][k]=0;
    if(n==0 && k==0) dp[n][k]=1;
    else {
      if(k) rep(i,n+1) dp[n][k] += dp[n-i][k-1];
    }
    
    printf("f(%d,%d) = %lld\n",n,k,dp[n][k]);
  }
*/

  p=5;
  c[0][0][0][0]=1;
  rep(i,60) rep(j,60) rep(k,60) rep(l,60){
    if(i==0 && j==0 && k==0 && l==0) continue;
    c[i][j][k][l]=0;
    if(i) c[i][j][k][l] += c[i-1][j][k][l];
    if(j) c[i][j][k][l] += c[i][j-1][k][l];
    if(k) c[i][j][k][l] += c[i][j][k-1][l];
    if(l) c[i][j][k][l] += c[i][j][k][l-1];
    c[i][j][k][l] %= p;
  }

  bef = 0;
  rep(n,55){
    cnt = 0;
    rep(i,60) rep(j,60) rep(k,60) rep(l,60){
      if(i+j+k+l>n) continue;
      if(c[i][j][k][l]) cnt++;
    }
    k=n; ff[8]='0';
    rep(i,8) ff[7-i]=k%p+'0', k/=p;
    printf("%s %lld\n",ff,cnt-bef); bef=cnt;
  }
  
  return 0;
}

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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