题目的意思是,给你m种元素,他们每个元素有n种不同的相位,如果相位相同则可以组合在一起发动一次魔法攻击(当然,一个也可以)。问你发动一次魔法至少有l种元素组合的概率?


首先我是自己想的去找这些可能性,总数比较好找,就是n^m,但是发现当l>m/2时会有重复,而且不好去除。所以就看了题解。。。大家都是按照自己的理解为球填色。

我是这样理解的,先画图:

blob.png

各个变量标识和题目意思相同,途中第一条黄色箭头代表发动一次3元素的攻击,第二条黄色箭头代表发动一次1元素的攻击(当然,我这样画两个相同的元素处在不同相位上肯定是不对的,只是为了方便大家理解,实际摆放的时候一个元素一个相位!!!)。

然后,由于正向推导不好推,那我们反过来求这个条件:

求当使用了i个相位,j个元素的时候,并且元素少于min(j, l)个的时候的值。(条件1)

然后用总情况减去这些不符合情况的就行。

递推式为:

dp[i][j] = ∑k->(0,min(j, l)) dp[i-1][j-k]*C[m-(j-k)][k];

这个递推式不好看啊,弱鸡表示目前的水平理解起来非常吃力。

我们假设的dp[i][j]为当前使用了j种元素放置在i种相位上时不符合情况的数目。

那么他当前可以用i个相位,j个元素。这等于使用了i-1个相位来放置j-k种元素并且这元素都符合条件1(为什么是j-k?因为你现在只有j种元素可以用,你还要保证k种元素处在相同相位上,所以你只能用剩下的j-k种元素填充条件1),现在多出来的一个相位用来放置这不满足的k种元素,使得他们在同一条线上发动攻击并且满足条件1的情况(这样就保证了所有的情况都是不满足大于l的)。这不满足的k从哪里来?就从m-(j-k)中来。(为什么?因为j-k已经是被i-1个相位使用过的元素了,所以你只能从剩下的元素里面找出k种来)。

也不知道我这样理解对不对,不对的话还请各位大神指点。


代码:

python2版本:

StatusAccepted
Time3550ms
Memory1396kB
Length881
LangPython (Python 2.7.3)

这里还需要复习一个公式:

C(n+1, m+1) = C(n, m)+C(n,  m+1)

没有这个公式先把C打表的话python可能会TLE,第一次6900过的,后来就一直GG。

C = [[0 for i in range(105)] for i in range(105)]
for i in range(0, 102):
    C[i][0]=1
    for j in range(1, i+1):
        C[i][j] = C[i-1][j] + C[i-1][j-1]
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)
while True:
    try:
        m, n, l = map(int, raw_input().split())
        if l > m:
            print('mukyu~')
        else:
            dp = [[0 for i in range(105)] for i in range(105)]
            dp[0][0] = 1
            for i in range(1, n+1):
                for j in range(1, m+1):
                    for k in range(0, min(j+1, l)):
                        dp[i][j] += dp[i-1][j-k]*C[m-(j-k)][k]
            tot = n ** m
            use = 0
            for i in range(1, n+1):
                use += dp[i][m]
            use = tot - use
            g = gcd(tot, use)
            print str(use/g)+'/'+str(tot/g)
    except:
        break

代码:

java版本:

StatusAccepted
Time1303ms
Memory22420kB
Length2018
LangJava (java 1.7.0)
public class Main {
    static final int maxn = 105;
    static BigInteger C[][] = new BigInteger[maxn][maxn];
    static BigInteger dp[][] = new BigInteger[maxn][maxn];
    static BigInteger N[] = new BigInteger[maxn];
    private static void Fac(BigInteger X[]) {
        X[0] = BigInteger.ONE;
        for (int i = 1; i < X.length; i++) {
            X[i] = X[i - 1].multiply(BigInteger.valueOf(i));
        }
    }
    private static void Comb(BigInteger X[][]) {
        for (int i = 0; i < maxn; i++) {
            for (int j = 0; j <= i; j++) {
                X[i][j] = N[i].divide(N[j]).divide(N[i - j]);
            }
        }
    }
    public static void main(String args[]) {
        Fac(N);
        Comb(C);
        int n, m, l;
        Scanner cin = new Scanner(System.in);
        while (cin.hasNext()) {
            m = cin.nextInt();
            n = cin.nextInt();
            l = cin.nextInt();
            if (l > m) {
                System.out.println("mukyu~");
                continue;
            }
            for (int i = 0; i < maxn; i++) {
                for (int j = 0; j < maxn; j++) {
                    dp[i][j] = BigInteger.ZERO;
                }
            }
            dp[0][0] = BigInteger.ONE;
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= m; j++) {
                    for (int k = 0; k <= Math.min(j, l - 1); k++) {
                        dp[i][j] = dp[i][j].add(dp[i - 1][j - k].multiply(C[m - (j - k)][k]));
                    }
                }
            }
            BigInteger all = BigInteger.valueOf(n).pow(m);
            BigInteger use = BigInteger.ZERO;
            for (int i = 1; i <= n; i++) {
                use = use.add(dp[i][m]);
            }
            use = all.subtract(use);
            BigInteger g = all.gcd(use);
            System.out.println(use.divide(g) + "/" + all.divide(g));
        }
    }
}