典型的数位dp，但是边界处理：当最后一位的时候需要特判

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 998244353;
int f[203][11][11][11];
//位数，首，末，余
void init() {

for(int j=1;j<=9;j++){
   for(int i=0;i<=9;i++){
           f[2][i][j][i%j]++;
       }
   }
   for(int i=2;i<=201;i++){
       for(int j=0;j<=9;j++){
           for(int z=1;z<=9;z++){
            for(int y=0;y<z;y++){
             for(int k=0;k<=9;k++){
                f[i+1][j][z][(y+k)%z]=(f[i+1][j][z][(y+k)%z]+f[i][j][z][y])%mod;
             }   
            }
           }
       }
   }
}

int dp(vector<int> &a,int op) {
   int k=a[0];
   int last=0;
   int n=a.size();
   int res=0;
   for(int i=n;i>=1;i--){
       int x=a[i-1];
       if(i>1){
       for(int j= (i==n?1:0) ;j<x;j++){
           for(int z=1;z<=9;z++){
               for(int y=0;y<z;y++)
            if((last+y)%z==0){
                //cout<<"pp\n";
           res=(res+f[i][j][z][y])%mod;}
       }
       }

       last=(x+last);
       }
       if(i==1){
            for(int j=1;j<x;j++){
        if((last)%j==0){
               // cout<<"pp\n";
           res=(res+1)%mod;
            }}
           if(op&&k&&last%k==0) res=(1+res)%mod;
       }
   }
   for(int i=n-1;i>=2;i--){
       for(int j=1;j<=9;j++)
       for(int z=1;z<=9;z++)
       res=(res+f[i][j][z][0])%mod;
   }
   //cout<<res<<"\n";
   return res;
}

signed main() {
    init();
    string l, r;
    cin >> l >> r;
    vector<int> ll, rr;
    reverse(l.begin(), l.end());
    reverse(r.begin(), r.end());
    for (auto c : l) {
        ll.push_back(c - '0');
    }
    for (auto c : r) {
        rr.push_back(c - '0');
    }

    cout << (dp(rr,1) - dp(ll,0) + mod) % mod;
    return 0;
}

贡献求和，枚举每一个位作为i2，i3，然后拆位和左右计算，再乘以组合左右搭配数，也可以画图找搭配图规律

从图上找规律的题解

//枚举每个点作为i2和i3
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 998244353, N = 1e5 + 5;

int pre[N][33], sur[N][33];
int a[N];
int n;

signed main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }

     for (int i = 1; i <= n; ++i) {
        for (int b = 0; b <= 31; ++b) {
            pre[i][b] = pre[i-1][b] + ((a[i] >> b) & 1);
        }
    }

     for (int i = n; i >= 1; --i) {
        for (int b = 0; b <= 31; ++b) {
            sur[i][b] = sur[i+1][b] + ((a[i] >> b) & 1);
        }
    }

    int ans = 0;
    for (int b = 0; b <= 31; ++b) {
        int v = (1LL << b) % mod;
        int sum_left = 0, sum_right = 0;

         for (int j = 2; j <= n-2; ++j) {
            int bit = (a[j] >> b) & 1;
            int cnt = (bit == 0) ? pre[j-1][b] : (j-1 - pre[j-1][b]);
            int m = n - j;
            int comb = (m >= 2) ? (m * (m - 1) / 2) % mod : 0;
            sum_left = (sum_left + cnt * comb) % mod;
        }

         for (int i = 3; i <= n-1; ++i) {
            int bit = (a[i] >> b) & 1;
            int cnt = (bit == 0) ? sur[i+1][b] : ( (n - i) - sur[i+1][b] );
            int m = i - 1;
            int comb = (m >= 2) ? (m * (m - 1) / 2) % mod : 0;
            sum_right = (sum_right + cnt * comb) % mod;
        }

        ans = (ans + (sum_left + sum_right) * v % mod) % mod;
    }

    cout << (ans % mod + mod) % mod << endl;
    return 0;
}

整数花费隔板法之有限制版本

1，调整首位取值范围，使得都从0开始
2，计算最大非法数
3，容斥定理
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mod = 998244353;
const int max_fact = 2e6 + 10;  

