#295 (div.2) E.Pluses everywhere

1. 제목 설명: 클릭 하여 링크 열기
2. 문제 풀이 사고: 본 문 제 는 조합 수학 문제 로 처음에 재 귀적 인 사상 으로 했 으 나 결 과 는 틀 렸 다.다른 사람의 해법 을 배우 고 나 니 탁 트 였 다.정확 한 해법 은 한 자릿수 가 전체 에 기여 하 는 값 에 주목 하 는 것 이다.예 를 들 어 입력 한 n 자리 수가 D1D2D 3... D (n - 1) D (n) 라면 D (i) 가 한 자리 일 때 그 앞 에 반드시 '+' 가 있 을 것 이다.나머지 k - 1 개의 '+' 는 남 은 n - 2 개의 공간 에 배치 되 어 있 기 때문에 모두 C (n - 2, k - 1) 가지 상황 이 있 고 D (i) 의 총 공헌 치 는 D (i) * C (n - 2, k - 1) 이다.마찬가지 로 D (i) 가 10 자리 일 때 D (i + 1) 는 반드시 한 자리 이 고 D (i + 1) 앞 에 '+' 가 있 을 것 이다. 그러면 나머지 k - 1 개의 '+' 는 남 은 n - 3 개의 공간 에 배치 되 기 때문에 C (n - 3, k - 1) 의 경우 D (i) 의 총 공헌 치 는 D (i) * 10 * C (n - 3, k - 1) 로 유추 된다.이러한 D (i) 는 최대 n - k 위 (개 위 는 1 위, 10 위 는 2 위, 순서대로 유추) 에 불과 해 첫 번 째 기여 치 를 계산 했다.
두 번 째 부분의 공헌 치 는 '+' 뒤의 그 자리 에서 나온다.D (i + 1) 앞 에 '+' 가 있 고 n 위 라 고 가정 할 때 반드시 k 개의 '+' 가 그 앞 에 있 는 n - 1 개의 공간 에 배치 되 기 때문에 C (n - 1, k) 의 경우 D (i + 1) 의 총 공헌 치 는 D (i + 1) * C (n - 1, k) 이다.D (i + 1) 앞 에 '+' 가 있 고 n - 1 위 라면 총 공헌 은 D (i + 1) * 10 * C (n - 2, k) 로 유추 된다.마지막 으로 두 부분의 합 을 더 하면 최종 답 이다.
조합 수 취 모, 접두사 와 관련 되 기 때 문 입 니 다.따라서 초기 화 에서 이 수의 값 을 미리 계산 해 후속 처리 에 편리 하도록 해 야 한다.조합 수 공식 에 따 르 면 C (n, k) = n! /k!/(n-k)!，따라서 n 을 미리 계산 해 야 한다!(mod M) 의 값 입 니 다.이 문제 에서 M 은 소수 이기 때문에 역원 으로 나눗셈 을 대체 하 는 것 을 고려 할 수 있다.페 르 마 의 작은 정리 에 따 르 면 n ^ (M - 1), 1 (mod M), 즉 n * n ^ (M - 2), 1 (mod M).따라서 n 의 역 원 은 n ^ (M - 2) 이다.이것 은 이 문제 의 첫 번 째 새로운 지식 점 이다.n 을 계산 해 냈 다!n! =n*(n-1)!，양쪽 에 INV (n), INV (n - 1) 를 동시에 곱 하면 INV (n - 1) = n * INV (n) 로 간략화 되 기 때문에 이 공식 을 이용 하여 다른 역 원 을 추론 할 수 있다. 이것 은 본 문제 의 두 번 째 새로운 지식 이다.이 문 제 는 한 자릿수 공헌 치 를 고려 한 차원 에서 세 번 째 새로운 지식 이다.
메모: long long 형 을 출력 할 때% I64d 로 출력 하 는 것 을 추천 합 니 다.
3. 코드:

#define _CRT_SECURE_NO_WARNINGS 
#include<iostream>
#include<algorithm>
#include<string>
#include<sstream>
#include<set>
#include<vector>
#include<stack>
#include<map>
#include<queue>
#include<deque>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<ctime>
#include<functional>
using namespace std;

typedef long long LL;
const int MOD = 1000000000 + 7;
const int N = 110000;
int n, k, a[N],sum[N];
char st[N];
LL fac[N], inv[N];

LL pow_mod(LL a, LL k)
{
	LL ans = 1;
	while (k > 0)
	{
		if (k & 1)ans = ans*a%MOD;
		a = a*a%MOD;
		k >>= 1;
	}
	return ans;
}
void init()//      ，  
{
	fac[0] = 1;
	for (int i = 1; i <= n; i++)
		fac[i] = fac[i - 1] * i%MOD;
	inv[n] = pow_mod(fac[n], MOD - 2);
	for (int i = n - 1; i >= 0; i--)
		inv[i] = inv[i + 1] * (i + 1) % MOD;
}
int C(int n, int k)//       
{
	return fac[n] * inv[k] % MOD*inv[n - k] % MOD;
}
int main()
{
	//freopen("t.txt", "r", stdin);
	scanf("%d%d", &n, &k);
	scanf("%s", st + 1);
	sum[0] = 0;
	for (int i = 1; i <= n; i++)
	{
		a[i] = st[i] - '0';
		sum[i] = sum[i - 1] + a[i];
	}
	init();
	LL ans = 0;
	LL s;
	LL base = 1;//base     LL！
	for (int i = 1; i <= n - k; i++)
	{
		s = (LL)sum[n - i] * base%MOD;//       
		ans += (LL)s*C(n - i - 1, k - 1) % MOD;

		s = (LL)a[n - i + 1] * base%MOD;//       
		ans += s*C(n - i, k) % MOD;

		base *= 10;
		ans %= MOD;
		base %= MOD;
	}
	printf("%I64d
", ans);
	return 0;
}