【codechef】Chef and Strange Formula（找规律，灵活题）

不正狼

　　

Input:
5 7
1 2 3 4 5
Output:
6
Explanation

F(1) = 1 * (1! + 1) = 2
F(2) = 1 * (1! + 2) + 2 * (2! + 2) = 3 + 8 = 11
F(3) = 1 * (1! + 3) + 2 * (2! + 3) + 3 * (3! + 3) = 4 + 10 + 27 = 41
F(4) = 1 * (1! + 4) + 2 * (2! + 4) + 3 * (3! + 4) + 4 * (4! + 4) = 5 + 12 + 30 + 112 = 159
F(5) = 1 * (1! + 5) + 2 * (2! + 5) + 3 * (3! + 5) + 4 * (4! + 5) + 5 * (5! + 5) = 794
F(1) + F(2) + F(3) + F(4) + F(5) = 2 + 11 + 41 + 159 + 794 = 1007
1007 modulo 7 = 6
有一个规律：1*1！+2*2！+...+n*n! = (n-1)!-1
可以转化F(x)=x*(1+2+...+x)+1*1！+2*2！+...+x*x!
　　

x*x*(x+1)/2取模的时候要注意分奇偶情况：奇数时，/2和x+1归一起；偶数时，/2和x归一起
如果x>m，那么(x-1)!肯定含有一项是m，因此(x-1)! = 0，(x-1)!-1 =-1;
http://www.codechef.com/problems/STFM/　　

#include <cstdio>
#include <cstring>
#include <iostream>
#define ll long long
using namespace std;
int x[10000001];
int fact[10000001];
int main(){
int n,m;
scanf(&quot;%d%d&quot;,&n,&m);
ll max=0;
for(int i=0;i<n;++i){
scanf(&quot;%I64d&quot;,&x);
if(x>max&&x<m-1) //找出最大值(大于m-1直接不考虑(含有公因子m))
max=x;
}
ll f=1,sum=0,t1,t2,t3;
for(ll i=1;i<=max+1;++i){  //i-1的阶乘
f*=i;
f%=m;
fact[i-1]=f;
}
for(int i=0;i<n;++i){
if(x>m||fact[x]==0)
sum+=m-1;  //sum-1
else
sum+=fact[x]-1;
if(x%2==0){   //x为偶数，可以直接/2
t1=(x/2)%m;
t2=x%m;
t3=(x+1)%m;
sum=sum+(((t1*t2)%m)*t3)%m; // x*x*(x+1)/2
}
else{    //x+1为偶数，可以/2
t1=x%m;
t2=((x+1)/2)%m;
sum=sum+(((t1*t1)%m)*t2)%m; // x*x*(x+1)/2
sum=sum%m;
}
}
printf(&quot;%I64d\n&quot;,sum);
return 0;
}