原题： http://hihocoder.com/contest/challenge5
解答
=========
A 字体
这个题是线段树
B 魔法
这个题思路很简单，n个箱子构成m个轮换，每个轮换为 t1->t2->t3..->tj, （即t1箱子含有t2的钥匙，t2的箱子含有t3的钥匙...）
现在要求的概率是，从n个箱子中挑出k个，他们分布在所有的m个轮换中的概率。
- 求出挑k个箱子恰好分布在m个轮换中，这是一个分组背包问题:
- 每个轮换是一个背包分组，容量为s, 里面每个物品i 对应从该轮换中挑出i个箱子(显然0<i<=k）。
- dp地装入某个背包分组： cnt1[ 0 <= x <= k ] = E { cnt [ 0 <= x-i <=k ] * C( s, i ) , 其中
0<i<=k }
一开始想得比较复杂，C（300， x ）是会爆long long int的， 后来发现数据很弱。
C 与链
这个题是对二进制位的分组背包，
- 假设该位为1的ai 个数为j， 那么 个数j的取值可以为0到k， 那么j的每种取值就是取一个物品；
- 又因为个数j 只能取一个值，就相当于这些物品（或取值）构成一个背包分组（或一个新的虚拟物品）
- 然后多个2进制位构成多个背包分组。
代码
=========
B 魔法解箱子算概率
分组背包 O（K^2 * m ), m为轮换个数即物品分组个数， K为背包容量， 同时也是 每个分组的物品个数的上限
#include<iostream>
#include<iomanip>
using namespace std;
#include <string.h>
#include <vector>
typedef long double ll;
ll a[301][301];
void ca(){
memset(a, 0, sizeof(a));
for(int i=1; i<301; i++) a[0][i]=0;
for(int i=0; i<301; i++) a[i][0]=1;
for(int i=1; i<301; i++){
for(int j=1; j<301; j++){
a[i][j] = a[i-1][j] + a[i-1][j-1];
}
}
}
double calc(vector<int> &ss, int n, int K){
int l = ss.size();
// l ge beibao
vector<ll> cnt(K+1, 0), tmp;
cnt[0]=1;
for(int i=0; i<l; i++){
tmp=vector<ll>(K+1, 0);
for(int j=1; j <= ss[i] && j <= K; j++){
for(int k=0; k<=K-j; k++){
// tmp[k+j] = tmp[k+j] + cnt[k];//@error
tmp[k+j] = tmp[k+j] + cnt[k]*a[ss[i]][j];
}
}
cnt=tmp;
}
//cout<<cnt[K]<<":"<<a[n][K]<<endl;
return cnt[K]/a[n][K];
}
int main(){
int casen; cin>>casen;
ca();
for(int casei=0; casei<casen; casei++){
int n, k;
cin>>n>>k;
vector<int> s(n, -1);
for(int i=0; i<n; i++){
//cin>>s[i]; @error
int a; cin>>a; s[i]=a-1;
}
vector<bool> visit(n, false);
vector<int> ss;
for(int i=0; i<n; i++){
if(!visit[i]){
int cnt=0;
int j = i;
while(!visit[j])
cnt++, visit[j]=true, j=s[j];
ss.push_back(cnt);
//cout<<":"<<cnt<<endl;
}
}
cout<<fixed<<setprecision(9)<<calc(ss, n, k)<<endl;
}
return 0;
}
C 与链 （分组背包， O(n*k) )
#include <iostream>
#include <vector>
using namespace std;
typedef long long int ll;
#define MOD 1000000009
int calc(int n, int k){
vector<ll> cnt(n+1, 0);
vector<ll> tmp;
cnt[0]=1;
for(int step=1; step<=n; step*=2){
tmp = cnt;
for(int i=1; i<=k; i++){
for(int j=0; j<=n-step*i; j++){
tmp[j+step*i]+=cnt[j];
tmp[j+step*i]%=MOD;
}
}
cnt=tmp;
}
return cnt[n];
}
int main(){
int N; cin>>N;
for(int casei=0; casei<N; casei++){
int n,k ;
cin>>k>>n;
cout<<calc(n, k)<<endl;
}
return 0;
}