ll fact[max_fact], inv_fact[max_fact];  

ll pow_mod(ll a, ll b) {
    ll res = 1;
    for (; b; b >>= 1, a = a * a % mod)
        if (b & 1) res = res * a % mod;
    return res;
}

void precompute() {
    fact[0] = 1;
    for (int i = 1; i <= max_fact; ++i)
        fact[i] = fact[i - 1] * i % mod;
    inv_fact[max_fact] = pow_mod(fact[max_fact], mod - 2);
    for (int i = max_fact - 1; i >= 0; --i)
        inv_fact[i] = inv_fact[i + 1] * (i + 1) % mod;
}

ll comb(int n, int k) {
    if (n < 0 || k < 0 || n < k) return 0;
    return fact[n] * inv_fact[k] % mod * inv_fact[n - k] % mod;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    precompute();  

    int N, M;
    cin >> N >> M;


    if (N == 1) {
        cout << (M >= 1 && M <= 9 ? 1 : 0) << endl;
        return 0;
    }

    if (M < 1 || M > 9 * N) {
        cout << 0 << endl;
        return 0;
    }

    ll ans = 0;

    // 遍历第一位的违反次数（0或1次）
    for (int a = 0; a <= 1; ++a) {
        // 计算其他位最多可以违反的次数
        int max_b = (M - 1 - 9 * a) / 10;
        // 遍历其他位的违反次数
        for (int b = 0; b <= max_b; ++b) {
            int total_sub = 9 * a + 10 * b; // 总共减去的数值
            if (total_sub > M - 1) continue; // 跳过非法情况
            int rem = M - 1 - total_sub;     // 剩余需要分配的和
            ll c_comb = comb(1, a) * comb(N - 1, b) % mod; // 选择违反的位置
            ll c_rem = comb(rem + N - 1, N - 1);          // 剩余和的解数
            int sign = (a + b) % 2 == 0 ? 1 : -1;         // 容斥符号
            ans = (ans + sign * c_comb * c_rem % mod + mod) % mod; // 累加项
        }
    }

    cout << ans << endl;
    return 0;
}

这道题可以乱搞出来，但是争取的思路的，计算每个数字在每个位置出现的期望然后来乘
//正确思路

乱搞
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5+5;
int mod =998244353;
int fac[N], ifac[N];
int q(int a, int k, int mod) {
    int res = (int)1 % mod;
    while (k) {
        if (k & (int)1)
            res = res * a % mod;
        k >>= (int)1;
        a = a * a % mod;
    }
    return res;
}
int inv(int x) {
    return q(x, mod - 2, mod);
}
void init(int n) {
    for (int i = 0; i <= n; i++) {
        fac[i] = ifac[i] = 0;
    }
    fac[0] = 1;
    for (int i = 1; i <= n; i++) {
        fac[i] = fac[i - 1] * i % mod;
    }
    ifac[n] = inv(fac[n]);
    for (int i = n - 1; i >= 0; i--) {
        ifac[i] = ifac[i + 1] * (i + 1) % mod;
    }
}

int C(int n, int m) {
    if (m < 0 || m > n || n < 0) {
        return 0;
    }
    return fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}
int A(int n, int m) {
    if (m < 0 || m > n || n < 0) {
        return 0;
    }
    return fac[n] * ifac[n - m] % mod;
}
int a[10];
int sum=0;
int ans=0;
int pre=1;
int pre_sum[N];
signed main()
{
  init(100001);
  for(int i=1;i<=9;i++){
    cin>>a[i];
    sum+=a[i];
  }

  pre_sum[1]=1;
  for(int i=2;i<=100001;i++){
    pre=(pre*10)%mod;
    pre_sum[i]=(pre_sum[i-1]+pre)%mod;
  }
  for(int i=1;i<=9;i++){

      int iv=1;
      for(int j=1;j<=9;j++){
          if(i==j) continue;
          iv=(iv*A(a[j],a[j]))%mod;
      } // cout<<i*(pre_sum[sum])*A(sum-1,sum-a[i])%mod*inv(iv)%mod<<"\n";
      //固定一个 i 的操作已经隐含了从 a[i] 个实例中选择一个的过程。
     ans=(ans+i*(pre_sum[sum])*A(sum-1,sum-a[i])%mod*inv(iv)%mod)%mod;
  }
  cout<<ans<<"\n";
}

