国内做航模比较好的网站,网站项目怎么做的,网站开发的基本技术路线,网站结构 扁平结构 树状结构Codeforces1142D 做法#xff1a;构建一个可以识别出合法串的自动机#xff0c;然后就可以想办法在上边 dp 出答案。 首先#xff0c;按照最直观的思路画一画这个自动机#xff0c;找到每一个状态s如何推出它的后继t#xff0c;然后通过状态的转移方式#xff0c;找到等价… Codeforces1142D 做法构建一个可以识别出合法串的自动机然后就可以想办法在上边 dp 出答案。 首先按照最直观的思路画一画这个自动机找到每一个状态s如何推出它的后继t然后通过状态的转移方式找到等价的状态想办法压缩这个自动机。我们令x的位数是dax是比x小的合法的数的数目bx是位数是d的合法数中比x小的数的数目cx是位数是d的合法数的数目。那么如果在x后添加一个数字s构成一个数字y\(ay ax - bx cx cal(ax-bx1,bx) s\), \(cal(a,b)\)是从a开始到b在%11下循环求和。 这个式子的\(ax-bxcx\)就是在计算x的这种位数中最后一个数字的编号\(cal(ax-bx1,bx) s\)就是当前层比y小的数的个数那么有\(by cal(ax-bx1,bx) s\)\(cy cal(ax-bx1,cx)\)。观察这个转移的式子如果 ax11 会导致 ay 11by cy如果 bx11 会导致 ay - 11 55, by 55, cy 如果cx 11 会导致 ay 11 bycy 55。观察可以知道 (ax,bx,cx) 在 %11 意义下等价后继的数量种类也一致转移是有等价性的于是对于这个三元组(ax,bx,cx)我们建出11 * 11 * 11的状态转移图而一个子串如果可以在这个图上完成匹配他就是合法的。显然对于个位置i如果它的最长匹配距离是A那么答案加A设\(dp[i][j]\)表示以字符串的第i个位置为起点自动机的节点j为起点最长的匹配长度。就有\(dp[i][j] dp[i1][nxt(j,s[i1])] 1\)其中 \(nxt(s,c)\) 指状态s后添加一个字符c走到的新状态需要注意的一点是对于任意一种串的位置i和状态sdp[i][s]至少为1复杂度\(O(11^3 N)\)求解过程中需要理性取模。注意常数 #include bits/stdc.h
#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 pairll,ll
#define Pii pairint,int
#define Plp pair ll,Pii
#define Pip pair int,Pii
#define Ppp pair Pii,Pii
#define x first
#define y second
typedef long long ll;
const int N 100100;using namespace std;
int cal(int a, int n) {return (( (aan-1)*n/2 )%1111)%11;
}
int n, dp[2][11][11][11];
char s[N];
ll ans;int main() {scanf( %s,s1); n strlen(s1);int f 0;per(i, n, 1) {int now s[i] - 0, nx s[i1] - 0;rep(a, 0, 10) rep(b, 0, 10) rep(c, 0, 10) {dp[f][a][b][c] 1;if(i n) continue;if( (a1)%11 nx ) continue;int ta (a - b 11 c cal(a-b1,b) nx) % 11;int tb (cal(a-b1,b) nx) %11 ;int tc cal(a-b1,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;
} 转载于:https://www.cnblogs.com/RRRR-wys/p/10668310.html
