2611. [HZOI 2016]你猜是不是DP V2

【题目描述】

小绿帽同学在做了“2587. [HZOI 2015]你猜是不是DP”后发现自己学会了DP的正确姿势，

于是它非常开心的点开了一道新的题，并且它成功的列出了DP的方程！！

然而那道题的正解是O(nlogn^3)的（小绿帽怎么可能会～），但是小绿帽却列出了n^2的DP方程。

所以还是请你帮助小绿帽同学完成这道题。

下面是小绿帽同学的DP方程：

for(int i=1;i<=n;i++)

    for(int j=1;j<=n;j++)

        f[i][j]=get(f[i-1][j]);

for(int i=1;i<=n;i++)

    for(int j=1;j<=n;j++) {

        f[i][j]+=f[get(f[i-1][j])][get(f[i-1][j]+1)];

        ans+=f[i][j];

    }

其中f[0][1...n]的值由输入给出，ans%p的值即为答案。

其中get()函数是这个样子滴～

int get(int x) {

   x%=p;

   return (x^(x>>7)^(x<<3)^(x>>2))%n+1;

}

你可以认为这个方程就是对的，那么接下来交给你了，帮助小绿帽小朋友解决这个DP问题吧！

【输入格式】

第一行两个整数n,p

第二行n个整数表示f[0][1...n]

【输出格式】

一个整数ans.

【样例输入】

5 2



1 2 3 4 5

【样例输出】

0

【提示】

共18个测试点。

第1~5个测试点每个4分，n<=2000;

第6～13个测试点每个5分，n<=8000;

第14～18个测试点每个8分,n<=11500;

对于第i个测试点,p为第i个素数。

对于18个测试点，n均为4的倍数。

【来源】

一只名字很长的蒟蒻