CSP_收集卡牌

CSP_收集卡牌

-----------废话连篇-------

体会到，当有一定基础之后，一道题最难的是有思路--理解题意后可以用已知的
工具（数据结构和算法，数学等）构建出思路.
有时候连题意都搞不懂，有时候连暴力都不会！有时候知道思路后将这种思路实现之后，
并不代表会了这道题，因为以后遇到相同类型的题目，甚至是除了背景题意完全一模一样
的题可能仍然不会做！！！
思路历程: 刚开始看着道题，尝试去推导公式，结果发现并不容易，感觉计算机解决的问题大多数是
比较模糊的形式，像那种分析解，而不是数值解，他可以去逼近，或者 通过枚举逐渐去靠近那个结果，
就像动态规划，为了求得结果，前面铺了很长的路，然而往往 这种方法却是最简便的，
其实 感觉动态规划如果一般用于求最优解，这个题更像递推
但是做题一定程度上并不是看这道题符合哪个算法的特征才去尝试 使用这个算法 ，
这也许是一种思路,但是更可靠的还是前面所说根据需要采用算法或数据结构：
首先，期望便是要求出每一种次数对应成功的概率，这是基调，即使有合并等操作会使求解更简便，
但先从这里开始思考；对于我抽取的这i次，有多少种，分别是哪些，这是比较直直观，有比较重要的信息，
那么这个时候确实需要对算法的条件有种敏锐感，（当然，表示状态不一定要用受限于数据范围的二进制压缩，
也可以使用数组来表示，但如果数据量不大的话，显然二进制的位运算会是操作更为便捷！），
看到16这么小，便可以联想到二进制状态压缩；
现在有了抽取次数和这些次数中包含的种类状态，那么是否可以完全确定抽取具体情况呢？
显然不能，而且十分不清晰，这就是这个题目最大的难点或者对于我来说比较难以跨过的一个坎，
但如果我知道抽取i次，i次中包含的种类的状态s的概率呢？那么就可以算出i次
在期望公式中的那部分（应该有概率论中的术语），如何求？直接推到公式肯定牛逼，而且我猜测可能只要数学能力强，
应该是可以推出来的，但我的数学能力不强，，，，
那么这个时候就涉及对信息的利用，或者说我去由之前求得的结果，或者这样想：
我抽取的第i次(抽到第k个)，可能在前i-1次抽取所构成的状态中（\(f_{ij}=f_{i-1j}*p_k\)），也可能不在(\(f_{ij}=f_{i-1(j-(1<<(k-1)))}*p_k\))，那么状态转移方程就是\(f_{ij}=(f[i-1][j]+f[i-1][j-(1<<(k-1))])*p_k\)
得到状态转移方程之后剩下的便是细节了. 那么怎么在一个完全类似但不一样的题型中能够想到这种递推的思路呢？我想，要对某一个具体操作进行分情况讨论，看分出来的几种情况能不能被简化求解，能不能由其他结果推出，能不能不断地被分解成非常简单的问题，这种逐层分解 的思路真的很重要！！！

#include
#define LOCAL
using namespace std;
int cont[1<<16];
long double f[85][1<<16];
long double p[20];
long double ans;
int read(){
    int s=0,f=1,c=getchar();
    while (c<'0' || c>'9' ) { if (c=='-') f=-1;c=getchar();}
    while (c>='0' && c<='9') { s=(s<<1)+(s<<3)+c-'0';c=getchar();}
    return f*s;
}


int main(){
    #ifdef LOCAL
    freopen("input.txt","r",stdin);
    #endif
    int n=read(),k=read();
    int S=(1<>=1;}
    }
    f[0][0]=1.0000000000;
    for (int i=1;i<=(n-1)*k+1;++i){
    // for (int i=1;i<=n*k;++i){
        // for (int j=1;j<=S && cont[j]<=i;++j){
        //注意这里虽然我的出发点是好的，但是cont[j]并不是递增的！！！而对于cont[j]>i的情况：
        //f[i][j]一定是0 （因为f[1][3]=f[0][3]+f[0][1]+f[0][3]+f[0][2]=0）因此不会对ans产生影响
        for (int j=1;j<=S;++j){
            for (int k=0;k