SRM501 Div1 Medium(500), Div2 Hard(1000) FoxAverageSequence
動的計画法。数列の合計・直前のA[i]の値・A[i-1]≦A[i]が成り立つか、のそれぞれに対してbeautifulな数列の個数を覚えておく。A[i-1]の値は必要ない。
#include <vector> using namespace std; class FoxAverageSequence{public: int theCount( vector <int> seq ) { int M = 1000000007; int n = (int)seq.size(); static int T[40][1601][41][2]; // [p][s][a][f] // sum[0≦i≦p]A[i] = s // A[i] = a // f==0ならばA[p-1]>A[p] f==1ならばA[p-1]≦A[p] // なる数列の個数 memset(T,0,sizeof T); for ( int a=0; a<=40; a++ ) if ( seq[0]==-1 || seq[0]==a ) T[0][a][a][1]++; for ( int p=1; p<n; p++ ) for ( int s=0; s<=40*p; s++ ) for ( int a0=0; a0<=40; a0++ ) if ( seq[p]==-1 || seq[p]==a0 ) if ( a0*p<=s ) for ( int a1=0; a1<=40; a1++ ) { if ( a1<=a0 ) T[p][s+a0][a0][a1<=a0] += T[p-1][s][a1][0], T[p][s+a0][a0][a1<=a0] %= M; T[p][s+a0][a0][a1<=a0] += T[p-1][s][a1][1]; T[p][s+a0][a0][a1<=a0] %= M; } int ans = 0; for ( int s=0; s<=40*n; s++ ) for ( int a=0; a<=40; a++ ) for ( int f=0; f<=1; f++ ) ans += T[n-1][s][a][f], ans %= M; return ans; }};