Codeforces1142D

做法：构建一个可以识别出合法串的自动机，然后就可以想办法在上边 dp 出答案。 首先，按照最直观的思路画一画这个自动机，找到每一个状态s如何推出它的后继t，然后通过状态的转移方式，找到等价的状态，想办法压缩这个自动机。我们令x的位数是d，ax是比x小的合法的数的数目，bx是位数是d的合法数中比x小的数的数目，cx是位数是d的合法数的数目。那么如果在x后添加一个数字s构成一个数字y，\(ay = ax - bx + cx + cal(ax-bx+1,bx) + s\), \(cal(a,b)\)是从a开始到b在%11下循环求和。 这个式子的\(ax-bx+cx\)就是在计算x的这种位数中最后一个数字的编号，\(cal(ax-bx+1,bx) + s\)就是当前层比y小的数的个数，那么有\(by = cal(ax-bx+1,bx) + s\)，\(cy = cal(ax-bx+1,cx)\)。观察这个转移的式子，如果 ax+11 会导致 ay + 11，by， cy，如果 bx+11 会导致 ay - 11 + 55, by + 55, cy 如果cx + 11 会导致 ay + 11， by，cy + 55。观察可以知道 (ax,bx,cx) 在 %11 意义下等价，后继的数量种类也一致，转移是有等价性的，于是对于这个三元组(ax,bx,cx)我们建出11 * 11 * 11的状态转移图，而一个子串如果可以在这个图上完成匹配，他就是合法的。显然，对于个位置i如果它的最长匹配距离是A，那么答案加A，设\(dp[i][j]\)表示以字符串的第i个位置为起点，自动机的节点j为起点，最长的匹配长度。就有\(dp[i][j] = dp[i+1][nxt(j,s[i+1])] + 1\)，其中 \(nxt(s,c)\) 指状态s后添加一个字符c走到的新状态，需要注意的一点是，对于任意一种串的位置i和状态s，dp[i][s]至少为1！！复杂度\(O(11^3 N)\)求解过程中需要理性取模。注意常数

#include 
    
     #define rep(i,a,b) for(int i = (a); i <= (b); ++i)#define per(i,a,b) for(int i = (a); i >= (b); --i)#define pb push_back#define Pll pair
     
      #define Pii pair
      
       #define Plp pair< ll,Pii >#define Pip pair< int,Pii >#define Ppp pair< Pii,Pii >#define x first#define y secondtypedef long long ll;const int N = 100100;using namespace std;int cal(int a, int n) {    return (( (a+a+n-1)*n/2 )%11+11)%11;}int n, dp[2][11][11][11];char s[N];ll ans;int main() {    scanf(" %s",s+1); n = strlen(s+1);    int f = 0;    per(i, n, 1) {        int now = s[i] - '0', nx = s[i+1] - '0';        rep(a, 0, 10) rep(b, 0, 10) rep(c, 0, 10) {            dp[f][a][b][c] = 1;            if(i == n) continue;            if( (a+1)%11 <= nx ) continue;            int ta = (a - b + 11 + c + cal(a-b+1,b) + nx) % 11;            int tb = (cal(a-b+1,b) + nx) %11 ;            int tc = cal(a-b+1,c);            dp[f][a][b][c] = dp[f^1][ta][tb][tc] + 1;        }        if(now) ans += dp[f][now-1][now-1][9];        f ^= 1;    }    printf("%lld\n",ans);        return 0;}