ARC059C

· · 题解

提供一个复杂度 O(n^2 \log n) 但是并不会跑得更快（而且一定跑得更慢）的算法
而且是嘴巴的没去写过
其实只是来水题解的

首先我们来考虑 O(n^3) 做法。
假如 \{x_i\} 已经确定了，怎么计算。
设 f_{i,j} 表示考虑前 i 个 a，并且总和为 j 的时候，前 i 个的乘积。那么可以简单地列出转移方程。

f_{i,j}=\sum_{k=0}^j f_{i-1,j-k}\cdot x_i^k

然后我们把 x_i^k 替换成 \sum _{l=a_i}^{b_i} l^k 就是正确答案。
因为考虑你每一位选的 x 是互相独立的，然后每一位选的 a 也是独立的，所以这样就是正确答案。

代码： 

int n,c;
int a[N],b[N];
int p[N][N],s[N][N],f[N][N],S[N][N];
signed main()
{
    rd(n);rd(c);
    for (int i=1;i<=n;i++) rd(a[i]);
    for (int i=1;i<=n;i++) rd(b[i]);
    for (int i=1;i<=400;i++) {int t=1;for (int j=0;j<=c;j++) {p[i][j]=t;t=t*i%mod;}}
    for (int k=0;k<=c;k++) for (int i=1;i<=400;i++) s[i][k]=(s[i-1][k]+p[i][k])%mod;
    for (int k=0;k<=c;k++) for (int i=1;i<=n;i++) S[i][k]=s[b[i]][k]-s[a[i]-1][k];
    f[0][0]=1;
    for (int i=1;i<=n;i++) for (int j=0;j<=c;j++) for (int k=0;k<=j;k++) f[i][j]=(f[i][j]+f[i-1][j-k]*S[i][k])%mod;
    cout<<(f[n][c]+mod)%mod<<endl;
}

我们发现 for (int i=1;i<=n;i++) for (int j=0;j<=c;j++) for (int k=0;k<=j;k++) f[i][j]=(f[i][j]+f[i-1][j-k]*S[i][k])%mod;
这个是复杂度瓶颈，然后发现这是个卷积形式。
那么我们用 MTT 或者三模 NTT 之类的就能降低复杂度。
但是显然会跑得更慢