【洛谷P3266】[JLOI2015]骗我呢

更正题面,对于\(1 \le i \le n\); \(1 \le j <m\) 满足 \(x_{i,j} < x_{i,j+1}\)
对于每一行,一共有m个数,值域为\([0, m]\),而且每行的数单调上升,很显然,\([0, m]\),这些只有一个数不出现。并且我们每次新加一行的时候,只需要考虑上一行的状态就行了,因此我们列出一个朴素的dp状态,设dp[i][j]表示当前已经放了i行,最后一行缺的是j,转移方程为\(dp_{i,j} = \sum_{k = min(0, j + 1)}^{j + 1}dp_{i – 1, k}\),这个东西我们可以算一下就知道了,当m = 4,的时候,目前为0134,上一行为0124,这样是合法的,但是上一行为0123的时候这样就不合法了
那么现在我们将方程式变一下形,\(dp_{i, j} = dp_{i, j – 1} + dp_{i – 1, j + 1}\),可以发现现在我们每次转移只会向右一格&向左下一格。在这里题目的美妙即将展开了。我们现在可以把式子转化成图。
就是这么一张图片,问你从平行四边形右下走到左上且不跨越A B两直线的方案数。这样我们有一个比较显然的思路,用总方案数减去不合法的方案数。那么我们用A表示这个方案跨越了左边的边界,用B表示这个方案跨越了右边的边界。我们设最左下角的为\((0, 0)\),左侧直线表达式为\(y_{A} = x + 1\),右侧表达式为\(y_{B} = x – (m + 2)\)
那么我们的目的是去除形如ABABBBBAAAABABABAAAB这些方案。对于刚才那个方案,我们发现连续的一段区间可以直接缩成一个字母——他一直在跨越同一个边界,没有意义。所以刚才那个可以缩水成ABABABABABAB这样的方案。接下来,我们令初始点为\((n+m+1,n)\),重复以下操作:
将当前点以直线A为对称轴翻转,然后将原点到当前点的方案数从答案中减去,再将当前点以直线B为对称轴翻转,把原点到当前点的方案给加上,一直重【复】复【读】,直到当前点的任意一维坐标小于0结束。
这样子我们就相当于将以A和AB为后缀的方案删除了,然后把BA和BAB为后缀的方案加回去……所以实际上我们到最后是把以A为前缀的方案删除了。
同理再对B做一遍这样的操作。总方案为//(C_{2 * n + m + 1}^{n})。
放代码

#include<algorithm>
#include<iostream>
#include<cstring>
#include<climits>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#include<queue>
#include<map>
#define ri register int

using namespace std;

typedef long long lo;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

const lo mo = 1e9 + 7;

inline void re(lo &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

lo n, m, d, ans, inv[3000010], fac[3000010];

lo c(lo x, lo y)
{
    if(x < y)
        return 0;
    return fac[x] * inv[y] % mo * inv[x - y] % mo;
}

lo cc(lo x, lo y)
{
    if(x < 0 || y < 0)
        return 0;
    return c(x + y, y);
}

inline void change(lo &x, lo &y, lo num)
{
    swap(x, y), x += num, y -= num;
}

inline lo ksm(lo x, lo k)
{
    lo rt = 1, a = x;
    while(k)
        rt = rt * ((k & 1) ? a : 1) % mo, a = a * a % mo, k >>= 1;
    return rt;
}

int main()
{
    re(n), re(m), d = max(n, m), inv[1] = inv[0] = fac[1] = fac[0] = 1;
    for(ri i = 2; i <= 3000000; i ++)
        fac[i] = fac[i - 1] * i % mo;
    inv[3000000] = ksm(fac[3000000], mo - 2);
    for(ri i = 2999999; i >= 2; i --)
        inv[i] = inv[i + 1] * (i + 1) % mo;
    lo lx = n + m + 1, ly = n;
    ans = cc(lx, ly);
    while(lx >= 0 && ly >= 0)
        change(lx, ly, -1), ans -= cc(lx, ly), change(lx, ly, m + 2), ans += cc(lx, ly), ans %= mo;
    lx = n + m + 1, ly = n;
    while(lx >= 0 && ly >= 0)
        change(lx, ly, m + 2), ans -= cc(lx, ly), change(lx, ly, -1), ans += cc(lx, ly), ans %= mo;
    ans = (ans % mo + mo) % mo, printf("%lld", ans);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注