【GDOI2014模拟】网格【蒟蒻的小题解】
学习压行+卡常第一天。。。
Description
某城市的街道呈网格状,左下角坐标为A(0, 0),右上角坐标为B(n, m),其中n >= m。现在从A(0, 0)点出发,只能沿着街道向正右方或者正上方行走,且不能经过图示中直线左上方的点,即任何途径的点(x, y)都要满足x >= y,请问在这些前提下,到达B(n, m)有多少种走法。
Input
输入文件中仅有一行,包含两个整数n和m,表示城市街区的规模。
Output
输出文件中仅有一个整数和一个换行/回车符,表示不同的方案总数。
Sample Input
输入1:
6 6
输入2:
5 3
Sample Output
输出1:
132
输出2:
28
问:一眼过去是不是道大水题?那么请看一下时间限制,空间限制以及数据范围。
Time Limits: 1000 ms
Memory Limits: 65536 KB
50%的数据中,n = m,在另外的50%数据中,有30%的数据:1 <= m < n <= 100
100%的数据中,1 <= m <= n <= 5 000
是不是顿时就蒙了?
来个滚动数组,来个压位高精这样就不会MLE了吧?也不会RE了吧?
BOOM!!!恭喜你TLE了!!!
兄弟们,这是数学题啊!!!
进入正题
经过推算,我们发现:
别问我是怎么推出来的
然后,为了不打高精度除法 ,我们考虑把每个东西,即上面挂着的那几个东西(博主懒,不想打出来~~~),然后分解质因数,用质因数相乘就可以免掉除法高精,如果你想打除法高精,请自动省略下面推导部分。
推导:
我们知道
而
这里的是指质因子,指此质因子的个数。
同理,分解和,设为中某个质因子的个数,设为中某个质因子的个数,然后合并,就成为了以下式子:
秒啊!这样就只需要打乘法了!
那至于减法呢?也要打,用于,也就是求最终结果时用。
好了,这题的思路就是这么简单!下面放出code。
CODE
本人今天刚开始学卡常和压行。。。有点丑。。。别喷了别喷了,再喷人傻了。
//L.E.M.T专用水印
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
struct node {
int len,a[10005];
}ans,c,b,t;
int n,m,cnt,p[10005],bj[10005],v[10005],mo=100000;
inline int read() {
int s=0;
char ch=getchar();
while (ch<'0'||ch>'9') ch=getchar();
while (ch>='0'&&ch<='9') {s=s*10+ch-'0',ch=getchar();}
return s;
}
inline node jian(node x,node y) {
t=b,t.len=x.len;
for (register int i=1;i<=x.len;i++) {
t.a[i]+=x.a[i]-y.a[i];
if (t.a[i]<0) t.a[i]+=mo,t.a[i+1]--;
}
while (t.len>0&&t.a[t.len]==0) t.len--;
return t;
}
inline node cheng(node x,int g) {
t=b;
t.len=x.len;
for (register int i=1;i<=x.len;i++) {
t.a[i]+=x.a[i]*g,t.a[i+1]+=t.a[i]/mo,t.a[i]%=mo;
}
t.len++;
while (t.a[t.len]>=mo) {
t.a[t.len+1]+=t.a[t.len]/mo,t.a[t.len]%=mo,t.len++;
}
if (t.a[t.len]==0) t.len--;
return t;
}
inline void fen(int x,int t) {
while (x>1) {v[bj[x]]+=t,x/=bj[x];}
}
inline node find(int n,int m) {
memset(v,0,sizeof(v));
c=b,c.len=1,c.a[1]=1;
for (register int i=n-m+1;i<=n;i++) fen(i,1);
for (register int i=1;i<=m;i++) fen(i,-1);
for (register int i=1;i<=10005;i++) {for (int j=1;j<=v[i];j++) c=cheng(c,i);}
return c;
}
int main() {
for (register int i=2;i<=10005;i++) {
if (bj[i]==0) {bj[i]=i,cnt++,p[cnt]=i;}
for (register int j=1;j<=cnt;j++) {
if (i*p[j]>10005) {break;}
bj[i*p[j]]=p[j];
if (i%p[j]==0) {break;}
}
}
n=read(),m=read();
ans=jian(find(n+m,m),find(n+m,m-1));
printf("%d",ans.a[ans.len]);
for (register int i=ans.len-1;i>=1;i--) printf("%05d",ans.a[i]);
}
应该都看懂了吧?(试探)
上一篇: 2020.10.27【CSP-J/S】普及组模拟赛总结
下一篇: 信息课蒟蒻指南