靠，允许为空的隔板法板子题

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5+5;
int mod =998244353;
int fac[N], ifac[N];
int q(int a, int k, int mod) {
    int res = (int)1 % mod;
    while (k) {
        if (k & (int)1)
            res = res * a % mod;
        k >>= (int)1;
        a = a * a % mod;
    }
    return res;
}
int inv(int x) {
    return q(x, mod - 2, mod);
}
void init(int n) {
    for (int i = 0; i <= n; i++) {
        fac[i] = ifac[i] = 0;
    }
    fac[0] = 1;
    for (int i = 1; i <= n; i++) {
        fac[i] = fac[i - 1] * i % mod;
    }
    ifac[n] = inv(fac[n]);
    for (int i = n - 1; i >= 0; i--) {
        ifac[i] = ifac[i + 1] * (i + 1) % mod;
    }
}

int C(int n, int m) {
    if (m < 0 || m > n || n < 0) {
        return 0;
    }
    return fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}
int A(int n, int m) {
    if (m < 0 || m > n || n < 0) {
        return 0;
    }
    return fac[n] * ifac[n - m] % mod;
}
int n,m;
void solve(){
  cin>>n>>m;
  cout<<C(n+m-1,m-1)<<"\n";

}
signed main()
{
  init(200001);
 int t;
 cin>>t;
 while(t--){
   solve();
 }


}

质因数分解和简单容斥

大数范围内找互质个数。直接采用质因数分解后采用容斥

发现枚举因数的过程中，会有因数被重复枚举。我们可以转换顺序，先枚举因数，再枚举每倍数。这样的时间复杂度为O(nlnn)；调和级数优化

预处理好移动的方向后开启状态dijk，点有坐标和使用和跳跃次数，距离也是

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

struct Node {
    int x, y;
    int blocks, steps;
    bool operator<(const Node& other) const {
        if (blocks != other.blocks) return blocks > other.blocks;
        return steps > other.steps;
    }
};

struct Distance {
    int blocks = INT_MAX;
    int steps = INT_MAX;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, m, k;
    cin >> n >> m >> k;
    vector<string> grid(n);
    int start_x = -1, start_y = -1, end_x = -1, end_y = -1;

    // 读取网格并定位起点和终点
    for (int i = 0; i < n; ++i) {
        cin >> grid[i];
        for (int j = 0; j < m; ++j) {
            if (grid[i][j] == 's') {
                start_x = i;
                start_y = j;
                grid[i][j] = '1'; // 起点位置视为有方块
            } else if (grid[i][j] == 't') {
                end_x = i;
                end_y = j;
                grid[i][j] = '1'; // 终点位置视为有方块
            }
        }
    }

    // 预处理所有可能的跳跃方向 (dx, dy)
    vector<pair<int, int>> dirs;
    int k_sq = k * k;
    for (int dx = -k; dx <= k; ++dx) {
        for (int dy = -k; dy <= k; ++dy) {
            if (dx == 0 && dy == 0) continue; // 排除原地跳跃
            if (dx * dx + dy * dy <= k_sq) {
                dirs.emplace_back(dx, dy);
            }
        }
    }

    // 初始化距离数组
    vector<vector<Distance>> dist(n, vector<Distance>(m));
    dist[start_x][start_y] = {0, 0};
    priority_queue<Node> pq;
    pq.push({start_x, start_y, 0, 0});

    while (!pq.empty()) {
        Node curr = pq.top();
        pq.pop();

        // 当前路径状态已不是最优，跳过
        if (curr.blocks > dist[curr.x][curr.y].blocks || 
            (curr.blocks == dist[curr.x][curr.y].blocks && curr.steps >= dist[curr.x][curr.y].steps)) {
            continue;
        }

        // 处理所有可能的跳跃方向
        for (auto [dx, dy] : dirs) {
            int nx = curr.x + dx;
            int ny = curr.y + dy;
            // 检查边界
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;

            // 计算是否需要放置方块
            int add_block = (grid[nx][ny] == '0') ? 1 : 0;
            int new_blocks = curr.blocks + add_block;
            int new_steps = curr.steps + 1;

            // 判断是否更优
            if (new_blocks < dist[nx][ny].blocks || 
                (new_blocks == dist[nx][ny].blocks && new_steps < dist[nx][ny].steps)) {
                dist[nx][ny] = {new_blocks, new_steps};
                pq.push({nx, ny, new_blocks, new_steps});
            }
        }
    }

