【LuoguP3266】[JLOI2015]騙我呢

題目連結

題目描述

(懶得寫了,見原題)

Sol

一個很神仙的組合問題

稍微模拟就可以發現一個事實,當上一行選擇了删去 x x x,後下一行可選的數是 [ x − 1 , m ] [x-1,m] [x−1,m]

是以dp也就是一個不斷求字首和并加上後一個的過程: f [ i ] [ j ] = ∑ k = 0 j + 1 f [ i − 1 ] [ k ] f[i][j]=\sum_{k=0}^{j+1}f[i-1][k] f[i][j]=∑k=0j+1​f[i−1][k]

之後再往這方面想就比較難有收獲了，我們轉換一下模型,這個顯然類似一個格路問題,隻不過允許在某個地方至多一次向下走一格,這樣的東西就很不好求。

是以我們必須要把這樣的東西轉換一下 (無圖,以下純屬瞎BB) ，我們畫出一個dp的轉移DAG圖,容易發現其中有一些斜着的邊,那麼我們把斜着的邊給扯直了,這樣所有邊都在網格上,發現這時我們不能經過兩條直線

于是問題轉化為求 ( 0 , 0 ) (0,0) (0,0)到 ( n + m , n ) (n+m,n) (n+m,n)的格路數并且不經過 y = x + 2 y=x+2 y=x+2和 y = x − m − 1 y=x-m-1 y=x−m−1兩條直線

然後就很神仙了,容斥計算

答案=總方案 − - − 第一個經過了 y = x + 2 y=x+2 y=x+2的 − - − 第一個經過了 y = x − m − 1 y=x-m-1 y=x−m−1的

考慮怎麼求出經過一條直線的方案，常用思想把終點關于該直線對稱,這樣每一條到這個對稱後的終點的路徑都對應了一條不合法路徑

但是說起來簡單實際寫起來卻比較難了解，每次需要遞歸翻折才能求出以某個直線開頭的方案(其實我也不會啊 TAT ， 哪位大佬會的教教我為什麼要這麼做)

代碼:

#include<bits/stdc++.h>
using namespace std;
#define Set(a,b) memset(a,b,sizeof(a))
const int mod=1e9+7;
int n,m;
typedef long long ll;
template<class T>inline void Inc(T&x,int y){x+=y;if(x>=mod) x-=mod;return;}
template<class T>inline void Dec(T&x,int y){x-=y;if(x <  0) x+=mod;return;}
template<class T>inline int fpow(int x,T k){int ret=1;for(;k;k>>=1,x=(ll)x*x%mod)if(k&1) ret=(ll)ret*x%mod;return ret;}
namespace Sol{
    const int N=3e6+1;
    int fac[N],finv[N];
    inline int C(int n,int m){return n<m? 0:(ll)fac[n]*finv[m]%mod*finv[n-m]%mod;}
    inline void Sieve(){
        fac[0]=finv[0]=1;
        for(int i=1;i<N;++i) fac[i]=(ll)fac[i-1]*i%mod;
        finv[N-1]=fpow(fac[N-1],mod-2);
        for(int i=N-2;i;--i) finv[i]=(ll)finv[i+1]*(i+1)%mod;
        return;
    }
    inline void Flip(ll&x,ll&y,ll c){ll dt=x+c-y;x=x-dt;y=y+dt;return;}
    void work(){
        Sieve();
        int ans=C(m+(n<<1),n);
        ll x,y,op;
        x=n+m,y=n;op=-1;
        while(233) {
            op==1? Flip(x,y,2):Flip(x,y,-1-m);
            if(x<0||y<0) break;
            op==1? Inc(ans,C(x+y,x)):Dec(ans,C(x+y,x));
            op=-op;
        }
        x=n+m,y=n,op=-1;
        while(233){
            op==1? Flip(x,y,-1-m):Flip(x,y,2);
            if(x<0||y<0) break;
            op==1? Inc(ans,C(x+y,x)):Dec(ans,C(x+y,x));
            op=-op;
        }
        cout<<ans<<endl;
    }
}
int main()
{
    cin>>n>>m;
    Sol::work();
    return 0;
}