srm 592 dv2 1000pt

我真是个傻逼。。这题想了好长时间，最后还是看别人的代码有了点灵感。写的时候发现位运算那点写的各种不利索。。又模仿了一下别人的代码。。

。。先说一下思路好了。。每个数最多有16位，也就是大约能搞出6万个数，最多有100个数，问题就转化为在这100个集合里每个集合找出一个数组成一个不降的序列。根据苏神教我的，这种有大量重复的搜索就是其实就是dp啦。dp[i][j]表示长度为i，最后一个数是j的序列有几种方法，就有dp[i][j] = Σdp[i-1][k(k<=j)]（嘛。。用滚动数组去掉一维i）。

我们可以先把每个集合里的这6w个数排一下序，找k的时候就可以用一个指针p，慢慢往后移了。

代码如下

# include <iostream>
# include <cstdio>
# include <algorithm>
# include <string>
# include <vector>
# include <sstream>
# include <cstring>
# define MOD 1000000007
using namespace std;
typedef long long ll;
ll v[2][66000],dp[2][66000];
class LittleElephantAndArray
{
public:
    int getNumber(long long A, int N)
    {
        string str;
        int i,pre,j,cnt;
        for (i=0;i<=N;++i)
        {
            stringstream ss;
            ss<<(A+i);
            ss>>str;
            int len = str.size(),k;cnt = 0;
            for (j=1;j<(1<<len);++j)
            {
                ll num = 0;
                for (k=0;k<len;++k)
                    if (j&(1<<k))
                        num = num*10 + (str[k]-'0');
                v[1][cnt++] = num;
            }
            sort(v[1],v[1]+cnt);
            if (i)
            {
                int p = 0,t = 0;
                for (j=0;j<cnt;++j)
                {
                    while (p<pre&&v[0][p]<=v[1][j])
                    {
                        t += dp[0][p++];
                        t %= MOD;
                    }
                    dp[1][j] = t;
                }
            }
            else
            {
                for (j=0;j<cnt;++j)
                    dp[1][j] = 1;
            }
            pre = cnt;
            memcpy(dp[0],dp[1],sizeof(dp[1]));
            memcpy(v[0],v[1],sizeof(v[1]));
        }
        ll ans = 0;
        for (i=0;i<cnt;++i)
        {
            ans += dp[0][i];
            ans %= MOD;
        }
        return ans;
    }    
};