【LOJ】#2109. 「JLOI2015」骗我呢

题解

我深思熟虑许久才算是明白个大概的计数问题吧

先是转化成一个矩形，列一条直线y = x,y = x - (m + 1)我们从(0,0)走到(n + m + 1,m + 1)就是答案

因为我们起始相当于第一行缺一个0，然后有m+1种转移的方案，每次在距左边界j的地方某个点向上走表示转移到缺j - 1，向右走一步走到了缺j，再走一步走到缺j + 1....

我们把向上走当做-1，向右走当做+1，我们可以建立一个新的模型

就是起点为\((0,0)\)终点为\((2 * n + m + 1,m + 1)\)，每次可以走到\((x + 1,y + 1)\)或者走到\((x + 1,y - 1)\)

不能碰到\(y = -1\)或者\(y = m + 2\)

我们要用总方案去掉碰到\(y = -1\)和碰到\(y = m + 2\)再加上两个都碰到的

我们对于碰到\(y = -1\)我们就关于让终点关于\(y = -1\)对称，求原点到那里的方案数，因为每条不合法的路径对应一条到翻折点的路径在和\(y = -1\)第最后一个交点处后的路径沿\(y = -1\)翻折即可

我们把两个都碰到的拆成最后一个碰到的是\(y = -1\)记为A和第最后一个碰到的是\(y = m + 2\)记为B

举个例子

我们对于\(y = -1\)统计第最后碰到的是A

对于一条需要被加上的路径（也就是影响需要被抵消的路径）

经历的顺序记为

ABABA

那么我们

去掉了后缀为AB 和A 的

再加上后缀为AB 和 ABA的

再减去后缀为ABA 和 ABAB的

直到不能计算了为止

怎么计算后缀为AB 和 ABA的两种情况呢

我们把\(y = m + 2\)对着\(y = -1\)再次翻折，把(n * 2 + m + 1,m + 1)这个点对着\(y = -1\)翻折后，再次对着\(y = -m - 4\)翻折

计算(0,0)到目标点的答案就是我们想要的

最后我们只要把直线不断翻折直到不能达成为止

我们再对\(y = m + 1\)做相同的操作即可

这道题要是考场上给我，我也只能写60分暴力滚粗了……

代码

#include <bits/stdc++.h>

#define enter putchar('\n')

#define space putchar(' ')

#define pii pair<int,int>

#define fi first

#define se second

#define mp make_pair

#define pb push_back

#define eps 1e-8

#define MAXN 4000005

//#define ivorysi

using namespace std;

typedef long long int64;

typedef unsigned long long u64;

typedef double db;

template<class T>

void read(T &res) {

    res = 0;T f = 1;char c = getchar();

    while(c < '0' || c > '9') {

        if(c == '-') f = -1;

        c = getchar();

    }

    while(c >= '0' && c <= '9') {

        res = res * 10 - '0' + c;

        c = getchar();

    }

    res *= f;

}

template<class T>

void out(T x) {

    if(x < 0) {x = -x;putchar('-');}

    if(x >= 10) out(x / 10);

    putchar('0' + x % 10);

}

const int MOD = 1000000007;

int inc(int a,int b) {

    return a + b >= MOD ? a + b - MOD : a + b;

}

int mul(int a,int b) {

    return 1LL * a * b % MOD;

}

int fac[MAXN],invfac[MAXN],inv[MAXN],N,M,ans,x;

int C(int n,int m) {

    if(n < m) return 0;

    return mul(fac[n],mul(invfac[m],invfac[n - m]));

}

int F(int n,int m) {

    return C(n,(n - m) / 2);

}

void Calc(int y,int y_1,int y_2) {

    while(1) {

        y = 2 * y_1 - y;

        y_2 = 2 * y_1 - y_2;

        if(abs(y) > x) break;

        ans = inc(ans,MOD - F(x,y));

        y = 2 * y_2 - y;

        y_1 = 2 * y_2 - y_1;

        if(abs(y) > x) break;

        ans = inc(ans,F(x,y));

    }

}

int main() {

#ifdef ivorysi

	freopen("f1.in","r",stdin);

#endif

    read(N);read(M);

    inv[1] = 1;

    for(int i = 2 ; i <= 4000000 ; ++i) inv[i] = mul(inv[MOD % i],MOD - MOD / i);

    fac[0] = invfac[0] = 1;

    for(int i = 1 ; i <= 4000000 ; ++i) {

        fac[i] = mul(fac[i - 1],i);

        invfac[i] = mul(invfac[i - 1],inv[i]);

    }

    x = 2 * N + M + 1;

    ans = inc(ans,F(x,M + 1));

    Calc(M + 1,-1,M + 2);Calc(M + 1,M + 2,-1);

    out(ans);enter;

}

巴特西

【LOJ】#2109. 「JLOI2015」骗我呢

题解

代码

最新文章

热门文章