放课后的约定 by:S_H_Y

时间:2022-05-16 14:19:11

题目背景

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

题目描述

一条君的项链弄丢了,或许还躺在学校草坪里的某处,那条项链系着他珍藏的一把锁。千棘虽然不情愿,但是也必须帮忙找,因为这起事大概是她造成的。

学校草坪可以看作N×M的格子。一条从左上角(1,1),千棘从右下角(n,m)开始寻找。每个时刻,一条会选择一个他自己没有找过的某块草坪开始找,(他应该不知晓千棘有没有找过这块草坪)。千棘也这么做。但是,同一时刻,一条和千棘不能在同一个格子里,不然他们会发生口角。

历史的车轮已经留下辙迹,未来的迷一般的花园却绚丽绛紫、怦然心动。是宇宙幽默的必然,还是人类甜涩的多情。总之,他们想知道,这样的搜寻方案,有多多少少呢。

输入输出格式

输入格式:

第一行两个整数N,M,表示草坪的长和宽。

输出格式:

一行一个正整数Ans,表示方案数,除以23333的余数。

输入输出样例

输入样例#1:
2 2
输出样例#1:
18
样例解释:
一条:(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。

★啊阿 淡淡浮现脑海不确定的记忆

★仅是轮廓却充满着荆棘的样子

★紧紧束缚内心

巧克力便当还是兔子沙盒。

放课后的约定 by:S_H_Y

Thanks for viewing this problem.

出题人:S_H_Y

思路:首先要明確一個問題,由於一條和千棘是二次人物或其他各種神奇的原因,他們的移動方式是瞬移。。。

然後問題就可以轉化為求一條的全部搜索路線每條各自對應的錯排列的總和。

由於第一個搜索點是確定的,所以一條的全部搜索路線a=(n*m-1)!。

由於千棘的第一個搜索點也是確定的,所以每一條一條的搜索路線對應的錯排數b=f[n*m-1]=f[n*m-1]+(f[n*m-1]+1)*(n*m-2)。(這個式子是要一路推過來的)

另外,還需要惡心的高精技巧,而且還要取mod。

額呵呵,根據式子,如果m*n>mod,輸出0即可,不用太在意n*m爆空間的問題了,高精也可以水一點了。

然而水不過,so。。。

放课后的约定 by:S_H_Y

代碼實現:

 #include<cstdio>
#include<iostream>
using namespace std;
const int mod=;
long long n,m;
int yt=,qj[],ans;
int main(){
cin>>n>>m;qj[]=;
if(n>mod||m>mod||n*m>mod||n*m==){printf("0\n");return ;}//特判一下。
if(m*n==){printf("1\n");return ;}//特判一下。
for(int i=;i<=n*m-;i++){yt*=i;yt%=mod;}
for(int i=;i<=n*m;i++) qj[i]=(qj[i-]+qj[i-])*(i-)%mod;
ans=(yt*qj[n*m])%mod;
printf("%d\n",ans);
return ;
}

內心崩潰,無以言說。

题目来源:洛谷