卷积和

摘要:
题意:假定数字$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=

随便看看

k8s集群上删除pod及service

删除k8s集群中的pod:找到pod的名称空间,并根据名称空间删除pod1。首先删除pod2,然后删除相应的部署。否则,删除pod是无用的。您还将看到pod,因为deployment.yaml文件中定义的副本数如下:delete the pod[root@test2~]#kubectlgetpod-njenkinsNAMEREADYSTATUSRESTART...

WPF知识点全攻略13- 绘图

行&lt;线条X1=“10”Y1=“100”X2=“260”Y2=“100“Stroke=“黑色”StrokeDashArray=“5”StrokeThickness=“2”&gt;线冲程&gt;矩形&lt;矩形边距=“5”笔划=“黑色”高度=“100”宽度=“100“&gt;&lt;&书信电报,...

"SQLserver 事务日志已满"解决方法

如果不够,备份后换个地方存[注:tempdb你数据库名称。...

Qt使用镜像源快速安装与更新

如果我们选择在线安装模式,那就更麻烦了,因为下载速度一般不慢。事实上,在中国,Qt图片来源很多,但很少有人使用。原因是Qt图像源做得不好。如果我们导入它,它将自动链接到官方图像源。因为它已经从官方来源同步,没有更改,所以我们无法逐个添加补丁,这太麻烦了。好吧,让我停止胡说八道。让我告诉你如何使用国产Qt图像源。...

Github仓库重命名

1.在Github上重命名仓库,转到您自己的仓库,找到Setting标记,然后单击Options中的Settings以设置Repositoryname。2.修改本地仓库信息。由于远程仓库名称已更改,因此本地对应的仓库名称也应更改。1.检查当前远程仓库的信息$gitremote-v列出了所有远程仓库信息,包括网站地址。2.修改本地对应远程仓库的地址。修改后,使...

季调方法论

理论与实践“季节性调整原则季节性调整方法分析季节性调整实践中遇到的问题只有同比数据缺少春节效应阅读”通货膨胀的季节性调整和预测模型“通货膨胀预测CPI的季节性调整具有明显的春节效应考虑春节效应的季节性调节春节效应的确定CPI的季节调整基于季节性调整后CPI的预测通货膨胀的修正(应对非洲猪瘟的影响)修订并扩大了季度调查方法的CPI预测读数...