湖南省第十二届大学生计算机程序设计竞赛$H$题
规律，递推。
这种问题一看就有规律。可以按位统计对答案的贡献。即第$1$位对答案作出了多少贡献，第$2$位对答案作出了多少贡献.....累加和就是答案。
先写一个暴力的程序来找找规律：
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<iostream>
using namespace std;
typedef long long LL;
const double pi=acos(-1.0),eps=1e-;
void File()
{
freopen("D:\\in.txt","r",stdin);
freopen("D:\\out.txt","w",stdout);
}
template <class T>
inline void read(T &x)
{
char c = getchar();
x = ;
while(!isdigit(c)) c = getchar();
while(isdigit(c))
{
x = x * + c - '';
c = getchar();
}
} const int maxn=;
struct X
{
int p;
}s[maxn];
int n;
int f[maxn][maxn]; int main()
{
while(~scanf("%d",&n))
{
memset(f,,sizeof f);
for(int i=;i<=n;i++) s[i].p=i; for(int i=;i<=n;i++)
{
for(int j=i;j<=n;j++)
{
for(int k=i;k<=(i+j)/;k++) swap(s[k],s[j-(k-i)]); for(int k=;k<=n;k++) f[s[k].p][k]++; for(int k=i;k<=(i+j)/;k++) swap(s[k],s[j-(k-i)]);
}
} for(int i=;i<=n;i++)
{
int sum=;
for(int j=;j<=n;j++)
{
// sum=sum+(int)pow(10.0,j-1)*f[i][j];
printf("%3d ",f[i][j]);
}
printf("\n");
// printf("%d ",sum);
}
printf("\n"); }
return ;
}
上面的代码中，$f[i][j]$表示$i$这一位，所有交换中，在$j$位出现了几次；答案就是$\sum\limits_{i = 1}^n {\left( {s[i]×\left( {\sum\limits_{j = 1}^n {f[i][j]×{{10}^{j - 1}}} } \right)} \right)} $。
输出来看一下$n=10$和$n=11$时候的情况，看看$f[i][j]$有没有什么规律：
通过观察可以发现：
$[1].$每一行的和都是一样的，$n=x$时，每一行的和$cnt[x]$都是一样的，并且$cnt[x]=x+cnt[x-1]$。
$[2].$第$i$行的贡献${\sum\limits_{j = 1}^n {f[i][j]×{{10}^{j - 1}}} }$可以由第$i-1$行的贡献${\sum\limits_{j = 1}^n {f[i-1][j]×{{10}^{j - 1}}} }$递推而来。
也就是说，我们可以$O(n)$效率得到每一位的贡献，然后乘上输入的那个权值就是答案了。
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<iostream>
using namespace std;
typedef long long LL;
const double pi = acos(-1.0), eps = 1e-;
void File()
{
freopen("D:\\in.txt", "r", stdin);
freopen("D:\\out.txt", "w", stdout);
}
template <class T>
inline void read(T &x)
{
char c = getchar(); x = ; while (!isdigit(c)) c = getchar();
while (isdigit(c)) { x = x * + c - ''; c = getchar(); }
} const LL mod = 1e9 + ;
const int maxn = ;
LL a[maxn], cnt[maxn], POW[maxn], sPOW[maxn], num[maxn];
char s[maxn];
int n; int main()
{
cnt[] = ;
for (int i = ; i <= ; i++) cnt[i] = (cnt[i - ] + i) % mod;
POW[] = ; sPOW[] = ;
for (int i = ; i <= ; i++)
{
POW[i] = (LL) * POW[i - ] % mod;
sPOW[i] = (sPOW[i - ] + POW[i]) % mod;
} while (~scanf("%d%s", &n, s))
{
memset(num, , sizeof num);
memset(a, , sizeof a); num[] = (cnt[n] - (n - ) + mod) % mod;
a[] = (num[]*POW[] % mod + (sPOW[n - ] - sPOW[] + mod) % mod) % mod; int L = , R = n - ;
for (int i = ; i < n / ; i++)
{
L++, R--; num[i] = (num[i - ] - (R - L + ) + mod) % mod;
a[i] = (a[i - ] + sPOW[R] - sPOW[L - ] + mod) % mod;
a[i] = (a[i] + ((num[i] - i + mod) % mod)*POW[i] % mod) % mod;
a[i] = (a[i] - (((num[i - ] - i + mod) % mod)*POW[i - ] % mod) + mod) % mod;
} num[n - ] = num[];
a[n - ] = (num[n - ] * POW[n - ] % mod + sPOW[n - ]) % mod; L = , R = n - ; LL d = ;
for (int i = n - ; i >= (n ) / ; i--)
{
L++, R--; num[i]= (num[i + ] - (R - L + ) + mod) % mod;
a[i]= (a[i + ] + sPOW[R] - sPOW[L - ] + mod) % mod;
a[i] = (a[i] + ((num[i] - d + mod) % mod)*POW[i] % mod) % mod;
a[i] = (a[i] - (((num[i + ] - d + mod) % mod)*POW[i + ] % mod) + mod) % mod;
d++;
} LL ans = ;
for (int i = ; s[i]; i++) ans = (ans + (LL)(s[i] - '')*a[n-i-] % mod) % mod;
cout << ans << endl;
}
return ;
}