[JLOI2015]骗我呢

[Luogu3266]

神仙题只能看神仙题解

\(dp[i][j]\) 表示第 \(i\) 行没有出现过的数是 \(j\) 的方案数

则\(dp[i][j]=∑_{k=0}^{j+1}dp[i?1][k]\)

优化后为\(dp[i][j]=dp[i?1][j+1]+dp[i][j?1]\)

画图转化为 : 从原点出发，只能向右或向上走，不接触直线\(A,B\)，到达点\((n+m+1,n)\)的路径条数

到\((x,y)\)的不合法的方案为先穿过\(A\)或先穿过\(B\)

先穿过\(A\)的实现方式是 : 把\((x,y)\)沿\(A\)翻折 , 减去答案 ; 将翻折过的点沿\(B\)翻着 , 加上答案 ; 再沿A翻折...

同理计算以 \(B\) 开头的方案，就是先沿 \(B\) 折就好了

具体细节的话沿着 \(A\) 折是 \((x,y)->(y-1,x+1)\) ，沿着 \(B\) 折是 \((x,y)->(y+(m+2),x-(m+2))\)

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define Debug(x) cout<<#x<<"="<<x<<endl
using namespace std;
typedef long long LL;
const int INF=1e9+7;
inline LL read(){
    register LL x=0,f=1;register char c=getchar();
    while(c<48||c>57){if(c=='-')f=-1;c=getchar();}
    while(c>=48&&c<=57)x=(x<<3)+(x<<1)+(c&15),c=getchar();
    return f*x;
}

const int MAXN=3e6+5;
const int mod=1e9+7;

int fac[MAXN],ifac[MAXN],inv[MAXN];
int n,m,up,x,y,ans;

inline int add(int x,int y){x+=y;return x>=mod?x-mod:x;}
inline int mul(LL x,int y){x*=y;return x>=mod?x%mod:x;}

inline void flip1(int &x,int &y){swap(x,y);x--,y++;}
inline void flip2(int &x,int &y){swap(x,y);x+=m+2,y-=m+2;}
inline int calc(int x,int y){
    if(x<0||y<0) return 0;
    return mul(fac[x+y],mul(ifac[x],ifac[y]));
}

int main(){
    n=read(),m=read();up=max(n,m)*3+1;
    inv[0]=inv[1]=fac[0]=fac[1]=ifac[0]=ifac[1]=1;
    for(int i=2;i<=up;i++){
        inv[i]=mod-1ll*(mod/i)*inv[mod%i]%mod;
        fac[i]=mul(fac[i-1],i);
        ifac[i]=mul(ifac[i-1],inv[i]);
    }
    x=n+m+1,y=n;
    ans=calc(x,y);
    while(x>=0&&y>=0){
        flip1(x,y); ans=add(ans,mod-calc(x,y));
        flip2(x,y); ans=add(ans,calc(x,y));
    }
    x=n+m+1,y=n;
    while(x>=0&&y>=0){
        flip2(x,y); ans=add(ans,mod-calc(x,y));
        flip1(x,y); ans=add(ans,calc(x,y));
    }
    printf("%d\n",ans);
}

[JLOI2015]骗我呢

原文：https://www.cnblogs.com/lizehon/p/10585345.html