给定一个n,输出\((a1+x)*(a2+x)*...(an+x)\)的多项式长度。
每一个字符(包括"a”、“x”、“("、")”、“+”,每一个指数的每一个数字,每一个下标
的每一个数字长度都为1。如π=n时,总长度为40。
对于这个题来说我们直接把a,x,(),+,数字,下标分类讨论一下,就能得到最终的答案。
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
#define mo 10000
#define int long long
using namespace std;
int a[10] = {0, 9, 99, 999, 9999, 99999, 999999, 9999999, 99999999, 999999999};
int ksm(int a, int b)
{
int ans = 1;
while (b)
{
if (b & 1)
ans = a * ans % mo;
a = a * a % mo;
b >>= 1;
}
return ans % mo;
}
signed main()
{
freopen("mult.in", "r", stdin);
freopen("mult.out", "w", stdout);
int n, ans = 0;
scanf("%lld", &n);
if (n >= 1)
{
int now = n, sum = 0;
for (int i = 9; i >= 1; i--)
{
if (now > a[i])
sum += i * (now - a[i]), now = a[i];
}
sum += n;
// printf("%d",sum);
ans = ans + ksm(2, n) - 1LL;//+
ans = ((ans % mo) + (n + mo)) % mo;//x
ans = ((ans % mo) + (sum + mo) - 1LL) % mo;//zhi
ans = ans + 2LL * (n - 1) % mo;//kuo
ans = ans + (ksm(2LL, n - 1) * ((n % mo) + (sum % mo)) % mo) % mo;//xia
printf("%lld", (ans + mo) % mo);
}
return 0;
}