[数位+状压][DP] codeforces 1073E Segment Sum

这场前四个的难度跟后面的完全不是一个div的。。。abcd都很容易出的那种。。

然后今天这个E,怎么说,思路很容易想到,一看就是数位dp,然后也比较容易发现需要保存已经用过的数字集合,所以一个下标是状压的二进制。

然后我以为就这么开心的做了,但是操蛋的是,这个需要考虑很多前导0的情况。。然后我就写炸了。。。调了巨久。。。基本上后来就是各种特殊情况往上加,呵呵,虽然最后1y但是对我来说感觉做出来跟没做出来已经没什么区别了,浪费了n个小时(本来该看射频的啊啊啊啊啊啊啊啊凉凉

丑陋的各种特判代码先放这儿,等我去扒一扒前排大佬代码(其实cf那场也就不到100人A了这个题

#include

using namespace std;

const int maxn=1e5+5;
const int mod=998244353;
typedef long long LL;


LL vis[30][(1<<10)+1];
int K;
LL kpow[30],p10[30];
void init()
{
    kpow[0]=1;
    for(int i=1; i<=20; i++)
        kpow[i]=kpow[i-1]*K%mod;
    p10[0]=1;
    for(int i=1; i<=20; i++)
        p10[i]=p10[i-1]*10%mod;
}


LL cnt[25][1027];
LL f(int n,int S,LL& tot)
{
    if(vis[n][S])
    {
        tot=(tot+cnt[n][S])%mod;
        return vis[n][S];
    }

    int hm=__builtin_popcount(S);
    if(hm>K)
        return 0;
    LL tp=0;
    if(hm==K)
    {

        for(int w=1; w<=n; w++)
            for(int i=0; i<10; i++)
                if(S&(1<1; i--) //deal with the prefix 0s
    {
        for(int j=1; j<10; j++)
        {
            LL tmp=f(i-1,(1<=10)
        ans+=10,fuck+=45;//n==1
    int cc[30]= {0};
    for(int i=dig; i>1; i--)
    {
        int j;
        LL tmp;
        for(j= i==dig?1:0; j>l>>r>>K;
    init();
    LL t1,t2,b1,b2;
    int a1=pre(l-1,t1);
    int a2=pre(r,t2);
    cout<<(t2-t1+mod)%mod;

    return 0;
}

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据