Time Limit: 2 sec / Memory Limit: 1024 MB

Score : <var>600600</var> points

Problem Statement

Snuke has a blackboard and a set <var>SS</var> consisting of <var>NN</var> integers. The <var>ii</var>-th element in <var>SS</var> is <var>SiSi</var>.

He wrote an integer <var>XX</var> on the blackboard, then performed the following operation <var>NN</var> times:

  • Choose one element from <var>SS</var> and remove it.
  • Let <var>xx</var> be the number written on the blackboard now, and <var>yy</var> be the integer removed from <var>SS</var>. Replace the number on the blackboard with <var>xmodyxmody</var>.

There are <var>N!N!</var> possible orders in which the elements are removed from <var>SS</var>. For each of them, find the number that would be written on the blackboard after the <var>NN</var> operations, and compute the sum of all those <var>N!N!</var> numbers modulo <var>109+7109+7</var>.

Constraints

  • All values in input are integers.
  • <var>1≤N≤2001≤N≤200</var>
  • <var>1≤Si,X≤1051≤Si,X≤105</var>
  • <var>SiSi</var> are pairwise distinct.

Input

Input is given from Standard Input in the following format:

<var>NN</var> <var>XX</var>
<var>S1S1</var> <var>S2S2</var> <var>……</var> <var>SNSN</var>

Output

Print the answer.

Sample Input 1 Copy

Copy 
2 19
3 7

Sample Output 1 Copy

Copy 
3
  • There are two possible orders in which we remove the numbers from <var>SS</var>.
  • If we remove <var>33</var> and <var>77</var> in this order, the number on the blackboard changes as follows: <var>19→1→119→1→1</var>.
  • If we remove <var>77</var> and <var>33</var> in this order, the number on the blackboard changes as follows: <var>19→5→219→5→2</var>.
  • The output should be the sum of these: <var>33</var>.

Sample Input 2 Copy

Copy 
5 82
22 11 6 5 13

Sample Output 2 Copy

Copy 
288

Sample Input 3 Copy

Copy 
10 100000
50000 50001 50002 50003 50004 50005 50006 50007 50008 50009

Sample Output 3 Copy

Copy 
279669259
  • Be sure to compute the sum modulo <var>109+7109+7</var>.

 

题意：

给定一个数x和一个含有n个数的数组。

将数组排成任意顺序（即一共有N！种顺序组合），然后扫一遍数组，x对a[i] 取模，余数代替x，然后对下一个数进行同样的操作。

直到扫完整个数组。最后得到的数是num

然后把所有顺序组合得到的num全加起来就是ans，需要对1e9+7取模。

 

思路：

通过分析我们可以知道，

当数组的一个数a[i]前面有一个数a[x]，并且a[x] 比 a[i] 小。那么我们分析上面的取余操作可以知道a[i]其实对答案没有任何影响。

因为在对a[i]取余之前的数值x，已经比a[i]小了，因为对a[x]取余过了，一个小数对大数取余，没有改变的。

那么我们对数组从大到小排序后，

定义dp[i][j] 表示，排列了前i个数后，当前值x为j的所有情况数。

转移有两种，

如果a[i] 数放在 i位置，

那么我们知道他对i位置 j%a[ i ] 的贡献是上一个位置i-1的j的数量。

如果a[i] 不放在这个位置。

它放在后面的n-i的任意位置都可以，而且对当前位置i的j即dp[i][j]的贡献就是dp[i-1][j] ，因为这一位的 a[i] 没有影响。

 

细节见代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#define ALL(x) (x).begin(), (x).end()
#define rt return
#define dll(x) scanf("%I64d",&x)
#define xll(x) printf("%I64d\n",x)
#define sz(a) int(a.size())
#define all(a) a.begin(), a.end()
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define pii pair<int,int>
#define pll pair<long long ,long long>
#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define MS0(X) memset((X), 0, sizeof((X)))
#define MSC0(X) memset((X), '\0', sizeof((X)))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define eps 1e-6
#define gg(x) getInt(&x)
#define db(x) cout<<"== [ "<<x<<" ] =="<<endl;
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
ll powmod(ll a,ll b,ll MOD){ll ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}
inline void getInt(int* p);
const int maxn=1000010;
const int inf=0x3f3f3f3f;
/*** TEMPLATE CODE * * STARTS HERE ***/
int a[maxn];
int n;
int x;
ll dp[202][100010];
const ll mod=1e9+7;
int main()
{
    //freopen("D:\\common_text\\code_stream\\in.txt","r",stdin);
    //freopen("D:\\common_text\\code_stream\\out.txt","w",stdout);
    gbtb;
    cin>>n>>x;
    repd(i,1,n)
    {
        cin>>a[i];
    }
    sort(a+1,a+1+n,[&](int x,int y){return x>y;});
    dp[0][x]=1;
    repd(i,1,n)
    {
        repd(j,0,x)
        {
            dp[i][j%a[i]]+=dp[i-1][j];
            dp[i][j%a[i]]=(dp[i][j%a[i]]+mod)%mod;
            dp[i][j]+=dp[i-1][j]*(n-i)%mod;
            dp[i][j]=(dp[i][j]+mod)%mod;
        }
    }
    ll ans=0ll;
    repd(i,0,x)
    {
        ans+=(dp[n][i]*i)%mod;
        ans=(ans+mod)%mod;
    }
    cout<<ans<<endl;



    return 0;
}

inline void getInt(int* p) {
    char ch;
    do {
        ch = getchar();
    } while (ch == ' ' || ch == '\n');
    if (ch == '-') {
        *p = -(getchar() - '0');
        while ((ch = getchar()) >= '0' && ch <= '9') {
            *p = *p * 10 - ch + '0';
        }
    }
    else {
        *p = ch - '0';
        while ((ch = getchar()) >= '0' && ch <= '9') {
            *p = *p * 10 + ch - '0';
        }
    }
}