DP?

DP?

题解

看这标题取得，一看就知道不是DP。

我们可以先把每个点的路径长给算出来，根据贪心可知，对于一个点它的最小路径的走法是一定的。

这走法就是向斜上方或正上方一直走到底，然后就沿着1一直走。

如果在中线左方，就是往斜上方走，右方就是往右走。

而走到一的路径也十分好求，

这样用lucas就可以做出来了。

源码

感觉有点卡常。

#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
typedef long long LL;
const int mo=1e9+7;
const int INF=0x3f3f3f3f;
#define gc() getchar()
template<typename _T>
void read(_T &x){_T f=1;x=0;char s=gc();while(s>'9'||s<'0'){if(s=='-')f=-1;s=gc();}while(s>='0'&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=gc();}x*=f;
}
int fac[1505][10005],inv[1505][10005];
int prime[10005],cntp,mp[10005];
bool oula[10005];
int qkpow(int a,int s,int p){int t=1;while(s){if(s&1)t=t*a%p;a=a*a%p;s>>=1;}return t;
}
int C(int n,int m,int p){if(n<m)return 0;if(n==m)return 1;int t=mp[p];return fac[t][n]*inv[t][m]%p*inv[t][n-m]%p;//if(n<m)return 0;int up=1,down=1;//for(int i=n-m+1;i<=n;i++)up=up*i%p;//for(int i=2;i<=m;i++)down=down*i%p;//return up*qkpow(down,p-2,p)%p;
}
void init(){for(int i=2;i<=1e4;i++){if(!oula[i])prime[++cntp]=i,mp[i]=cntp;for(int j=i<<1;j<=1e4;j+=i)oula[j]=1;}for(int j=1;j<=cntp;j++){fac[j][0]=inv[j][0]=1;for(int i=1;i<=1e4;i++)fac[j][i]=fac[j][i-1]*i%prime[j],inv[j][i]=qkpow(fac[j][i],prime[j]-2,prime[j]);}
}
int lucas(int n,int m,int p){if(!m)return 1;return C(n%p,m%p,p)*lucas(n/p,m/p,p)%p;
}
signed main(){int n,m,p,tt=0;init();while(scanf("%d %d %d",&n,&m,&p)!=EOF){printf("Case #%d: ",++tt);if(m<=n/2)printf("%d\n",(lucas(n+1,m,p)+n-m)%p);else printf("%d\n",(lucas(n+1,m+1,p)+m)%p);}return 0;
}
/*
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1
2 2
3 4 3
4 6 6 4
5 8 12 8 5
6 10 18 18 10 6
*/

谢谢！！！

DP?

DP?

题解

看这标题取得，一看就知道不是DP。

我们可以先把每个点的路径长给算出来，根据贪心可知，对于一个点它的最小路径的走法是一定的。

这走法就是向斜上方或正上方一直走到底，然后就沿着1一直走。

如果在中线左方，就是往斜上方走，右方就是往右走。

而走到一的路径也十分好求，

这样用lucas就可以做出来了。

源码

感觉有点卡常。

#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
typedef long long LL;
const int mo=1e9+7;
const int INF=0x3f3f3f3f;
#define gc() getchar()
template<typename _T>
void read(_T &x){_T f=1;x=0;char s=gc();while(s>'9'||s<'0'){if(s=='-')f=-1;s=gc();}while(s>='0'&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=gc();}x*=f;
}
int fac[1505][10005],inv[1505][10005];
int prime[10005],cntp,mp[10005];
bool oula[10005];
int qkpow(int a,int s,int p){int t=1;while(s){if(s&1)t=t*a%p;a=a*a%p;s>>=1;}return t;
}
int C(int n,int m,int p){if(n<m)return 0;if(n==m)return 1;int t=mp[p];return fac[t][n]*inv[t][m]%p*inv[t][n-m]%p;//if(n<m)return 0;int up=1,down=1;//for(int i=n-m+1;i<=n;i++)up=up*i%p;//for(int i=2;i<=m;i++)down=down*i%p;//return up*qkpow(down,p-2,p)%p;
}
void init(){for(int i=2;i<=1e4;i++){if(!oula[i])prime[++cntp]=i,mp[i]=cntp;for(int j=i<<1;j<=1e4;j+=i)oula[j]=1;}for(int j=1;j<=cntp;j++){fac[j][0]=inv[j][0]=1;for(int i=1;i<=1e4;i++)fac[j][i]=fac[j][i-1]*i%prime[j],inv[j][i]=qkpow(fac[j][i],prime[j]-2,prime[j]);}
}
int lucas(int n,int m,int p){if(!m)return 1;return C(n%p,m%p,p)*lucas(n/p,m/p,p)%p;
}
signed main(){int n,m,p,tt=0;init();while(scanf("%d %d %d",&n,&m,&p)!=EOF){printf("Case #%d: ",++tt);if(m<=n/2)printf("%d\n",(lucas(n+1,m,p)+n-m)%p);else printf("%d\n",(lucas(n+1,m+1,p)+m)%p);}return 0;
}
/*
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1
2 2
3 4 3
4 6 6 4
5 8 12 8 5
6 10 18 18 10 6
*/

谢谢！！！