【BZOJ 4574】【ZJOI 2016】線分樹

式:http://www.cnblogs.com/Dragon-Light/p/6475923.html 問題の解き方が少しまちがっているかもしれないので修正する
各数を列挙し、f[k][i][j]がk輪以降のi~j区間の数が列挙した数に等しいものよりも小さいことを示す案数とする.この[i,j]の範囲は厳密であることに注意してください.すなわち、i−1番目とj+1番目の数はいずれも大きいです.(言い換えれば、いずれも上限を超えている)明らかに、この数が影響できる範囲は、左の最初の数より大きい数から右の最初の数より大きい数までである.この最大範囲を[l,r]とする.f[k][i][j]=Σi−1 u=l(f[k−1][u][j](u−1)+Σrv=j+1(f[k−1][i][v](n−v)+f[k−1][i][j](sum(i−1)+sum(j−i+1)+sum(j−i+1)+sum(n−j))のうち、sum(x)は区間サイズxのサブ区間数、すなわちx*(x+1)/2を表す.
この公式を説明する.1つ目のケースは、[u,j]という区間から[i,j]という区間に縮小したことを示し、[u,i-1]という区間の数が大きくなったことを示している.i−1が右端点であることを決定し,[1,u−1]のいずれかの左端点を取っても,[u,i−1]これらの数を大きくすることができる(条件によっては,u−1番目の数は必ず中間これらの数より大きいからである).第二の状況は同じである.3つ目のケースは,区間がすべてi左側,すべてj右側,およびi,jの中間であり,この3つのケースは影響しない.
直接計算する時間の複雑さはO(q*n^4)ですが、実際にやっている間に区間がいっぱいになるわけがないので、実はこの複雑さには全く及ばず、50点も取れるようになりましたし、当時試験場でもこの点数を取る人がいたので、そうしたはずです.次の最適化を考えると、第1の状況と第2の状況は明らかに接頭辞と計算で計算することができ、このように時間の複雑度はO(q*n^3)に下がり、この複雑度も同様に過小評価されている(実際には満の3 sでも引っかかるはずだ)、このようにして70点であり、同じようにこの点数を達成する人もいて、接頭辞とを使ったはずだ.接頭辞や考えやすいように見えますが、本題の公式はもともと複雑で、試験場で公式をはっきりリストできなければ、あまり考えられません.そしてこの複雑さはUOJの上では意外にも走ることができて、基本的には2.6 sカードで行きます.しかし、本機で測定すると、10 s+..%UOJの酸素スイッチ.試験場の正解を聞いたのか?カード定数でしょうか、型取り演算を少なくすればいいです.

#include
#include
#include
#include 
#include
#include
#include
#include
#include
#define ll long long
#define inf 1000000000
#define mod 1000000007
#define N 405
#define fo(i,a,b) for(i=a;i<=b;i++)
#define fd(i,a,b) for(i=a;i>=b;i--)
using namespace std;
ll a[N],b[N],f[3][N][N],d[N],sum[N][N],rk[N];
int n,q,i,j,k,l,r;
ll res;
bool cmp(const int &x,const int &y) {return a[x]<a[y];}
int c(int x) {return x*(x+1)>>1;}
void check(int l,int r,int x)
{
    int i,j,k;
    //memset(f,0,sizeof(f));
    fo(i,l,r) fo(j,i,r) f[0][i][j] = 0; 
    f[0][l][r] = 1;
    fo(k,1,q)
        {
            fo(i,l,r) d[i] = 0;
            fo(i,l,r)
                {
                    fo(j,i,r)
                        {
                            f[k&1][i][j] =  d[j] % mod;
                            d[j] += (f[(k-1)&1][i][j] * (i - 1)) % mod;
                        }
                }

            fo(i,l,r)
                {
                    ll t = 0;
                    fd(j,r,i)
                        {
                            f[k&1][i][j] = (f[k&1][i][j] + t) % mod; 
                            t = (t + f[(k-1)&1][i][j] * (n - j)) % mod;
                        }
                }

            fo(i,l,r) d[i] = 0;
            fo(i,l,r)
                {
                    fo(j,i,r) f[k&1][i][j] =  (f[k&1][i][j] + d[j]) % mod;
                    d[j] += (f[(k-1)&1][i][j] * (i - 1)) % mod;
                }

            fo(i,l,r)
                fo(j,i,r)
                    f[k&1][i][j] = (f[k&1][i][j] + f[(k-1)&1][i][j] * (c(i-1) + c(j-i+1) + c(n-j))) % mod;
        }   
    fo(i,l,r)
        {
            ll t = 0;
            fd(j,r,i)
                {
                    t = (t + f[q&1][i][j]) % mod;
                    sum[j][rk[x]] = (sum[j][rk[x]] + t) % mod;  
                }
        }

}
int main()
{
    scanf("%d%d",&n,&q);
    fo(i,1,n) scanf("%d",&a[i]); fo(i,1,n) b[i] = i; sort(b+1,b+n+1,cmp);
    fo(i,1,n) rk[b[i]] = i;
    fo(i,1,n)
        {
            l = i; while (a[l-1] <= a[i] && l > 1) l--;
            r = i; while (a[r+1] <= a[i] && r < n) r++;
            check(l,r,i);
        }
    fo(i,1,n)
        {
            res = 0;
            fo(j,1,n)
                {
                    if (!sum[i][j]) continue;
                    fo(k,1,j-1) sum[i][j] -= sum[i][k];
                    while (sum[i][j] < 0) sum[i][j] += mod;
                    res = (res + a[b[j]] * sum[i][j])%mod; 
                    res %= mod;
                }
            while (res < 0) res += mod; res %= mod; printf("%lld",res);
            if (i != n) printf(" "); else printf("
");
        }
    return 0;
}