题解：P13447 [GCJ 2009 #3] Interesting Ranges

PizzaYY · 2025-11-20 19:20:27 · 题解

思路

首先考虑前缀和，设 s_i 表示 1\sim i 中回文数的个数对 2 取模的值，那么区间 [l,r] 是一个好区间当且仅当 s_{l-1}=s_r。现在要求 [L,R] 有多少个子区间是好区间，若求出 s_{L-1\sim R} 中有多少个 0 和 1（记为 cnt_0,cnt_1），那么答案就是 \binom{cnt_0}2+\binom{cnt_1}2。

显然求出 cnt_0 和 cnt_1 中任意一个即可知道另一个的值，下面考虑如何求其中的一个。

差分为 1\sim R 的个数减去 1\sim L-2 的个数，问题转化为求一个前缀的 cnt_0 或 cnt_1。

若第 i 个回文数为 a_i，那么 [a_i,a_{i+1}) 这个区间的 s 的取值是相等的，对 cnt_{0/1} 的贡献即为 a_{i+1}-a_i。考虑从这方面入手。

设 a_i 前半段的数为 x，发现对于 a_i 位数相同的时候，大部分 a_{i+1}-a_{i} 是相等的（例如 12421-12321=11411-11311=100,123321-122221=114411-113311=1100），问题出现在 x 最后一位为 9 时会往前进位（例如 13031-12921=110）。

考虑如何规避最后一位是 9 的情况：

• 若 x 位数大于等于 2，设 x 除去最后一位的数 y，发现我们可以统计 y 后跟上一个 0\sim 9 中偶数的答案，这样就不会出现最后一位是 9 的情况。然后发现每个 y 对应的回文数个数为偶数，所以对于其他的 y，仍然只需要记录最后一位是偶数的情况；
• 否则，这个回文数不会超过 100，直接暴力枚举即可。

发现我们现在记录的个数相当于 cnt_1，就可以预处理 f_i 表示 i 位回文数的答案。

若 i 为奇数，那么两个回文数的间隔即为 10^{\frac{i-1}2}，否则为 10^{\frac i2}+10^{\frac i2-1}。然后考虑 x 最后一位是偶数的个数，显然为 5\times(10^{\lfloor\frac {i-1}2\rfloor}-10^{\lfloor\frac {i-1}2\rfloor-1})。f_i 就是这两个数的乘积。特别的，对于 i\le 2，需要暴力枚举。

此时考虑计算 1\sim x 这个前缀的 cnt_1。设 x 的位数为 len，位数小于 len 可以直接使用预处理的 f 数组。

对于位数等于 len 的情况，经典的，枚举回文数的前一半和 x 的最长公共前缀长度，钦定下一位必须小于 x 的那一位，此时分两种情况讨论：

• 若最长公共前缀长度小于 \lfloor\frac{len-1}2\rfloor，最后一定剩下一位可以随便填，那么最后一位就可以取到 0\sim 9 的任意一个偶数。对答案的贡献计算方式和 f 类似；
• 否则，最多剩下一位，暴力枚举计算贡献即可。

记得对于 len\le 2 的情况特殊处理一下。

时间复杂度 O(len)，其中 len 表示 R 的位数。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6+5,mod = 1e9+7,inv2 = (mod+1)>>1;
int pw[N],f[N],sum[N];
inline int get(int x){x = (x+mod)%mod;return x*(x-1)%mod*inv2%mod;}
inline int get(string &s)
{
    int res = 0;
    for(int i = 0;i<s.size();i++) (res+=pw[s.size()-i-1]*(s[i]-'0'))%=mod;
    return res;
}
string s,t;
inline int work()
{
    if(s.size()&&s[0]<'0') return 0;
    if(s.size()==0) return 0;
    if(s.size()==1) return sum[s[0]-'0'];
    if(s.size()==2)
    {
        int now = (s[0]-'0')*10+s[1]-'0';
        return sum[now];
    }
    int n = s.size();
    int res = 0;
    for(int i = 0;i<n;i++) (res+=f[i])%=mod;
    bool fl = 1;
    int w = pw[n/2];
    if(n%2==0) (w+=pw[n/2-1])%=mod;
    for(int i = 0;i<(n-1)/2;i++)
    {
        int x = pw[(n-2*(i+1)-1)/2];
        (res+=x*w%mod*5*(s[i]-'0'-(i==0)))%=mod;
    }
    t.resize(n);
    for(int i = 0;i<10;i+=2)
    {
        for(int j = 0;j<(n-1)/2;j++)
            t[j] = t[n-j-1] = s[j];
        t[(n-1)/2] = i+'0';
        if(n%2==0) t[n/2] = i+'0';
        bool fl1 = (t<=s);
        t[(n-1)/2]++;
        if(n%2==0) t[n/2]++;
        bool fl2 = (t<=s);
        if(fl2)
        {
            (res+=w)%=mod;
        }
        else if(fl1)
        {
            t[(n-1)/2]--;
            if(n%2==0) t[n/2]--;
            (res+=get(s)-get(t)+1+mod)%=mod;
        }
        else break;
    }
    return res;
}
inline void solve()
{
    cin>>s;
    s[s.size()-1]-=2;
    int p = s.size()-1;
    while(p>0&&s[p]<'0')
    {
        s[p]+=10;
        s[p-1]--;
    }
    if(s[0]=='0') s.erase(s.begin());
    int ans = mod-work(),len = mod-get(s);
    cin>>s;
    (ans+=work())%=mod;
    (len+=get(s))%=mod;
    cout<<(get(ans)+get(len-ans))%mod<<'\n';
}
signed main()
{
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    pw[0] = 1;
    for(int i = 1;i<N;i++) pw[i] = pw[i-1]*10%mod;
    int now = 0;
    for(int i = 1;i<100;i++)
    {
        if(i<10||i%11==0) now^=1;
        sum[i] = sum[i-1]+now;
    }
    f[1] = sum[9];
    f[2] = sum[99]-sum[9];
    for(int i = 3;i<N;i++)
    {
        int cnt = (pw[(i-1)/2]-pw[(i-1)/2-1]+mod)%mod,w = pw[i/2];
        if(i%2==0) (w+=pw[i/2-1])%=mod;
        f[i] = cnt*w%mod*5%mod;
    }
    int T;cin>>T;
    for(int _ = 1;_<=T;_++)
    {
        cout<<"Case #"<<_<<": ";
        solve();
    }
    return 0;
}