gym/10446/C. 0689

ganking / 2023-08-10 / 原文

C. 0689

我们考虑i作为左端点的贡献。
我们强制翻转之后i这个点与原来不同，因为假如翻转之后i和原来相同，我们显然可以将这个翻转区间的左右端点往中间缩小1，也就是它会在更大的i被计算。

另一个问题，对于同一个i，不同的右端点是否会使得翻转之后相同，这也是不会的，

a b
a b b，因为如果他们相等，就会得出rev(a)=b的结论，跟我们前面的约束矛盾。

然后我们计算完了所有与原来的串不同的，它还有可能跟原来的相同，我们只需判断有没有0/8，或者两个69贴着即可。

#include<algorithm>
#include<cstdio>
#include<cstring>
#include<map>
#include<cmath>
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
using namespace std;
typedef long long ll;
const int N=1e6+5;
const ll mo=1e9+7;

char s[N];
ll tot,a[10];
int n,mt[10],c;
int main() {
   
    // #ifdef  LOCAL
//	       freopen("data.in","r",stdin);
    //     freopen("out.txt","w",stdout);
    // #endif
	int T;
	scanf("%d",&T);
	mt[0]=0;
	mt[6]=9;
	mt[9]=6;
	mt[8]=8;
	
	while (T--){
		scanf("%s",s+1);
		n=strlen(s+1);
		
		tot=0; 
		a[0]=a[6]=a[9]=a[8]=0;
		fd(i,n,1) {
			c=s[i]-'0';
			tot+=(ll)n-(ll)i-a[mt[c]];

			a[c]++;

			if (c!=0 && c!=8) tot++;
		}
		
		bool flag=0;
		fo(i,1,n) {
			if (s[i]=='8' || s[i]=='0') {
			flag=1;
			}
		}
		
		fo(i,1,n-1) {
			if (s[i]=='6' && s[i+1]=='9') flag=1;
			if (s[i]=='9' && s[i+1]=='6') flag=1;
		}
		if (flag) tot++;
		printf("%lld\n",tot);
	}
   
	

    return 0;
}