首页 > 代码库 > 【NOIP模拟题】Permutation（dp+高精度）
【NOIP模拟题】Permutation（dp+高精度）
首先我们可以这样想：
设状态f[i, j]表示1～i序列有j个‘<‘的方案数
那么考虑转移
因为i比i-1大，所以可以考虑从i-1来转移。首先i是要插入1～i-1这个序列的，所以我们可以思考插入的位置：
仔细推下可得：
当插入的位置原来是‘<‘时，答案不会改变
当插入的位置原来是‘>‘时，答案会+1
当插入左边界时，答案不变
当插入有边界时，答案+1
那么我们知道了前i-1的‘<‘数量和‘>‘的数量那么就能转移了
f[i,j]=(j+1)*f[i-1, j]+(max{i-1-(j-1), 0}+1)*f[i-1, j-1])
然后用高精度做。。
我就不吐槽高精度写错了个地方调试了好久！！！！！！！！！！！！
记住每一次调用的运算数一定要清空！！！！即在赋值的时候一定先清空后赋值！！！！！
#include <cstdio>#include <cstring>#include <cmath>#include <string>#include <iostream>#include <algorithm>#include <queue>#include <set>#include <vector>#include <map>using namespace std;typedef long long ll;#define pii pair<int, int>#define mkpii make_pair<int, int>#define pdi pair<double, int>#define mkpdi make_pair<double, int>#define pli pair<ll, int>#define mkpli make_pair<ll, int>#define rep(i, n) for(int i=0; i<(n); ++i)#define for1(i,a,n) for(int i=(a);i<=(n);++i)#define for2(i,a,n) for(int i=(a);i<(n);++i)#define for3(i,a,n) for(int i=(a);i>=(n);--i)#define for4(i,a,n) for(int i=(a);i>(n);--i)#define CC(i,a) memset(i,a,sizeof(i))#define read(a) a=getint()#define print(a) printf("%d", a)#define dbg(x) cout << (#x) << " = " << (x) << endl#define error(x) (!(x)?puts("error"):0)#define printarr2(a, b, c) for1(_, 1, b) { for1(__, 1, c) cout << a[_][__]; cout << endl; }#define printarr1(a, b) for1(_, 1, b) cout << a[_] << ‘\t‘; cout << endlinline const int getint() { int r=0, k=1; char c=getchar(); for(; c<‘0‘||c>‘9‘; c=getchar()) if(c==‘-‘) k=-1; for(; c>=‘0‘&&c<=‘9‘; c=getchar()) r=r*10+c-‘0‘; return k*r; }inline const int max(const int &a, const int &b) { return a>b?a:b; }inline const int min(const int &a, const int &b) { return a<b?a:b; }const int N=1155;int n, k;typedef int big[N];big f[N], tp, tp2;void clr(big a) { memset(a, 0, sizeof(int)*(a[0]+1)); a[0]=1; }void eqr(big a) { clr(a); memcpy(a, tp, sizeof(int)*(tp[0]+1)); } //先清空void fix(big a) { int i=a[0]; while(i>1 && !a[i]) --i; a[0]=i; }void Pr(big a) { for3(i, a[0], 1) printf("%d", a[i]); }void mul(big a, int t) { clr(tp); for1(i, 1, a[0]) tp[i]=a[i]*t; int k=0, i, sz=a[0]+32; for(i=1; i<=sz || k; ++i) { tp[i]+=k; k=tp[i]/10; tp[i]%=10; } tp[0]=i; fix(tp);}void pls(big a, big b) { clr(tp); int k=0, i, sz=max(a[0], b[0]); for(i=1; i<=sz || k; ++i) { tp[i]=a[i]+b[i]+k; k=tp[i]/10; tp[i]%=10; } tp[0]=i; fix(tp);}int main() { read(n); read(k); for1(i, 0, k) clr(f[i]); f[0][1]=1; for1(i, 2, n) for3(j, k, 0) { mul(f[j], j+1); eqr(f[j]); if(j>0) { int t=max(0, i-1-j)+1; mul(f[j-1], t); eqr(tp2); pls(f[j], tp2); eqr(f[j]); } } Pr(f[k]); return 0;}
【题目描述】
将 1 到 N 任意排列，然后在排列的每两个数之间根据他们的大小关系插入“>”和“<”。
问在所有排列中，有多少个排列恰好有K个“<”。
例如排列(3, 4, 1, 5, 2)
3 < 4 > 1 < 5 > 2
共有2个“<”
【输入格式】
N,K
【输出格式】
答案
【样例输入】
52
【样例输出】
66
【数据范围】
20%：N<= 10
50%：答案在0..2^63-1内
100%：K< N <= 100
【NOIP模拟题】Permutation（dp+高精度）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。