In your DP solution, you use a bitmask DP to represent the status. But I think maybe it is not necessary.

At first, I check every "special number" x, if n mod x != 0 or gcd(x, n/x) != 1 then we erase x from the special number list, because they will never show up in the result. Then I just run brute force algorithm. The complex will be O(S*2^K). And the implement can be as simple as brute force algorithm.

my code:

HASH <longlong,longlong> hash; for_each xinspecial numberifn mod x == 0andgcd(x, n / x) == 1 { for_each element iinhash {if(n mod (i->first * x) == 0) { hash[i->first * x] += i->second; } } hash[x] ++; }returnhash[n];

It is not difficult to proof that at every moment the size of hash will always not larger than 2^K.

for example, let's assume N = 2^1 * 3^3 * 5^2 * 7^4

and your bit status may be: 0 1 1 0

but I directly use their product: 3^3 * 5^2 as an status in my hashmap.]]>

Sorry again for not clarifying well what I meant. I will edit it and explain it further soon.]]>

Also I came up with a solution that uses only one array for dp. The code is this:

dp[0] = 1;for(inti = 0; i < possible.size(); i++) {intv = possible.get(i);for(intj = 0; j < dp.length; j++) {if((j & v) == 0) { dp[j | v] += dp[j]; } } }

So basically we keep in dp[bits] the number of sums by which we can reach bits combination. It works because (j | v) > j.

Nice problems by the way:)]]>

We will use your feedback when selecting editorial writers for the next SRMs.]]>

As it's in the Wiki, there's a possibility to improve it. It can be language correction, wording improvement or additional explanation in some parts, your additional comments, description of alternative solutions, etc. If you want to improve the wording of editorial writer or correct some language error, please feel free to put your change over the original text. And if you wish to add a comment or describe another approach, there's a section for this at the bottom of each problem.

Before editing, please be sure to check the following guidelines.

After approximately 1 month passes, we'll review the editorial once again, clean it a bit if necessary and make that version final (i.e. its editing will no longer be possible).]]>