CFR 622 F. The Sum of the k-th Powers ( Lagrange's Interpolation, Math )
題意:
令 f( k, x ) = sum( pow( i, k ) for i in range( 1, x + 1 ) ) % ( 1e9 + 7 )。
問 f( K, N ) 是多少。
制約:
1 ≤ N ≤ 1e9
0 ≤ K ≤ 1e6
解法:
很神奇,還沒看到這題的時候我就有想過手算一樣的問題了,還蠻顯然是用拉格朗日。
首先觀察到 f( k, x ) 的通式是 k + 1 次的多項式。用拉格朗日插值要有 k + 2 個 ( x, f( k, x ) ),就可以找出通式。為了方便,求的是 x <- [ 1, k + 2 ]。
時間 / 空間複雜度:
O( K lg MOD )
#include <bits/stdc++.h> using namespace std; const int MAXN = int( 1e9 ); const int MAXK = int( 1e6 ); const int MOD = int( 1e9 ) + 7; int int_pow( int v, int p ) { int res = not ( v == 0 and p ); while( p ) { if( p & 1 ) { res = 1LL * res * v % MOD; } p >>= 1; v = 1LL * v * v % MOD; } return res; } int inv( int v ) { return int_pow( v, MOD - 2 ); } int fact[ MAXK + 1 + 1 ]; int N, K; int f[ MAXK + 2 + 1 ]; signed main() { ios::sync_with_stdio( 0 ); cin >> N >> K; for( int i = fact[ 0 ] = 1; i <= K + 1; ++i ) { fact[ i ] = 1LL * fact[ i - 1 ] * i % MOD; } for( int i = 1; i <= K + 2; ++i ) { f[ i ] = ( f[ i - 1 ] + int_pow( i, K ) ) % MOD; } if( N <= K + 2 ) { cout << f[ N ] << endl; exit( 0 ); } int xmj = 1; for( int i = 1; i <= K + 2; ++i ) { xmj = 1LL * xmj * ( N - i ) % MOD; } int ans = 0; for( int i = 1; i <= K + 2; ++i ) { int p = 1LL * f[ i ] * xmj % MOD * inv( N - i ) % MOD * inv( 1LL * fact[ i - 1 ] * fact[ K + 2 - i ] % MOD ) % MOD; if( K + 2 - i & 1 ) p *= -1; ( ans += p ) %= MOD; } if( ans < 0 ) ans += MOD; cout << ans << endl; return 0; }