GYM100712I Bahosain and Digits

题解：

考虑枚举k后对k进行判定

设x[i]表示以i起始的k个数为一组需要一起做操作的次数

容易想到这构成了一个膜10意义下的同余方程，使得每个数加上$\sum\limits_{j=0}^{k-1} x[i-j]$后在膜10意义下相同

对k的判定也就是在确定这个方程是否有解

注意到我们可以枚举最后每个数相同后会变成哪个数(0~9)

这样也就可以计算得到x[1]

记个前缀和，再往下递推也就得到了其他的x[i]

最后再判定下最后的k个数能否通过之前几位的x[]变成我们枚举的那个数就好了

代码：

#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
    char c=getchar();bool f=0;x=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return x;
}
template<class t> inline void write(t x){
    if(x<0) putchar('-'),write(-x);
    else{if(x>9) write(x/10);putchar('0'+x%10);}
}

#define int long long

const int N=255;
int x[N],a[N],pre[N],n;
char s[N];

bool check(int len){
    for(x[1]=0;x[1]<=9;x[1]++){ //枚举x[1]
        int dig=(a[1]+x[1])%10; //计算得到最后都会变成哪个数
        pre[1]=x[1]; //记个前缀
        bool flag=1;
        for(int i=2;i<=n;i++){
            int cur=pre[i-1]; //求个sum
            if(i-len>0) cur-=pre[i-len];
            x[i]=((dig-a[i]-cur)%10+10)%10; //得到当前位的x[]
            if(i+len-1>n&&x[i]%10){ //如果最后k个数还要通过自身的操作来搞就是不合法的
                flag=0;
                break;
            }
            pre[i]=pre[i-1]+x[i];
        }
        if(flag) return 1;
    }
    return 0;
}

void doit(){
    scanf("%s",s+1);
    n=strlen(s+1);
    for(int i=1;i<=n;i++) a[i]=s[i]-'0';
    for(int i=n;i>=1;i--) if(check(i)){
        write(i);puts("");
        return ;
    }
}

signed main(){
    int t;
    read(t);
    while(t--) doit();
}