    // 输出结果
    if (dist[end_x][end_y].blocks == INT_MAX) {
        cout << "-1 -1\n";
    } else {
        cout << dist[end_x][end_y].blocks << " " << dist[end_x][end_y].steps << "\n";
    }

    return 0;
}

公式二分加分块：暴力复杂度太大，观察式子h-g（h）里面的变化了单调递减，最多有根号h组不同的递减。因为1，2，3，4.。。（n）*（n-1）/2；所以采用分组可以应对大数除以接近1的数

 #include <iostream>
 #include <vector>
 using namespace std ;
 typedef long long ll ;
 l l sub( ll n, ll a, ll b)
 {
 return n = n * a / b;
 }
 int main()
 {
 int t;
 cin >> t;
 while (t==)
 {
 l l n, a, b;
 cin >> n >> a >> b;
 l l cnt = 0;
 while (n)
 {
 l l l = 0, r = n;
 l l s = sub(n, a, b);
 while (l + 1 < r)
 {
 l l mid = (l + r) / 2;
 l l s1 = sub(mid, a, b);
 i f (s1 == s)
 {
 r = mid;
 }
 else
 {
 }
 l = mid;
 }
 l l d = (n = r) / s + 1;
 n == d * s;
 cnt += d;
 }
 cout << cnt = 1 << "\n";
 }
第18 页，共31页
2025 广州大学程序设计校赛
2025年3月29日
}

水题，情况/总情况

#include <bits/stdc++.h>
using namespace std;
#define int long long 
const int N = 2000010,mod =998244353;
int fac[N], ifac[N];
vector<int> dp;
int q(int a, int k, int mod) {
    int res = (int)1 % mod;
    while (k) {
        if (k & (int)1)
            res = res * a % mod;
        k >>= (int)1;
        a = a * a % mod;
    }
    return res;
}
vector<int> init_D(int n) {
    vector<int> dp(n + 1, 0);  
    dp[0] = 1;               
    if (n >= 1) {
        dp[1] = 0;           
    }
    for (int i = 2; i <= n; i++) {
        dp[i] = ((i - 1) * (dp[i - 1] + dp[i - 2])) % mod;  
    }
    return dp;
}
int inv(int x) {
    return q(x, mod - 2, mod);
}
void init(int n) {
    for (int i = 0; i <= n; i++) {
        fac[i] = ifac[i] = 0;
    }
    fac[0] = 1;
    for (int i = 1; i <= n; i++) {
        fac[i] = fac[i - 1] * i % mod;
    }
    ifac[n] = inv(fac[n]);
    for (int i = n - 1; i >= 0; i--) {
        ifac[i] = ifac[i + 1] * (i + 1) % mod;
    }
}

int C(int n, int m) {
    if (m < 0 || m > n || n < 0) {
        return 0;
    }
    return fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}
int A(int n, int m) {
    if (m < 0 || m > n || n < 0) {
        return 0;
    }
    return fac[n] * ifac[n - m] % mod;
}
void solve(){
    int n;
    cin>>n;
   // cout<<n-1<<" "<<A(n-1,n-1)<<" "<<inv(q(n-1,n,mod))<<"\n";
    cout<<dp[n]*inv(q(n-1,n,mod))%mod<<"\n";


}

signed main(){
    init(2000005);
    dp=init_D(2000005);
    int t;
    cin>>t;
    while(t--){
        solve();
    }

}

