yukicoder No.287 場合の数

意図としてはDPなのだろうけど、数学的考察により一発で求められる

各変数をN-a,N-b,...と置き換えることにより、1つ目の条件式はa+...+h=2Nとしてよい
2つ目以降の条件を忘れて、a+...+h=2Nを満たすようなa～hの組み合わせの個数を考えると、これは重複組合せで表され $_{2N} H _8$ 通り
このうち2つ目以降の条件式0≦a≦N,…,0≦h≦Nを満たさないものを考える
そのような組は、a～hの中でNを超えるものがただ1つ存在することと同値
その変数をから予めN+1を引けばa+...+h=N-1となるようにすることと同じになるので、このようなものは全部で $8 {}_{N-1} H_8$ 通り
よって、元の問題の答えは $_{2N} H _8 -8 {}_{N-1} H_8$ となる
手計算で展開してもよいが、流石に分数混じりの7次式は自信がないのでwolframalphaに投げて
(15N^7+203N^6+1113N^5+3185N^4+5145N^3+4802N^2+2547N+630)/630　という式を得る

N≦100なので7乗しても10^14であり64bitなら余裕

int main(){
	long n;
	scanf("%ld",&n);
	printf("%ld",(((((((15*n+203)*n+1113)*n+3185)*n+5145)*n+4802)*n+2547)*n+630)/630);
	return 0;
}

Cには冪乗が無いので計算式の部分をどうにか工夫しないといけないのだけど…
与式は定数項が1なので、n+1をkと置換すれば定数項は消えそう
再びwolframalphaにポイして　(15k^6+98k^5+210k^4+140k^3+77k+90)k/630　という式を得る。
運良くに3次の項も消えたらしい。
あとはこの式を短くなるように睨んで

long n;main(){n=scanf("%d",&n)>printf("%ld",(((((15*++n+98)*n+210)*n+140)*n*n+77)*n+90)*n/630);}

96B

2019/07/07追記
答えの式をぐっと睨むと、N+1,N+2,N+3を因数に持つことがわかる。
そこで残った4次式の係数がうまく小さくなるように考えると、N+3をKとしたとき 15K^4-67K^3+63K^2+43K+3 となるのが良さそうだとわかる。
さらにnがlongでなくても良いという当たり前の事実を加えて大幅な短縮に成功！

main(n){scanf("%d",&n);printf("%ld",++n*++n*++n*((((15L*n-67)*n+63)*n+43)*n+3)/630);}

85B

メモ

yukicoderでゆるふわgolf

yukicoder No.287 場合の数