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

思路

首先考虑前缀和，设

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

的位数。

代码

CPP

#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;
}

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

文章操作

思路

代码

相关推荐

评论

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