思维题：难点在于解决蚂蚁在同一个非根点上会重复，那么有多个叉点的时候难以处理，但是发现，当到达某个点的时候，如果t（深度）相同，那么他俩必定会在某个点重复，所以直接让他们慢一步，所以直接枚举1的子节点就行

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    ll n,ans = 0,cnt = 0;
    cin >> n;

    vector<ll> dep(n + 1),a;
    vector<vector<ll>> edge(n + 1);

    for(int i = 1;i < n;i++){
        ll u,v;
        cin >> u >> v;
        edge[u].push_back(v);
        edge[v].push_back(u);
    }

    auto dfs = [&](auto& self,ll p,ll f) -> void{
        dep[p] = dep[f] + 1;
        if(edge[p].size() == 1 && p != 1) a.push_back(dep[p]);
        for(auto v : edge[p]){
            if(v == f) continue;
            self(self,v,p);
        }
    };

    dep[1] = 0;
    for(auto i : edge[1]){
        a.clear();
        dfs(dfs,i,1);
        sort(a.begin(),a.end());
        cnt = 0;
        for(int i = 1;i < a.size();i++){
            a[i] = max(a[i],a[i - 1] + 1);
        }
        ans = max(ans,a.back());
    }
    cout << ans << "\n";
    return 0;
}

双映射

#include<bits/stdc++.h>
using namespace std;
#define int long long

int n, t;
int f[1000005]; // 鸽子i所在的巢的物理位置
int q[1000005]; // 物理位置pos对应的门牌号
int p[1000005]; // 门牌号a对应的物理位置

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> t;
    // 初始化：每个鸽子在对应巢中，门牌号与位置一致
    for (int i = 1; i <= n; ++i) {
        f[i] = i;
        q[i] = i;
        p[i] = i;
    }

    while (t--) {
        int op;
        cin >> op;
        if (op == 1) {
            int a, b;
            cin >> a >> b;
            // 将鸽子a移动到门牌号b的巢的物理位置
            f[a] = p[b];
        } else if (op == 2) {
            int a, b;
            cin >> a >> b;
            // 交换门牌号a和b的物理位置及对应的门牌号
            swap(q[p[a]], q[p[b]]);
            swap(p[a], p[b]);
        } else {
            int a;
            cin >> a;
            // 查询鸽子a所在巢的门牌号
            cout << q[f[a]] << "\n";
        }
    }

    return 0;
}

并查集加双映射

#include<bits/stdc++.h>
using namespace std;
#define int long long
int t;
int n,q;
int flag;
int x,y;
int f[1000005];
int fb[1000005];
int b[1000005];//第i个位置是第b[i]个部落
int dis[1000005];//第i个部落，在第dis[i]个位置 
int cha(int x)
{
    if(fb[x]==x)
    {
        return x;
    }
    return fb[x]=cha(fb[x]);
}

void bing(int x,int y)
{
    int fx=cha(x);
    int fy=cha(y);
    if(fx!=fy)
    {
        fb[fy]=fx;
    } 
}
void solve()
{

    cin>>n>>q;
    for(int i=1;i<=n;i++)
    {
        f[i]=i;
        fb[i]=i;
        dis[i]=i;
        b[i]=i; 
    }
    while(q--)
    {
        cin>>flag>>x;
        if(flag==1)
        {
            cin>>y;
            x=b[x];
            y=b[y]; 
            bing(x,y);
        }
        if(flag==2)
        {
            cin>>y;
            f[x]=b[y];
        }
        if(flag==3)
        {
            cin>>y;
            x=b[x];
            y=b[y];
            swap(b[dis[x]],b[dis[y]]);
            swap(dis[x],dis[y]);
        }
        if(flag==4)
        {
        //  cout<<"f[x]="<<f[x]<<"\n";
            cout<<dis[cha(f[x])]<<"\n";
        }
    }
//  cout<<"\n";
//  for(int i=1;i<=n;i++)
//  {
//      cout<<fb[i]<<" ";
//  }
}
signed main()
{
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    cin>>t;
    while(t--)
    solve();
    return 0;
}

蓝桥思维题

