また変わった問題。
https://codeforces.com/contest/2264/problem/F
問題
変数nの値が与えられたとき、以下の要素を組み合わせ、n=1~50に対する完全順列の個数を求める単一の数式を構成せよ
- 変数n
- 四則演算
- 括弧
- 小数点以下四捨五入
解法
順列が完全順列となる確率は1/eらしい。
ということで、求めるのはround(n!/e)である。
n!とeの構成法を考える。
- 正整数は、(n+n+n+n)/n=4のようにnを繰り返してnで割れば構成できる。
- n!は、(1*(n≧2)+1)*(2*(n≧3)+1)* ... ((k-1)*(n≧k)+1) ... * (49*(n≧50)+1)が計算できればよい。
- n≧xは、round(n/(n+x))で表現できる。nがx以上なら1になり、x未満なら0になるため。
- eは2+1/2*(1+1/3*(1+1/4*(....)))と連分数で表現できる。
string getN(int n) { if(n==1) return "n/n"; string ret="(n"; while(--n>=1) ret+="+n"; return ret+")/n"; } string revN(int n) { if(n==1) return "n/n"; string ret="(n"; while(--n>=1) ret+="+n"; return "n/"+ret+")"; } string ge(int v) { return "round(n/(n+"+getN(v)+"))"; } void solve() { int i,j,k,l,r,x,y; string s; string F=getN(1); for(i=2;i<=50;i++) F+="*(n/n+"+ge(i)+"*"+getN(i-1)+")"; string E=getN(1); for(i=50;i>=1;i--) E="n/n+"+revN(i)+"*("+E+")"; string ret="round("+F+"/("+E+"))"; cout<<ret<<endl; }
まとめ
この完全順列の確率をそもそも知らなかった。