CF1142D Foreigner题解
前言：
题目含义真的好难理解呜呜。
遇到的 dp 套 dp 的第三题，所以深入进行了理解。
参考博文：https://www.cnblogs.com/AWhiteWall/p/16479483.html
题意简化：
先定义了不充分。
- 首先数字 $[1,9]$ 都不充分，注意没有 $0$。
- 当这个数字（设为 $x$）大于等于 $10$ 时，我们将它拆成两部分，一部分是他的最后一位，我们设为 $c$，另一部分为去掉末尾后的数字，我们设其为 $y$，那么需要满足 $y$ 是不充分的，并且 $y$ 在所有不充分数中的大小排名 $Rank_y$ 满足 $c < Rank_y \bmod 11$。
很复杂吧，我也觉得，所以要不不做了吧……
题解思路：
就像游园会那一道题一样，对于 dp 套 dp 我们先思考要是有个神犇，你需要他帮你设计什么自动机？
似乎就是一个较为普通的自动机吧，甚至没有神犇你都可以建立出来。大概就是 $f(i-1,j)$ 转移到 $f(i,nxt(j,s_i))$，其中 $nxt$ 表示的是大小标号为 $i$ 的数字在后面加上数字 $j$ 所达到数字的大小标号。
现在考虑怎么计算题目所需的答案。可以考虑每“增加”一个字符，就统计所有最后一位为该字符的子串
对于这个自动机每一次转移需要满足 $s_i<j\bmod11$。
然后接着考虑内部的 $nxt$ 怎么求解，我们假设原来的数字排名为 $k$，加入的数字为 $c$，
那么答案是：
$9+\sum_{i=1}^{k-1}(i\bmod11)+c+1$。
由于数据范围较大，这个状态也很有可能有很多个，于是就会达到 $O(n^2)$ 级别的时间复杂度。
现在时间复杂度需要优化，不然就是在前面的枚举开头字符中减少，不然就是在自动机那里减少。
我们看到有个 $x\bmod11$ 这个操作，又发现标号 $i$ 变为 $i\bmod11$ 对于答案不会产生影响，于是我们就想到优化状态数。
那么此时内部的转移，我们稍微利用一下等差数列（当然也可以直接预处理），答案就是：
$(9+k(k-1)/2+c+1)\bmod11$。
然后直接两个套就好了。
#include<bits/stdc++.h>
#define int long long
using namespace std;
int getnxt(int nowk,char c){
int nowc=c-'0';
return (9+((nowk*(nowk-1)/2)%11)+nowc+1)%11;
}
int f[100005][12];
signed main(){
ios::sync_with_stdio(false);
string s;
cin >> s;
int ans=0;
int n=s.size();
s=" "+s;
for(int i=1;i<=n;i++){
for(int j=s[i]-'0'+1;j<=10;j++){
f[i][getnxt(j,s[i])]+=f[i-1][j];
}
if(s[i]>'0'){
f[i][s[i]-'0']++;
}
for(int j=0;j<=10;j++){
ans+=f[i][j];
}
}
cout<<ans;
}