|
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("%d%d",&n,&m);
ll max=0;
for(int i=0;i<n;++i){
scanf("%I64d",&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("%I64d\n",sum);
return 0;
}
|
|
|