import java.math.BigInteger;
import java.util.LinkedHashMap;
class CountStrings2 {
// cache. key: N:M
private LinkedHashMap
<String, BigInteger
> sNM
= new LinkedHashMap
<String, BigInteger
>(); private final int P;
public CountStrings2(int P, int N, int M) {
this.P = P;
System.
out.
println("P=" + P
+ " N=" + N
+ " M=" + M
+ " S=" + S
); //outputCaches();
computeAsympt(N,M);
}
if (!sNM.containsKey(k)) {
if (N < M) {
} else {
for (int i= 1; i < M; i++) {
b = b.add(computeS(N-i, M));
}
}
sNM.put(k, b);
}
return sNM.get(k);
}
public void outputCaches() {
System.
out.
println("============== SNM ==== (P=" + P
+ ")"); for (String k
: sNM.
keySet()) { System.
out.
println("SNML " + k
+ "=" + sNM.
get(k
)); }
}
public void computeAsympt(int N, int M) { // asympotic approximation
double theta = 1.0 / P;
double probasympt
= Math.
pow(1 - Math.
pow(theta, M
- 1),N
* (1 - theta
)); double probexact = 1000000.0/cc.doubleValue();
System.
out.
printf("prob:%.4f asymptotic:%.4f\n" ,probexact, probasympt
); }
public static void main
(String[] args
) { new CountStrings2(4, 50, 5);
}
}
aW1wb3J0IGphdmEubWF0aC5CaWdJbnRlZ2VyOwppbXBvcnQgamF2YS51dGlsLkxpbmtlZEhhc2hNYXA7CgpjbGFzcyBDb3VudFN0cmluZ3MyIHsKCgkvLyBjYWNoZS4ga2V5OiBOOk0KCXByaXZhdGUgTGlua2VkSGFzaE1hcDxTdHJpbmcsIEJpZ0ludGVnZXI+IHNOTSA9IG5ldyBMaW5rZWRIYXNoTWFwPFN0cmluZywgQmlnSW50ZWdlcj4oKTsKCXByaXZhdGUgZmluYWwgaW50IFA7CgoJcHVibGljIENvdW50U3RyaW5nczIoaW50IFAsIGludCBOLCBpbnQgTSkgewoJCXRoaXMuUCA9IFA7CgkJQmlnSW50ZWdlciBTID0gY29tcHV0ZVMoTiwgTSk7CgkJU3lzdGVtLm91dC5wcmludGxuKCJQPSIgKyBQICsgIiBOPSIgKyBOICsgIiBNPSIgKyBNICsgIiBTPSIgKyBTKTsKCQkvL291dHB1dENhY2hlcygpOwoJCWNvbXB1dGVBc3ltcHQoTixNKTsKCX0KCglwcml2YXRlIEJpZ0ludGVnZXIgY29tcHV0ZVMoaW50IE4sIGludCBNKSB7CgkJU3RyaW5nIGsgPSBOICsgIjoiICsgTTsKCQlpZiAoIXNOTS5jb250YWluc0tleShrKSkgewoJCQlCaWdJbnRlZ2VyIGIgPSBCaWdJbnRlZ2VyLlpFUk87CgkJCWlmIChOIDwgTSkgewoJCQkJYiA9IEJpZ0ludGVnZXIudmFsdWVPZihQKS5wb3coTik7CgkJCX0gZWxzZSB7CgkJCQlmb3IgKGludCBpPSAxOyBpIDwgTTsgaSsrKSB7CgkJCQkJYiA9IGIuYWRkKGNvbXB1dGVTKE4taSwgTSkpOwoJCQkJfQoJCQkJYiA9IGIubXVsdGlwbHkoQmlnSW50ZWdlci52YWx1ZU9mKFAtMSkpOwoJCQl9CgkJCXNOTS5wdXQoaywgYik7CgkJfQoKCQlyZXR1cm4gc05NLmdldChrKTsKCX0KCglwdWJsaWMgdm9pZCBvdXRwdXRDYWNoZXMoKSB7CgkJU3lzdGVtLm91dC5wcmludGxuKCI9PT09PT09PT09PT09PSBTTk0gPT09PSAgKFA9IiArIFAgKyAiKSIpOwoJCWZvciAoU3RyaW5nIGsgOiBzTk0ua2V5U2V0KCkpIHsKCQkJU3lzdGVtLm91dC5wcmludGxuKCJTTk1MICIgKyBrICsgIj0iICsgc05NLmdldChrKSk7CgkJfQoJfQoKCXB1YmxpYyB2b2lkIGNvbXB1dGVBc3ltcHQoaW50IE4sIGludCBNKSB7IC8vIGFzeW1wb3RpYyBhcHByb3hpbWF0aW9uIAoJCWRvdWJsZSB0aGV0YSA9IDEuMCAvIFA7CgkJZG91YmxlIHByb2Jhc3ltcHQgPSAgTWF0aC5wb3coMSAtIE1hdGgucG93KHRoZXRhLCBNIC0gMSksTiAqICgxIC0gdGhldGEpKTsKCQlCaWdJbnRlZ2VyIFMgPSBjb21wdXRlUyhOLCBNKTsKCQlCaWdJbnRlZ2VyIGNjID0gQmlnSW50ZWdlci52YWx1ZU9mKFApLnBvdyhOKS5tdWx0aXBseShCaWdJbnRlZ2VyLnZhbHVlT2YoMTAwMDAwMCkpLmRpdmlkZShTKTsKCQlkb3VibGUgcHJvYmV4YWN0ID0gMTAwMDAwMC4wL2NjLmRvdWJsZVZhbHVlKCk7CgkJU3lzdGVtLm91dC5wcmludGYoInByb2I6JS40ZiBhc3ltcHRvdGljOiUuNGZcbiIgLHByb2JleGFjdCwgcHJvYmFzeW1wdCk7Cgl9CgoJcHVibGljIHN0YXRpYyB2b2lkIG1haW4oU3RyaW5nW10gYXJncykgewoJCW5ldyBDb3VudFN0cmluZ3MyKDQsIDUwLCA1KTsKCgl9Cn0=