PKU 1349 Coding of Permutations
http://poj.org/problem?id=1349
n個の数字の並びが与えられるので、辞書順最小から何番目の順列かを答えろというような問題。
多倍長を引っ張って来ました。
全然関係ないですが、<>記号を使うと時々emacsのインデントが崩れるのが悲しいです。なんか解決方法ってないんでしょうかね。
string ret; string add(const string&a,const string&b){ ret.clear(); int as=a.size(),bs=b.size(); int c=0; rep(i,max(as,bs)){ int t=c; if(i<as)t+=a[as-i-1]-'0'; if(i<bs)t+=b[bs-i-1]-'0'; c=t/10; t%=10; ret+=t+'0'; } if(c)ret+=c+'0'; reverse(ALL(ret)); return ret; } string mulcret; string multc(char m,const string&a){ m-='0'; mulcret.clear(); int c=0; int as=a.size(); rep(i,as){ int t=c+m*(a[as-i-1]-'0'); c=t/10; t%=10; mulcret+=t+'0'; } if(c)mulcret+=c+'0'; reverse(ALL(mulcret)); return mulcret; } string mulret; string mult(const string&a,string b){ mulret.clear(); int as=a.size(); rep(i,as){ mulret=add(mulret,multc(a[as-i-1],b)); b+='0'; } return mulret; } string in; vector<string> ans; string itos(int n){ stringstream ss; ss<<n; return ss.str(); } string fact(int n){ if(n<=0)return "1"; return mult(itos(n),fact(n-1)); } void solve(){ FOR(it,in)if(!isdigit(*it))*it=' '; stringstream ss(in); int n; ss>>n; vector<int> num; int t; while(ss>>t)num.pb(t); string re="1"; rep(i,n){ string f=fact(n-i-1); string ad="0"; for(int j=i+1;j<n;++j) if(num[i] > num[j])ad=add(ad,"1"); re=add(re,mult(ad,f)); } ans.pb(re); } main(){ while(getline(cin,in),in!="-1")solve(); rep(i,SZ(ans)){ if(i)cout<<','; cout<<ans[i]; } cout<<endl; }