読者です 読者をやめる 読者になる 読者になる

メモ

yukicoderで遊んでいる競プロゆるふわ勢

yukicoder No.287 場合の数

問題はこちら
No.287 場合の数 - yukicoder

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

各変数をN-a,N-b,...と置き換えることにより、1つ目の条件式はa+...+h=2Nとしてよい
これを満たすようなa~hの組み合わせの個数は、重複組合せで表され_{2N} H _8通り
1つ目の条件を満たすものの中で2つ目以降の条件式0≦a≦N,…,0≦h≦Nを満たさないものを考える
そのような組は、a~hの中でNを超えるものがただ1つ存在することと同値
a>Nと仮定する
a=N+kとおくと、残りの7変数はb+…+h=N-kなので先程と同様に_{n-k}H_7通り
b>Nなどのケースも同様なので、このようなものは全部で8 \sum_{k=1}^{n} {_{n-k}H_7}通り
よって、元の問題の答えは_{2N} H _8 -8 \sum_{k=1}^{n} {_{n-k}H_7}となる
手計算で展開してもよいが、流石に分数混じりの7次式は自信がないのでwolframalfaに投げて
(15N^7+203N^6+1113N^5+3185N^4+5145N^3+4802N^2+2547N+630)/630 という式を得る
第2項の計算第1項-第2項の計算。一度にまとめては計算出来ないようだ)

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