卷积和

摘要:
题意:假定数字$x=d_0d_1d_2d_3...d_{n-1}$,则$F=sum_{i=0}^n{d_id_{n-i-1}}$求$sum_{i=L}^R{F}$的值。解法:只要求出$S=sum_{i=1}^{n-1}{F}$1. 先统计数位小于$n$的数位的。对于接下来剩下的$[frac{tot}{2}]$对,按照有一个确定,有两个确定,有三个确定分类。

题意:

假定数字$x = d_0d_1d_2d_3...d_{n-1}$,则$F(x) = sum_{i=0}^n{d_i d_{n-i-1}}$

求$sum_{i = L}^R {F(i)}$ 的值。

解法:

只要求出 $S(n) = sum_{i = 1}^{n-1} {F(i)}$

1. 先统计数位小于 $n$ 的数位的(分三 / 两种情况)。

2. 考虑枚举数位,假定当前还剩下$len$位没有确认,首先考虑如果长度为奇数,统计一下。

对于接下来剩下的 $[frac{tot}{2}]$ 对,按照有一个确定,有两个确定,有三个确定分类。

$O(log^2n)$

想清楚再写,QAQ

卷积和第1张卷积和第2张
#include <iostream>#include <cstdio>#include <cstring>

#define LL long long
#define P 1000000007LL
#define N 110

using namespacestd;

intnum[N], v[N];
LL cnt[10][10], power[N];

void solve(inttot)
{
    if(tot == 1)
    {
        for(int i = 1;i <= 9;i++)
            cnt[i][i]++;
    }
    else{
        for(int i = 1;i <= 9;i++)
            for(int j = 1;j <= 9;j++)
                cnt[i][j] += 2LL * power[tot-2] %P;
        if(tot == 2) return;
        if(tot & 1)
        {
            for(int i = 1;i <= 9;i++)
                cnt[i][i] += 9LL * power[tot-2] %P;
        }
        LL tmp = (tot-2)/2LL;
        for(int i = 1;i <= 9;i++)
            for(int j = 1;j <= 9;j++)
                cnt[i][j] += (2LL * tmp * power[tot-3] * 9LL) %P;
    }
}

void solve(int tot, intlen)
{
    if(tot & 1)
    {
        int tmp = tot/2 + 1;
        if(v[tmp] == -1)
        {
            for(int i = 1;i <= 9;i++)
                cnt[i][i] += power[len-1];
        }
        else cnt[v[tmp]][v[tmp]] +=power[len];
    }
    for(int i = 1;i <= tot/2;i++)
    {
        if(v[i] >= 0)
            cnt[v[i]][v[tot-i+1]] += 2ll * power[len] %P;
        else{
            if(v[tot-i+1] >= 0)
            {
                for(int j = 1;j <= 9;j++)
                    if(len > 0) cnt[j][v[tot-i+1]] += 2LL * power[len-1] %P;
            }
            else{
                for(int j = 1;j <= 9;j++)
                    for(int k = 1;k <= 9;k++)
                        cnt[j][k] += 2LL * power[len-2] %P;
            }
        }
    }
}

LL calc(LL n)
{
    memset(v, -1, sizeof(v));
    memset(cnt, 0, sizeof(cnt));
    int tot = 0;
    for(;n;n /= 10) num[++tot] = n%10;
    for(int i = 1;i < tot;i++) solve(i);
    for(int i = tot;i >= 1;i--)
    {
        for(int j = (i == tot? 1:0);j < num[i];j++)
            v[i] = j, solve(tot, i-1);
        v[i] =num[i];
    }
    LL ans = 0;
    for(int i = 1;i <= 9;i++)
        for(int j = 1;j <= 9;j++)
        {
            cnt[i][j] %=P;
            ans += (i * (LL)j * cnt[i][j]) %P;
        }
    return ans %P;
}

intmain()
{
    power[0] = 1;
    for(int i = 1;i < N;i++) power[i] = power[i-1] * 10LL %P;
    LL a, b;
    cin >> a >>b;
    cout << (calc(b+1) + P - calc(a)) % P <<endl;
    return 0;
}
View Code

免责声明:内容来源于网络,仅用于学习参考。如对内容有疑问,请及时联系本站处理。

上篇2017 jq 总结穆里尼奥之皮洛斯式胜利下篇

宿迁高防,2C2G15M,22元/月;香港BGP,2C5G5M,25元/月 雨云优惠码:MjYwNzM=

随便看看

linux性能评估-磁盘io概念实战篇

看起来python是个可疑进程。avgqu-sz:平均I/O队列长度。%util:一秒中有百分之多少的时间用于I/O操作,即被io消耗的cpu百分比备注:如果%util接近100%,说明产生的I/O请求太多,I/O系统已经满负荷,该磁盘可能存在瓶颈。如果avgqu-sz比较大,也表示有当量io在等待。观察iostat的最后一列,你会看到,磁盘vda的I/O使...

weblogic 的应用链接不上数据库报异常 Caused By: weblogic.common.ResourceException: Io exception: Connection reset 错误信息表示访问数据库异常,创建链接池失败

weblogic对此值注释:尝试建立数据库连接的间隔秒数。如果已设置此值且在创建数据源时数据库不可用,则在您指定的秒数之后,WebLogicServer将重新尝试在池中创建连接,并会不断尝试创建连接,直到创建成功。如果设置为0,则将禁用连接重试。...

Android开发者选项——Gpu呈现模式分析

对于Android用户来说,无论你用的什么品牌的手机,在开发者选项中都能发现“玄学曲线”的开关,之所以称其为玄学曲线,还是因为它被很多网友用于测试一个说不清道不明的东西——流畅度。说到玄学曲线其实它的真名叫做“ProfileGPURendering”,在中文安卓系统下译为“GPU显示配置文件”或“GPU呈现模式分析”等,根据不同厂商定制系统叫法稍有不同。...

ESXi挂载NFS共享存储

使用万兆交换机,ESXi使用NFS协议连接存储。本文介绍的是通过NFS协议挂载共享存储上的VS01卷,共享存储上已经赋予ESXi主机访问该卷的权限。...

windows下mstsc 远程Ubuntu 教程

为远程桌面控制设置Ubuntu 16.04的缺点是重新启动系统需要使用监视器登录系统。首先,我们将Ubuntu远程控制设置为允许远程连接,进入系统-˃首选项-˃桌面共享,或直接搜索桌面共享。如图所示,选中此项,然后选中安全项,并设置远程密码。...

安装gulp教程(整理)

所以安装nodejs。...