本番えらく場合分けに手間取っている。
https://codeforces.com/contest/1768/problem/E
問題
1～3Nの順列Pにおいて、f(P)は以下の手順を任意の順で繰り返して、Pが昇順になる最小回数とする。
- 先頭2N要素を昇順に並べ替える
- 末尾2N要素を昇順に並べ替える
Pは(3N)!通りあるが、それらのf(P)の和をもとめよ。
解法
f(P)の最大値は3である。
よって、f(P)=0,1,2となるケースを数え上げよう。
- f(P)=0となるPは1通り
- f(P)=1となるPは、先頭・末尾いずれかを指定するとソートできるケースから、どちらでもソートできるケースを引こう。
- f(P)=2となるPは、先頭→末尾の順または末尾→先頭の順でソートできるケースから、どちらの順でもソートできるケースや、f(P)=0,f(P)=1となるケースを引こう。
- どちらの順でもソートできるのは、後半N要素に来るべきものが先頭2N要素になく、その逆も真のケースである。この時、後半N要素に来るべき要素が、真ん中N要素に何個来ているか総当たりしよう。
ll N,mo; const int NUM_=7000003; static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1]; ll comb(ll N_, ll C_) { if(C_<0 || C_>N_) return 0; return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo; } void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>mo; inv[1]=fact[0]=factr[0]=1; for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo; for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo; ll C[4]={}; //0手 C[0]=1; //1手 //どちらでも良い C[1]=fact[N]-1; //前半でないとだめ C[1]+=fact[2*N]-fact[N]; //後半でないとだめ C[1]+=fact[2*N]-fact[N]; C[1]=(C[1]%mo+mo)%mo; //2手 //前→後ろ //先頭N個に後半N個が1個以上あり、後半個に先頭N個がない //後半個に先頭N個がない C[2]+=2*comb(2*N,N)*fact[N]%mo*fact[2*N]%mo; //どっちでもいいケース //後半のものが前半になく、前半のものが後半にない //後半のものが真ん中に来る数を数える FOR(i,N+1) { ll a=comb(N,i); //真ん中に送る後半のN個を選ぶ ll b=comb(N,i); //後ろに送る真ん中のN個を選ぶ ll c=comb(N,i)*fact[i]%mo; //真ん中中の位置と並び ll d=fact[N]; //後ろN個の並び ll e=fact[2*N-i]; //前と後ろの残りのケース (C[2]-=a*b%mo*c%mo*d%mo*e%mo)%=mo; } //1手のケースを戻す C[2]-=C[0]; C[2]-=C[1]; C[2]=(C[2]%mo+mo)%mo; //3手 C[3]=fact[3*N]-C[0]-C[1]-C[2]; ll ret=0; FOR(i,4) ret+=i*C[i]; cout<<(ret%mo+mo)%mo<<endl; }
まとめ
悪くはない場合分けだと思うけど、もっと簡単に書けたりするのかな。
