首页 > 代码库 > N球M盒问题 & Password Attacker google code jam
N球M盒问题 & Password Attacker google code jam
第一个题目本质是个动归dp问题。但是分析dp的方程使用了组合数学中的N求M盒问题。
先来看下N球M盒的经典问题。
给定N个相同的球，放入M个不同的盒子中，要求每个盒子必须非空，求组合数。
假设Xi为第i个盒子中的放入的小球数，则方程
X1+X2+X3+...+Xm=N,
其实抽象成数学问题，就是求这个M元1次方程的正整数解的组数。
插板法分析：
N个小球排成一行，插入M-1个板，只能在小球中间插，而且板与板之间必须有球
分析到这里，聪明的大家肯定一看就知道是个N-1个空隙选M-1个来放入板，Cm-1,n-1.
有了上面的分析方法后，我们可以接着来分析原题。
dp[i][j]可以先考虑dp[i-1][k]，
那么还剩下j-k个相同的元素待插入，把j-k相同的球分成k个不同的堆，每堆可以为空。
为了转化成堆至少有一个球的情形，我们每个堆放入一个球，现在又可以变成了插板问题。最后插板得到的组合，每个减去1就是了
所以：最后动归的公式就是
dp(i,j)=sum( dp(i-1,k)C(j,k))
k 是 i-1 ~ j-1
调试的过程中一定用longlong来存储
typedef int64 long long
1 #include<cstdio> 2 #include<iostream> 3 #include<iomanip> 4 #include<cmath> 5 #include<cstring> 6 #include<cstdlib> 7 #include<string> 8 #include<sstream> 9 #include<vector> 10 #include<map> 11 #include<set> 12 #include<bitset> 13 #include<algorithm> 14 #include<cassert> 15 #include<ctime> 16 #include<queue> 17 using namespace std; 18 19 #define REP(i,n) for(int i = 0; i < (int)n; i++) 20 #define FOR(i,n,m) for(int i = (int)n; i <= (int)m; i++) 21 #define FOD(i,n,m) for(int i = (int)n; i >= (int)m; i--) 22 #define EACH(i,v) for(decltype((v).begin()) i = (v).begin(); i != (v).end(); i++) 23 24 typedef long long i64; 25 typedef pair<int, int> PI; 26 27 #define sz(v) ((i64)(v).size()) 28 #define all(v) (v).begin(),(v).end() 29 #define bit(n) (1LL<<(i64)(n)) 30 31 #define PB push_back 32 #define MP make_pair 33 #define X first 34 #define Y second 35 template<class T> void fmax(T &a, const T &b) { if (a < b) a = b; } 36 template<class T> void fmin(T &a, const T &b) { if (a > b) a = b; } 37 template<class T> T sqr(const T &a) { return a * a; } 38 39 long long M=1000000007LL; 40 41 long long C[101][101]; 42 long long dp[101][101]; 43 44 void composition(){ 45 FOR(i,0,100){ 46 C[i][i]=1; 47 C[i][0]=1; 48 } 49 50 FOR(i,2,100){ 51 FOR(j,1,i-1){ 52 C[i][j]=C[i-1][j]+C[i-1][j-1]; 53 } 54 } 55 } 56 57 void getCombination() { 58 int n = 105; 59 for (int i = 1; i <= n; i++) 60 C[i][0] = C[i][i] = 1LL; 61 62 for (int i = 2; i <= n; i++) 63 for (int j = 1; j <= i; j++) 64 C[i][j] = (C[i-1][j-1] % M + C[i-1][j] % M) % M; 65 } 66 67 long long solve(int m,int n){ 68 /* 69 memset(dp,0,sizeof(dp)); 70 FOR(i,1,n) 71 dp[1][i]=1; 72 FOR(i,2,n) 73 dp[i][i]=(dp[i-1][i-1] * (long long)i ) %M; 74 75 FOR(i,2,m){ 76 FOR(j,i+1,n){ 77 FOR(k,i-1,j-1){ 78 //dp[i][j]=(dp[i][j]+(dp[i-1][k]*C[j][k])%M)%M; 79 dp[i][j] = (dp[i][j] + (C[j][k] * dp[i-1][k]) % M) % M; 80 } 81 } 82 } 83 */ 84 memset(dp, 0LL, sizeof(dp)); 85 for (int i = 1; i <= n; i++) dp[1][i] = 1; 86 for (int i = 2; i <= n; i++) dp[i][i] = (dp[i-1][i-1] * (long long)i) % M; 87 88 for (int i = 2; i <= m; i++) 89 for (int j = i+1; j <= n; j++) 90 for (int k = i-1; k <= j-1; k++) 91 dp[i][j] = (dp[i][j] + (C[j][k] * dp[i-1][k]) % M) % M; 92 return dp[m][n]; 93 } 94 95 int main(){ 96 freopen("input.txt","r",stdin); 97 // freopen("out.txt","w",stdout); 98 int M,N,T; 99 //composition();100 getCombination();101 cin>>T;102 int counter=1;103 while(T--){104 cin>>M>>N;105 cout<<"Case #"<<counter++<<": "<<solve(M,N)<<endl;106 107 }108 return 0;109 }
最后代码奉上
N球M盒问题 & Password Attacker google code jam
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。