题解：CF1142D Foreigner

Dovish · 2025-11-20 20:52:52 · 题解

其实是找规律题的。

题解

判定一个数 x 是否合法需要知道 \lfloor\dfrac{x}{10}\rfloor 是否合法以及其排名。

那么一个朴素暴力的想法就是：枚举左端点，不断向右拓展合法的状态。

不过我们这个过程中需要在一个数末尾追加上一个数位，如何计算排名的变化呢？

发现我们本质上只需要计算排名在 \bmod 11 下的值即可。

然后打表找一下规律，发现：如果我们知道 x 的排名，则 10x 的排名总是一定的（在 \bmod {11} 意义下）。

具体而言，对应关系如下：

所以我们可以写出以下暴力：

int tr[11]={-1,10,0,2,5,9,3,9,5,2,0};
void solve()
{
    rep(i,1,n)
    {
        if(!a[i])continue;
        int rk=10; 
        rep(j,i,n)
        {
            if(a[j]>=rk)break;
            ans++;
            rk=(tr[rk]+a[j])%11;
        }
    }
}

优化这个是容易做的，我们设 f_{i,c} 表示在 i 的位置传入 c 的 rk，最早会在什么时刻使得 a_j\ge rk。

转移计算一下传入下一个位置的排名即可。

复杂度 O(np)，其中 p 是模数，本题中 p=11。

code

#include<bits/stdc++.h>
#define int long long
#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 edge(i,u) for(int i=head[u];i;i=e[i].next)
#define lc(u) (u<<1)
#define rc(u) (u<<1|1)
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define fst first
#define sed second
using namespace std;
const int N=1e5+10;
bool MS;int used;
int a[N];
string s;
int n,ans;
int tr[11]={-1,10,0,2,5,9,3,9,5,2,0};
int f[N][11];
bool MT;
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>s;
    n=s.size();
    s=" "+s;
    rep(i,1,n)
    a[i]=s[i]-'0';
    ans=0;
    rep(c,0,10)f[n+1][c]=n+1;
    per(i,n,1)
    {
        rep(c,0,10)
        {
            if(a[i]>=c)f[i][c]=i;
            else f[i][c]=f[i+1][(tr[c]+a[i])%11];
        }
        if(!a[i])continue;
        ans+=f[i][10]-i;
    }
    cout<<ans<<'\n';
    cerr<<"Memory:"<<(&MS-&MT)/1048576.0<<"MB Time:"<<clock()/1000.0<<"s\n";
}