`#include [HTML_REMOVED] //万能头文件
using namespace std;
using ll = long long; //int不够，得开long long，ll 好写一点
const int N = 200000 + 5;
int main()
{
int T;
cin >> T; //T组数据
while (T–)
{
unordered_map[HTML_REMOVED]mp; //记录每种职业的士兵数
ll n, k;
cin >> n >> k;
ll a, b;
for (int i = 0; i < n; i++)
{
cin >> a >> b;
mp[a] += b; //存数据
}
ll ans = 0; //答案初始为0
ll sum = 0; //记录所有士兵加起来最多能组成组纯职业小组
ll hash3 = 0; //下面在解释
ll tk = k; //记录最开始的k
for (auto& elem : mp) //每种职业
{
ll sec = elem.second;

//取该种职业的总士兵数
sum += sec / 3; //累加看该循环职业的士兵最多能组成多少纯职业小组
if (sec < 3) //这种职业的士兵凑不了纯小组，直接加进来，因为最坏情况：假如抽到的士兵中就有这种的职业士兵
{
ans += sec;
}
else
{
ans += 2; //先拿出2个士兵，到时候在加一个这种职业的士兵就凑成一组
sec -= 2; //拿出后剩下的士兵
if (sec / 3 < k) //如果剩下的士兵组成的纯职业小组不能组成k组
{
ans += sec / 3 * 3; //sec / 3 < k说明这种职业的剩下的士兵还不够凑成k个，我们把它们加进去，先凑成了sec / 3个纯小组，像那种大于k的是完全能凑成k组的就不先加，到时候需要的时候在加
k -= sec / 3; /
}
else
{
//如果sec / 3大于了k说明这种士兵人数多，我们先把士兵少的加进去，这种情况就存在hash3中
hash3 += sec / 3;
}
}
}
if (sum < tk)
{
//这种情况连所有士兵都选了都不能凑k个纯小组，那必然不行，输出-1
cout << -1 << endl;
continue;
}
if (hash3 >= k) //若hash3大于k，士兵少的已经加完了，那么只需要在能凑成小组的士兵中选就行了
{
cout << ans + (k - 1) * 3 + 1 << endl;
//将已经选了的士兵ans 加上 (k-1)3 +1 ,因为我们之前都提前把能凑成纯小组的士兵拿了2个，现在在拿一个就能组成小组所以+1，还剩k-1组，只需要加（k-1)3
}
else
{ //之前拿出2个的那种士兵，只需要加个1，就凑成了3个了，就是一组，而需要k组，加k个就ok了
cout << ans + k << endl;
}
}
return 0; //记住，最坏情况
}`

同一道题的不同时期的解法

贪心的思想
#include <bits/stdc++.h>
using namespace std;
#define int long long 
void solve(){
    string s;
    cin>>s;
    int n=s.size();
    s='?'+s;
    int cnt=0;
    for(int i=1;i<n;i++){
        int l=i;
        int r=i+1;
        bool b=false;
        //cout<<l<<" "<<r<<"\n";
        //cout<<s[l]<<" "<<s[r]<<"pppp\n";   
        while(l>=1&&r<=n){
            if(s[l]>s[r]){
                b=true;
            }else if(s[l]<s[r]){
                b=false;
            }
            if(b){cnt++;
              //  cout<<l<<" "<<r<<"\n";
            }
        l--;
        r++;  
        }
    }
    for(int i=2;i<n;i++){
        int l=i-1;
        int r=i+1;
        bool b=false;
        while(l>=1&&r<=n){
            if(s[l]>s[r]){
                b=true;
            }else if(s[l]<s[r]){
                b=false;
            }
           if(b){cnt++;
              // cout<<l<<" "<<r<<"\n";
            }
        l--;
        r++;        
        }
    }
    cout<<cnt<<"\n";
}
signed main(){
    int t;
    t=1;
    while(t--){
        solve();
    }
}
区间dp的思想
#include <bits/stdc++.h>
using namespace std;
string s;
bool dp[5010][5010];
int main(){
    cin>>s;
    int n=s.size();
    for(int len=2;len<=n;len++)
    for(int i=0;i+len-1<n;i++){
        int j=i+len-1;

        if(len==2){
        if(s[i]>s[j]){
            dp[i][j]=true;
        }
        }
        else{
            if(s[i]>s[j]) dp[i][j]=true;
            else if(s[i]==s[j]) dp[i][j]=dp[i+1][j-1];
        }
    }
    int sum=0;
    for(int len=2;len<=n;len++){
        for(int i=0;i+len-1<n;i++){
            int j=i+len-1;
            if(dp[i][j]) sum++;
        }
    }
    cout<<sum<<"\n";
}