Do knapsack in reverse for subtract operation

https://atcoder.jp/contests/abc321/submissions/45887808

Notice that in 321-like numbers, each digit can appear at max once.
Once we fix the possible digits, there will be a unique 321 no.

So the maximum possible no of 321-like numbers are $$$2^{10}$$$, generate all of them, sort them, and print kth value in the sorted array.

You can do it natively.

a={""}
Loop for 9
a={"",9}
Loop for 8
a={"",8,9,98}
Loop for 7
a={"",7,8,87,9,97,98,987}

You can easily observe that in 321-number there are only one time appeared in any number of $$$9/8/7/6/5/4/3/2/1/0$$$. So if you want to enumerate all of $$$1024$$$ 321-number, you can enum $$$2^{10}$$$ states that each bit indicates this bit appears in the new number. And then just add them into one number.

I feel ashamed :( https://atcoder.jp/contests/abc321/submissions/45864906

It's sequence A009995 https://oeis.org/A009995

Just brute force. Loop every possible value and check the sum. Or you can use binary search as stupid as me. https://atcoder.jp/contests/abc321/submissions/45828848

You can assume the last added element is x(since the order of adding element doesn't matters) and think of it as "undo" the last operation of adding element x, so you do everything reversely.

dp[i] = number of ways of getting a subset sum of i. When removing x, you want to subtract the number of ways of obtaining i-x from dp[i] without using this x.

Backward knapsack algorithm. Because $$$dp_i\to dp_{i+x}$$$ and continues, we need to first delete the contribution of smaller i to make sure that the we won't count extra contribution of x.

Did you consider a[i] > p ?

In line 62, you need to check if (pos>0) ,then the code will get accepted.

You may try (or just read the editorial) of this problem, since they are almost the same abc213-g

You can try LOCG which shows a classical way to do counting on connectivity.

the question end, my poor minds.

How about this? Guess u r Chinese

Yes, the Japanese version is normally available immediately after the contest (like in this one) while the one in English can take a bit longer.