メモ

yukicoderでゆるふわgolf

yukicoder No.420 mod2漸化式

問題はこちら
No.420 mod2漸化式 - yukicoder

/2と%2が並んでいるところを見るといかにも2進法っぽい。
ということで、2進法化した数をfに放り込んだところを想像すると、結局fはbitpop数を数える関数であることが分かる
・個数
0bit目から30bit目までのどのbitを立てるかを考えれば{}_{31}C_xであることは明らか
・総和
x=0のとき0。x≧1を仮定する。
30bit目が立っているような数がいくつあるか考える。
全体でx個の1が立っているためには、30bit目以外の部分でx-1個の1が必要。つまり{}_{30}C_{x-1}
ということで、「30bit目に関してのみ和を取れば」2^{30}*{}_{30}C_{x-1}となる。
対称性から同様に「i bit目に関してのみの和」は2^i*{}_{30}C_{x-1}となるので、求めるべき総和は
\sum_{i=0}^{30}2^i*{}_{30}C_{x-1}=(2^{31}-1)*{}_{30}C_{x-1}

二項係数の計算は漸化式{}_NC_i={}_NC_{i-1}*\frac{N+1-i}{i}ですれば良い

long choose(int n,int r){
	if(r>n||r<0)return 0;
	int i;
	long s=1;
	for(i=1;i<=r;i++)s=s*(n+1-i)/i;
	return s;
}
int main(){
	int x;
	scanf("%d",&x);
	printf("%ld %ld",choose(31,x),choose(30,x-1)*0x7FFFFFFF);
	return 0;
}

この漸化式で計算すればx>Nに対し{}_NC_x=0となる……のだけど、今回はxが大きいのでちゃんと適当な所で計算を打ち切らないといけない
{}_{30}C_{x-1}={}_{31}C_x*\frac{x}{31}
を利用しつつ、あとはintがオーバーフローしないように適当に気をつけると完成

i,x;
main(n){
	for(scanf("%d",&x);n&&i++<x;n=n*(32L-i)/i);
	i=!printf("%d %ld",n,n*1L*x/31*0x7FFFFFFF);
}

99B