当前位置：首页 > news >正文

放课后的约定

news 来源：原创 2024/9/21 9:03:13

【题目描述】

“十年。十年前。天空的蔚蓝，云彩的舒软。我，怎么会认识你。洁白的，洁白的，十年前。我无法忘却。终究是小时候的约定。记忆被困在冻土里，有时我不认识那天的我。难道一切，都锁在心里面了吗？”

学校草坪为一块N×M的地图，一条从左上角(1,1)、千棘从右下角(n,m)开始寻找。

每个时刻，一条会选择一个他自己没有找过的某块草坪开始找，千棘也这么做，但是，同一时刻，一条和千棘不能在同一个格子里，不然他们会发生口角。

现询问有多少合法的搜寻方案。

【输入描述】

第一行输入两个整数N、M，表示草坪的长和宽。

【输出描述】

一行输出一个正整数Ans，表示方案数 mod 23333的值。

【输入样例】

2 2

【输出样例】

【数据范围及提示】

样例解释：

一条：(1,1)-(1,2)-(2,1)-(2,2)　　千棘：(2,2)-(1,1)-(1,2)-(2,1)

一条：(1,1)-(1,2)-(2,1)-(2,2)　　千棘：(2,2)-(2,1)-(1,1)-(1,2)

一条：(1,1)-(1,2)-(2,1)-(2,2)　　千棘：(2,2)-(2,1)-(1,2)-(1,1)

一条：(1,1)-(1,2)-(2,2)-(2,1)　　千棘：(2,2)-(1,1)-(2,1)-(1,2)

一条：(1,1)-(1,2)-(2,2)-(2,1)　　千棘：(2,2)-(2,1)-(1,1)-(1,2)

一条：(1,1)-(1,2)-(2,2)-(2,1)　　千棘：(2,2)-(2,1)-(1,2)-(1,1)

一条：(1,1)-(2,1)-(1,2)-(2,2)　　千棘：(2,2)-(1,1)-(2,1)-(1,2)

一条：(1,1)-(2,1)-(1,2)-(2,2)　　千棘：(2,2)-(1,2)-(1,1)-(2,1)

一条：(1,1)-(2,1)-(1,2)-(2,2)　　千棘：(2,2)-(1,2)-(2,1)-(1,1)

一条：(1,1)-(2,1)-(2,2)-(1,2)　　千棘：(2,2)-(1,1)-(1,2)-(2,1)

一条：(1,1)-(2,1)-(2,2)-(1,2)　　千棘：(2,2)-(1,2)-(1,1)-(2,1)

一条：(1,1)-(2,1)-(2,2)-(1,2)　　千棘：(2,2)-(1,2)-(2,1)-(1,1)

一条：(1,1)-(2,2)-(1,2)-(2,1)　　千棘：(2,2)-(1,1)-(2,1)-(1,2)

一条：(1,1)-(2,2)-(1,2)-(2,1)　　千棘：(2,2)-(1,2)-(2,1)-(1,1)

一条：(1,1)-(2,2)-(1,2)-(2,1)　　千棘：(2,2)-(2,1)-(1,1)-(1,2)

一条：(1,1)-(2,2)-(2,1)-(1,2)　　千棘：(2,2)-(1,1)-(1,2)-(2,1)

一条：(1,1)-(2,2)-(2,1)-(1,2)　　千棘：(2,2)-(1,2)-(1,1)-(2,1)

一条：(1,1)-(2,2)-(2,1)-(1,2)　　千棘：(2,2)-(2,1)-(1,2)-(1,1)

共计18种方案。

对于30%的数据，n ≤ 2011，m ≤ 1000；

对于100%的数据，1 ≤ n ≤ 20114820163637，1 ≤ m ≤ 201205201610。

源代码：

#include<cstdio>
#define INF 23333
#define LL long long
LL n,m,Sum=1,i[24000];
int main()
{
    scanf("%I64d%I64d",&n,&m);
    if (n>INF||m>INF||n*m>INF||n*m==1) //一模没。
    {
        printf("0");
        return 0;
    }
    if (m*n==2) //都是特判。
    {
        printf("1");
        return 0;
    }
    i[2]=1;
    for (LL a=1;a<=n*m-2;a++)
      Sum=Sum*a%INF;
    for (LL a=3;a<=n*m;a++)
      i[a]=(i[a-1]+i[a-2])%INF*(a-1)%INF;
    printf("%I64d",Sum*i[n*m]%INF);
    return 0;
}

/*
    排列组合还是弱。
    n*m个格子可以看做S(n*m)个信封（⑨要写信）。
    若第1个格子不作要求，则第1个格子有n*(n-1)种可能，那么一条的方案数就是错排公式：
        (S-1)*(f[S-1]+f[S-2])
    同时，千棘（其实我是小野寺党）的方案数为全排列：
        S!
    若第1个格子为定值，则最终结果为：
        (S-2)!*f[S]
    还是要冷静仔细地分析问题。
*/