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

2015年07月01日06時53分28秒

AtCoder Regular Contest #039 B問題 - 高橋幼稚園

Source

AtCoder Regular Contest #039
問題文

問題概要

$N$ 人の人と，$K$ 個の飴があり，人は区別できるが，飴は区別できない．
あまりがないように飴を人に配りたいが，幸福度を各人がもらった飴の数の積で定義する．
幸福度が最大となるような飴の配り方は何通りあるかを ${\rm mod}\ 1000000007\ (10^9+7)$ で求める問題．

解法

全員に最低 $1$ 個の飴が行き届くかどうかで場合分けを行う．
まず，全員に飴が行き届かない場合，つまり，$K < N$ の場合はどのように配っても幸福度は $0$ にしかならない．
よって，答えは配り方のパターン数であり，それは重複組合せで ${}_N H_K = {}_{N+K-1}C_K$ となる．
$N \geq K$ の場合はできるだけ均等に配ると幸福度が最大となり，それは，全員に $\lfloor K/N \rfloor$ 個ずつ配り，余った $K\ {\rm mod}\ N$ 個を誰に配るか（$1$ 人にはたかだか $1$ 個配る）のパターン数を考えれば良い．
それはコンビネーションで ${}_N C_{K\ {\rm mod}\ N}$ である．
よって，いずれにしても，二項係数を求めればよく，パスカルの三角形を用いて計算すれば時間計算量は $O(N^2)$ 程度で，掛け算や逆元を用いて計算すれば $O(N)$ 程度．

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 ull unsigned ll

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);}
template <class T, class S> void reader(T *x, S *y){reader(x);reader(y);}

void writer(int x, char c){int s=0,m=0;char f[10];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
template<class T> void writerLn(T x){writer(x,'\n');}

int get_inv(ll a, int md){ll t=a,s=md,u=1,v=0,e;while(s){e=t/s;t-=e*s;u-=e*v;swap(t,s);swap(u,v);}if(u<0)u+=md;return u;}
struct combination{
  int *f,*v,m,s;unsigned **d;
  void* init(void *mem, int md, int lim=1100, int small=0){int i,j;m=md;s=small;f=(int*)mem;v=f+lim;d=(unsigned**)(v+lim);d[0]=(unsigned*)(d+s);REP(i,1,s)d[i]=d[i-1]+s;mem=(void*)(d[0]+s*s);if(lim){f[0]=1;REP(i,1,lim)f[i]=(ll)f[i-1]*i%m;v[lim-1]=get_inv(f[lim-1],m);for(i=lim-1;i;i--)v[i-1]=(ll)v[i]*i%m;}REP(i,1,s)d[0][i]=0;rep(i,s)d[i][0]=1;REP(i,1,s)REP(j,1,s){d[i][j]=d[i-1][j-1]+d[i-1][j];if(d[i][j]>=m)d[i][j]-=m;}return mem;}
  ll C(int a, int b){if(b<0||b>a)return 0;if(a<s)return d[a][b];return (ll)f[a]*v[b]%m*v[a-b]%m;}
  ll P(int a, int b){if(b<0||b>a)return 0;return (ll)f[a]*v[a-b]%m;}
  ll H(int a, int b){if(a==0&&b==0)return 1;if(a<=0||b<0)return 0;return C(a+b-1,b);}
};

char memarr[17000000]; void *mem = memarr;
#define MD 1000000007

int N, K;

int main(){
  int res;
  combination comb;

  mem = comb.init(mem, MD);

  reader(&N,&K);
  if(N <= K){
    res = comb.C(N, K%N);
  } else {
    res = comb.H(N, K);
  }

  writerLn((int)res);

  return 0;
}

Current time: 2024年04月19日00時47分28秒
Last modified: 2015年07月01日06時53分28秒 (by laycrs)
Tags: Competitive_Programming AtCoder AtCoder_Regular_Contest ARC039 ARC_B
トップページに戻る

Logged in as: unknown user (not login)

ログイン：