题解 CF520E 【Pluses everywhere】

ps:可能组合数一不小心打错了，请发现的大佬提出，谢谢。

我们来讨论每一位数$a_{i}$被算了多少次。

总共有$n-1$个空位可以放$'+'$所以，$a_{i}$左边有$i-1$个空位，右边$n-1-(i-1)$个。

举个例子来说~~（手动模拟一下）~~，如果数$a_{i}$右边有一个加号，则剩下$n-2$个空位放$k-1$个加号的方案里，每种方案$a_{i}$都当做各位记录到答案里，所以对答案影响：$C^{k-1}_{n-2}*$ $a_{i}$。
假设右边第一个不放，第二个放加号，则还有$n-3$个空位，$k-2$个加号。（因为$a_{i}$右边的以为不能放加号）对答案影响： $C_{n-3}^{k-2}*10*$ $a_{i}$。

$emm……$规律好像找出来了。

这样一直递推下去~~（找规律）~~的话。到$a_{n-1}$ 和 $a_{n}$ 位填的话。对答案的影响： $C^{1}_{n-k-2}*10^{k-1}*a_{i}$

但是，我们发现，最后一位数的后面好像并不能放加号。也就是说，最后一位需要特判。。。

所以，当右边全空着的时候对答案的贡献 $10^{i}*C_{n-i-1}^{i}*a_{i}$

全部统计起来，输出就好。
代码奉上。

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

const long long p=1e9+;

int n,k;

long long ans[];

char a[];

long long pen[];//阶乘

long long rpen[];//阶乘逆元

long long num[];//系数

long long pow2(long long a,long long b)

{

    long long res=;

    for(;b;b>>=,a=a*a%p) if(b&) res=res*a%p;

    return res%p;

}

void rebiut()

{

    num[]=pen[]=rpen[]=;

    for(int i=;i<=n;i++)

        pen[i]=pen[i-]*i%p,

        rpen[i]=pow2(pen[i],p-),

        num[i]=*num[i-]%p;

    return ;

}

long long C(long long n,long long k)//计算组合数，n下面，k上面

{

    if(k<||k>n||n<) return ;

    else return ((pen[n]*rpen[k])%p)*rpen[n-k]%p;

}

long long now;

int main()

{

    scanf("%d%d",&n,&k);

    scanf("%s",a);

    rebiut();

    for(int i=;i<n;i++) now=(now+num[i]*(a[n-i-]-''))%p;

    if(k==) {printf("%lld ",now);return ;}

    int d=n-k-;

    ans[]=C(n-,k-);

    for(int i=;i<=d;i++) ans[i]=(ans[i-]+num[i]*C(n-i-,k-))%p;

    for(int i=d+;i<n;i++) ans[i]=ans[i-];

    for(int i=;i<=d;i++) ans[i]=(ans[i]+num[i]*C(n-i-,k))%p;

    now=;

    for(int i=;i<n;i++) now=(now+ans[n-i-]*(a[i]-''))%p;

    printf("%lld ",now);

    return ;

}

巴特西

题解 CF520E 【Pluses everywhere】

最新文章

热门文章