题解 P3266 【[JLOI2015]骗我呢】

· · 题解

把大小关系看成一条边。

发现，最长的路径，就是从 (1,x)\rightarrow(n,y) 的这样长度为 m 的路径。

现在一共有 m+1 种不同数值，所以每条路径只会有 1 处可以选择比正常大 1 的数值。

所以假如要选某一个点作为 +1 的点，此时，他左上的的点都不能选。

所以可以有以下爆搜的代码。

#include<bits/stdc++.h>
using namespace std;
int n,m,ans;
inline void dfs(int x,int down)
{
    if(x==n+1) {ans++;return ;}
    for(int i=down;i<=m;i++) dfs(x+1,i);
    dfs(x+1,max(down-1,1));
}
int main()
{
    cin>>n>>m;
    dfs(1,1);
    cout<<ans<<endl;
}

发现这个选的状态可以理解成走格子。

假如上次选的是红色节点，那么红色圈起来的就是可选。

可以选的状态，相当于每次向右下走，接下来向上走能到的节点状态。

那么可以用一条只往 右下，上，走的路径，代表一种状态。

这个代表是双射，证明比较显然。

任何一种状态可以用一条路径表示，这个显然。

一条路径，可以代表一种状态，就是看那一步是向右下走。

tips

注意这个最下一排，我们要新建一排 虚点使其可以转移。

为了统计最后一列的和，可以新建一排虚点，然后把路径个数和转成到点 (n+1,m+1) 的路径个数。

统计路径大概的 dp

#include<bits/stdc++.h>
using namespace std;
int n,m,ans;
#define int long long
int dp[1000][1000];
const int mod=1e9+7;
signed main()
{
    cin>>n>>m;
    dp[1][1]=1;
    for(int i=1;i<=m+1;i++) dp[1][i]=1;
    for(int i=2;i<=n;i++)
    {
        dp[i][0]=dp[i-1][1];
        for(int j=1;j<=m+1;j++) dp[i][j]=dp[i-1][j+1]+dp[i][j-1], dp[i][j]%=mod;
    }
    int ans=0;
    for(int i=1;i<=m+1;i++) ans+=dp[n][i],ans%=mod;
    cout<<ans<<endl;
}

把这个斜着的图“转正”。

本质上相当于是一个矩形，有两条线限制，不能经过这两条线的点。

如果只有一条线限制，可以用折线法，构造双射。

如果我们对于每一条线折一次线，会用重复，比如说，我们假设经过 第一条线叫做 A ，经过第二条线叫做 B。注意，假如连续经过A\ or \ B ，我们只算一次。

那么 AB 。会被 A 算一遍 ，B 算一遍。

这时我们要减去 AB,BA 。此时还会有类似问题 。于是考虑容斥，这个类似前缀容斥。

即对 ABAB\cdots 这种串进行容斥。

tips

具体就是每次把一条直线根据另一条直线对称，然后把终点关于“对称后”这条新直线，再次对称。

由于每次问题都可以化归成经过两条直线的路径数，而且直线斜率均为 1，我们可以只维护截距，这样很好计算对称后的坐标，新的截距等你所维护的东西。

折线法代码。

#include<bits/stdc++.h>
using namespace std;
int n,m;
#define int long long
const int mod=1e9+7,N=3e6+10;;
int f[N],finv[N];
inline int qpow(int a,int b)
{
    int k=1;
    while(b){if(b&1) k=k*a%mod;a=a*a%mod,b>>=1;}
    return k;
}
inline pair<int,int> ref(int x,int y,int d){return make_pair(y-d,x+y-(y-d));}
inline int reflect(int a,int b){return a+a-b;}
inline int comb(int n,int m)
{
    if(n<0||m<0||n<m) return 0;
    return f[n]*finv[n-m]%mod*finv[m]%mod;
}
signed main()
{
    cin>>n>>m;n++,m+=2;
    f[0]=1;finv[0]=1;
    for(int i=1;i<=n+n+m;i++) f[i]=f[i-1]*i%mod;
    finv[n+n+m]=qpow(f[n+n+m],mod-2);
    for(int i=n+n+m-1;i>=1;i--) finv[i]=finv[i+1]*(i+1)%mod;
    int x,y,a,b,ans=0;
    x=n-1,y=n+m-1-1;a=-1,b=m;
    ans=comb(x+y,x);
    for(int j=1;j<=2;j++)
    {
        x=n-1,y=n+m-1-1;a=m,b=-1;
        if(j==2) swap(a,b);
        for(int i=1;i<=n+n+m;i++)
        {
            if(i==1)
            {
                pair<int,int>pot=ref(x,y,a);x=pot.first,y=pot.second;
            }
            else
            {
                if(i&1)
                {
                    a=reflect(b,a);pair<int,int>pot=ref(x,y,a);
                    x=pot.first,y=pot.second;
                }
                else
                {
                    b=reflect(a,b);pair<int,int>pot=ref(x,y,b);
                    x=pot.first,y=pot.second;
                }
            }
            if(i&1) 
            {
                ans-=comb(x+y,x);
                if(ans<0) ans+=mod;
            }
            else 
            {
                ans+=comb(x+y,x);
                if(ans>=mod) ans-=mod;
            }

        }
    }
    cout<<ans;
}
/*
23 233
938980383
*/