Codeforces Round #663 (Div. 2) C

題意：給定一個數n，構造一個數組包含1到n這n個數，其中每一個數ai兩側最近的大於ai的數與ai相連，使這個序列中出現環。問可能的序列多少種。
　　想到了可以構造最小的環即三個數且兩大夾一小，然後通過排列組合計數，但很難或者說不能做出來。其實自己做題時如果能夠儘快找到爲什麼得不出來或許也就能夠想到反過來考慮了。其實這個題目做法是先算出全部的排列然後減去不符合條件的（這個好找）,不符合條件即嚴格不會出現兩大夾一小情況，由大到小除了最大的數外每個數都可以在最大的數（或者說比它大的數構成的序列）左邊或右邊，所以是2^n-1種。答案即n - 2 ^ ( n - 1 )。
　　其實都不想亮程式碼了，因爲程式碼不需要水平而我寫的也完全沒什麼水平，不過還是加上完整。

#include<iostream>
#include<iomanip>
#include<fstream>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
#include<cstdio>
#include<map>
#include<queue>
#include<vector>
#include<utility>
#include<ostream>
#include<istream>
typedef long long ll;
using namespace std;
const ll mod=1e9+7;
#define PI acos(-1.0)
const ll maxn=1*1e6;
const int mx=(1<<20)+99;
ll n,m,x,ans,aans,flag,sybl,cc,aa;
int main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    //int t;
    //cin>>t;
    //for(int o=1;o<=t;++o)
    //{
        cin>>n;
        aa=1;
        for(int i=1;i<=n-1;i++)
        {
            aa*=2;
            aa%=mod;
        }
        ans=1;
        for(int i=1;i<=n;i++)
        {
            ans*=i;
            ans%=mod;
        }
        cout<<((ans>=aa?ans:ans+mod)-aa)%mod<<endl;
    //}
    //return 0;
}

總結：
　　這樣說着好像題目很簡單，當然講真的這個題也沒那麼難，不過確實不看題解不知道怎麼做。當一個問題正向或者求一個問題的區域性很難解很複雜時，可以反過來考慮或者是這裏的全域性減去恰好相反的，總之還是一種相反的。這一思路大部分都知道，甚至絕對是高中排列組合最基本的東西之一，但真到了用的時候（不再是排列組合那一套，但仍可能帶着排列組合的神）還是倆字「不會」啊。對於這個題究其原因兩點：這方面的知識沒有過專門的複習和相應的訓練，題目不敏感知識有遺忘。更重要的是，這種反向思考的能力沒有培養起來，即使是其它演算法的講解中老師也強調過這個的，但講的時候明白都懂，做的時候想不到，看了題解又恍然對啊這個題就這樣。所以，這個補題與其說補這個題倒不如說補這個思維方式，這個能力的養成更重要，而方法就是多做題多吃虧，吃多了就記住什麼味道了。