[TIOJ 1897][IOI 2014] Gondola

原題連結
Day2當中最簡單，也是我唯一有想到的一題orz

這道題分成3個任務：判斷序列合法性，給出任一故障序列，計算故障序列個數，難度也是依序增加的。

關於合法性，先做一些簡單的觀察。
一個難以下手的點是我們不知道序列是從哪裡開始算的，第0個元素到底原本是第幾台車根本不知道。
但是在這個序列當中如果有某個<=n的數字，也就是從沒有壞過的車子，我們就可以藉著他的位置去確定整個觀看序列所對應的車子編號。
還有一些需要判斷的東西（編號重複，所有車都壞過的case......）都並不難想，就不多說了。

要給出任一故障序列，我們需要先將觀看序列用上面的方法定序（若所有車都壞過不妨隨意定序），這樣我們就可以得到有壞掉的位置是哪些以及他們最後分別是哪幾台車。
然後按照壞掉的編號從小到大排序，把位置編號依序填入崩壞序列即可。（細節可以看code)

對於計數，需要對上面構造法有更多的觀察。
我們會發現上面在填入位置編號的過程中，我們直接把「曾經出現但最後沒出現」的新纜車丟給當前處理的位置編號，其實真正的情況是「所有有壞過的位置編號都可以」。
有了這個思考就很好做了，把快速冪函數做出來直接實做就好。

//#define TIOJ
#ifdef TIOJ
#include "lib1897.h"
#else
#include "gondola.h"
#endif

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long LL;
const int INF=(1<<30);
const int maxn=100000+5;
const LL mod=1000000009;
LL tmp[maxn];
vector<pair<LL,LL> >broke;
bool standardize(int n,int seq[])
{
    broke.clear();
    int Min=INF;
    for(int i=0;i<n;i++) if(Min==INF || seq[i]<seq[Min]) Min=i;
    for(int i=Min,p=0;p<n;i=(i==n-1?0:i+1)) tmp[p++]=seq[i];
    for(int i=0;i<n;i++) seq[i]=tmp[i];
    
    int now=seq[0]<=n?seq[0]:1;
    for(int i=0;i<n;i++,now=(now==n?1:now+1)) if(seq[i]>n) // broke
        broke.push_back(pair<int,int>(seq[i],now));
    sort(broke.begin(),broke.end());
         
    if(seq[Min]>n) return 0;
    return 1;
}
int valid(int n,int seq[])
{
    standardize(n,seq);
    for(int i=0;i<broke.size();i++) if(i && broke[i].first==broke[i-1].first) return 0;
    if(broke.size()!=n) for(int i=0;i<n;i++) if(seq[i]<=n && i!=seq[i]-seq[0]) return 0;
    return 1;
}
int replacement(int n,int seq[],int ret[])
{
    standardize(n,seq);
    int now=n+1,p=0;
    for(int i=0;i<broke.size();i++)
    {
        ret[p++]=broke[i].second;
        for(;now<broke[i].first;now++) ret[p++]=now;
        now++;
    }
    return p;
}
LL fast_pow(LL x,LL p) // get x^p
{
    if(p==0) return 1LL;
    LL ret=fast_pow(x,p/2);
    (ret*=ret)%=mod;
    if(p&1) (ret*=x)%=mod;
    return ret;
}
LL fac[maxn];
int countReplacement(int n,int seq[])
{
    if(!valid(n,seq)) return 0;
    LL ans=1,now=n+1,size=broke.size();
    for(int i=0;i<size;i++)
    {
        (ans*=fast_pow((size-i),broke[i].first-now))%=mod;
        now=broke[i].first+1;
    }
    return (ans*(size==n?(LL)n:1LL))%mod;
}