yukicoder No.420 mod2漸化式

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

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

二項係数の計算は漸化式ですれば良い

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に対しとなる……のだけど、今回はxが大きいのでちゃんと適当な所で計算を打ち切らないといけない

を利用しつつ、あとは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

2017/07/26追記

n*1L*x/31*0x7FFFFFFF
n*0x7FFFFFFFL*x/31

って書き換えれば2B短縮じゃね？？？
……といいたいところだが、x=16の最大ケースでとなるので駄目
……ではなく、これは2^64未満なのでunsigned longを使えば解決。1B短縮。
コンパイラのバージョンアップによる3Bとあわせて4B短縮

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

95B