题解 AT2067 【[ARC061A] たくさんの数式 / Many Formulas】

· · 题解

有一个O(n^2)的dp做法,后面还会提供一种O(n)的做法

$num[i]$表示到了第i位有多少种不同的组合 $sum[i][j]$表示从数字i到数字j为一组的值(比如123456,$sum[1][4]$就等于1234) 所以不难得到这样一个柿子 $$ f[i]=\sum\limits_{j=1}^{i}f[j-1]+sum[j][i]*num[j-1] $$ 相当于去固定右端点i,去枚举左端点j的位置 然后最终答案就是$f[n]$了 下面是代码 ```cpp #include<bits/stdc++.h> using namespace std; #define il inline #define ri register int #define ll long long il ll read(){ bool f=true;ll x=0; register char ch=getchar(); while(ch<'0'||ch>'9') {if(ch=='-') f=false;ch=getchar();} while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar(); if(f) return x; return ~(--x); } il void write(const ll &x){if(x>9) write(x/10);putchar(x%10+'0');} il void print(const ll &x) {x<0?putchar('-'),write(~(x-1)):write(x);putchar('\n');} il int max(const int &a,const int &b){return a>b?a:b;} il int min(const int &a,const int &b){return a<b?a:b;} string s; int a[11]; ll f[11]; ll num[11]; ll sum[11][11]; int n; int main(){ num[0]=1; cin>>s; n=s.length(); for(ri i=1;i<=n;++i){ a[i]=s[i-1]-'0'; } for(ri i=1;i<=n;++i){ for(ri j=i;j<=n;++j){ sum[i][j]=sum[i][j-1]*10+a[j]; } } for(ri i=1;i<=n;++i){ for(ri j=1;j<=i;++j){ f[i]+=f[j-1]+sum[j][i]*num[j-1]; num[i]+=num[j-1]; } } print(f[n]); return 0; } ``` ------------ 但是这道题目的柿子很简单,以至于给人一种可以$O(nlogn)$过去的感觉 发现$num[i]$就是相当于每一个空位上放或不放$+$的方案数,也就是$2^{i-1}

其中num[0]=1
为了方便此处定义2^{-1}=1
这个时候再来看刚才推出来的柿子,\sum\limits_{j=1}^{i}f[j-1]是可以通过前缀和O(1)得到的,瓶颈在另半边上

$g[i]=a[i]\sum\limits_{j=1}^{i}2^{j-2}=a[i]2^{i-1} g[i-1]=10*a[i-1]2^{i-2}

以此类推就可以了
所以\sum\limits_{j=1}^{i}2^{j-2}sum[j][i]=\sum\limits_{j=1}^{i}10^{i-j}a[j]2^{j-1},可以发现后面的a[j]2^{j-2}与i没有关系,可以提前预处理出来
于是此处用到F[i]=\sum\limits_{j=1}^{i}a[j]2^{j-1}
可以发现F[i]=2F[i-1]+a[i],O(n)得到
所以\sum\limits_{j=1}^{i}2^{j-2}sum[j][i]=\sum\limits_{j=1}^{i}10^{i-j}F[j],前面那一陀用G[i]表示
同样可以推得G[i]=G[i-1]*10+a[i]*2^{i-1},和F[i]没有关系了
而且整理发现,上面这个过程的总复杂度是O(n)的!

接下来重新梳理一下上面的过程

f[i]=\sum\limits^{i-1}_{j=1}f[j]+G[i]=sum[i-1]+G[i] G[i]=G[i-1]*10+a[i]*2^{i-1}

只需要这两个简单的柿子就可以做到O(n)
下面是代码 

#include<bits/stdc++.h>
using namespace std;
#define il inline
#define ri register int
#define ll long long
il ll read(){
    bool f=true;ll x=0;
    register char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=false;ch=getchar();}
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    if(f) return x;
    return ~(--x);
}
il void write(const ll &x){if(x>9) write(x/10);putchar(x%10+'0');}
il void print(const ll &x) {x<0?putchar('-'),write(~(x-1)):write(x);putchar('\n');}
il int max(const int &a,const int &b){return a>b?a:b;}
il int min(const int &a,const int &b){return a<b?a:b;}
string s;
const int MAXM=11;
int a[MAXM];
ll f[MAXM];
ll sum[MAXM];
ll g[MAXM];
int n;
ll powt[MAXM];
int main(){
    num[0]=1;
    cin>>s;
    n=s.length();
    for(ri i=1;i<=n;++i){
        a[i]=s[i-1]-'0';
        sum[i]=sum[i-1]+a[i];
    }
    powt[0]=1;//2的k次方
    for(ri i=1;i<=n;++i){
        powt[i]=powt[i-1]<<1;
        g[i]=g[i-1]*10+a[i]*powt[i-1];         
        f[i]=sum[i-1]+g[i];
        sum[i]=sum[i-1]+f[i];
    }
    print(f[n]);
    return 0;
}