问题描述
这题的题面真的妙……望大家结合样例正确理解题意……
首先来个样例解释：
样例1
显然，需要两次亵渎
第一次，a从1,2,3,4,6,7,8,9,10，变为0,0,0,0,1,2,3,4,5，对答案的贡献为
1*1+2*2+3*3+4*4+6*6+7*7+8*8+9*9+10*10=360
第二次，a从0,0,0,0,1,2,3,4,5，变为0,0,0,0,0,0,0,0,0，对答案的贡献为
1*1+2*2+3*3+4*4+5*5=55
所以答案为415
样例2
显然，需要三次亵渎
第一次，a从3,4，变为2,3，对答案的贡献为
3*3*3+4*4*4=91
第二次，a从2,3，变为1,2，对答案的贡献为
2*2*2+3*3*3=35
第二次，a从1,2，变为0,0，对答案的贡献为
1*1*1+2*2*2=9
所以答案为135
解题思路
我们发现，问题实际上是求一系列的(sum_{i=a}^bi^k)。那么问题可以转换为求(sum_{i=1}^ni^k)。
我们不妨记(sum_{i= 1}^ni^k)为(S_{n,k})。现在考虑如何求(S_{n,k})。
我们考虑
[egin{aligned}
(i+1)^{k+1}-i^{k+1}&={k+1 choose 1}i^k+{k+1 choose 2}i^{k-1}+...+{k+1choose k+1}i^0\
sum_{i=1}^n((i+1)^{k+1}-i^{k+1})&=(n+1)^{k+1}-1^{k+1}\
&={k+1choose 1}sum_{i=1}^ni^k+{k+1choose2}sum_{i=1}^ni^{k-1}+...+{k+1choose k+1}sum_{i=1}^n1\
&={k+1choose 1}S_{n,k}+{k+1choose2}S_{n,k-1}+...+{k+1choose k+1}S_{n,0}\
S_{n,k}&=frac{1}{k+1}((n+1)^{k+1}-1-sum_{i=0}^{k-1}{k+1choose k+1-i}S_{n,i})
end{aligned}
]
这样我们就可以在(O(k^2))求出(S_{n,k})。总时间复杂度(O(m^4))。
参考程序
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const LL Mod = 1000000007;
const LL MaxK = 60;
LL C[ MaxK ][ MaxK ];
LL n, m, A[ MaxK ];
LL Sn[ MaxK ], Power[ MaxK ];
void Exgcd( LL a, LL b, LL &x, LL &y ) {
if( b == 0 ) {
x = 1; y = 0; return;
}
Exgcd( b, a % b, y, x );
y -= a / b * x;
return;
}
LL Inv( LL a, LL b ) {
LL x, y;
Exgcd( a, b, x, y );
if( x < 0 ) x += b;
return x;
}
void Init() {
C[ 0 ][ 0 ] = 1;
for( LL i = 1; i <= MaxK - 1; ++i ) {
C[ i ][ 0 ] = 1;
for( LL j = 1; j <= i; ++j )
C[ i ][ j ] = ( C[ i - 1 ][ j - 1 ] + C[ i - 1 ][ j ] ) % Mod;
}
return;
}
void Get_Sn( LL n ) {
memset( Sn, 0, sizeof( Sn ) );
Sn[ 1 ] = ( n + 1 ) % Mod * ( n % Mod ) % Mod * Inv( 2, Mod ) % Mod;
Sn[ 0 ] = n % Mod;
Power[ 0 ] = 1;
for( LL i = 1; i <= m + 2; ++i )
Power[ i ] = ( n + 1 ) % Mod * Power[ i - 1 ] % Mod;
for( LL i = 2; i <= m + 1; ++i ) {
LL T = 0;
T = Power[ i + 1 ] - 1;
T = ( T % Mod + Mod ) % Mod;
for( LL j = 0; j <= i - 1; ++j ) {
T = T - C[ i + 1 ][ i + 1 - j ] * Sn[ j ] % Mod;
T = ( T % Mod + Mod ) % Mod;
}
Sn[ i ] = T * Inv( i + 1, Mod ) % Mod;
}
return;
}
LL Ask( LL n, LL k ) {
Get_Sn( n );
return Sn[ k ];
}
void Work() {
scanf( "%lld%lld", &n, &m );
for( LL i = 1; i <= m; ++i ) scanf( "%lld", &A[ i ] );
sort( A + 1, A + m + 1 );
++m;
A[ 0 ] = 0; A[ m ] = n + 1;
LL k = m;
LL Ans = 0;
for( LL i = 1; i <= k; ++i ) {
for( LL j = i; j <= m; ++j ) {
Ans = ( Ans + Ask( A[ j ] - 1, k ) - Ask( A[ j - 1 ], k ) ) % Mod;
Ans = ( Ans + Mod ) % Mod;
}
for( LL j = m; j >= i; --j )
A[ j ] -= A[ i ];
}
printf( "%lld
", Ans );
return;
}
int main() {
Init();
LL Cases;
scanf( "%lld", &Cases );
for( ; Cases; --Cases ) Work();
return 0;
}