首页 > 代码库 > 【UVA】12034-Race(递推,组合数打表)
【UVA】12034-Race(递推,组合数打表)
递推公式,假设第一名有i个人并列,那么:
f[n] = C(n,i) * f[n - i];
打出1 ~ 1000的所有组合数,之后记忆化搜索,需要打表。
14026995 | 12034 | Race | Accepted | C++ | 0.032 | 2014-08-12 11:47:47 |
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<vector> #include<stack> #include<queue> #include<map> #include<set> #include<list> #include<cmath> #include<string> #include<sstream> #include<ctime> using namespace std; #define _PI acos(-1.0) #define INF (1 << 10) #define esp 1e-6 typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> pill; /*=========================================== ===========================================*/ #define MAXD 1000 + 10 #define mod 10056 LL f[MAXD]; LL C[MAXD][MAXD]; LL _C(){ C[1][1] = 1; C[1][0] = 1; for(int i = 2 ; i <= MAXD - 10 ; i++) for(int j = 0 ; j <= i ; j++){ if(j == 0) C[i][j] = 1; else C[i][j] = C[i - 1][j - 1] + C[i - 1][j]; C[i][j] %= mod; } } LL _f(int n){ LL ans = 0; if(f[n] != -1) return f[n]; for(int i = 1 ; i <= n ; i++){ ans = ans + C[n][i] * _f(n - i); ans %= mod; } f[n] = ans; return f[n]; } int main(){ memset(f,-1,sizeof(f)); f[1] = 1; f[0] = 1; _C(); _f(MAXD - 10); int T,Case = 1; scanf("%d",&T); while(T--){ int n; scanf("%d",&n); printf("Case %d: %lld\n",Case++,f[n]); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。