Codeforces Round #506 (Div. 3) D. Concatenated Multiples

D. Concatenated Multiples

You are given an array n positive integers.

Let's call a concatenation of numbers 123456.

Count the number of ordered pairs of positions k.

Input

The first line contains two integers 2≤k≤109).

The second line contains 1≤ai≤109).

Output

Print a single integer — the number of ordered pairs of positions k.

Examples

input

Copy

6 11
45 1 10 12 11 7

output

Copy

input

Copy

4 2
2 78 4 10

output

Copy

input

Copy

5 2
3 7 19 3 3

output

Copy

Note

In the first example pairs 11.

In the second example all n(n−1) pairs suffice.

In the third example no pair is sufficient.

题意：给出n个数，再给一个mod，然后现在有一种方法说是，可以把任意两个数连接起来，问你连接起来的对数取余mod等于0的有多少个

思路：乍一看没什么思路，暴力肯定不行，10^5的数n^2就炸了，我们就要想怎么去优化他，我们可以考虑预处理然后遍历一遍

我们先给出一个例子 给出n个数和一个mod，求多少对加起来mod等于0？

这个n^2也不行，但是我们想一下如果我取余一个数=x 的话我要什么情况才能让这个数加一个数%mod等于0

我们只有（x+y）%mod == 0 那在我们知道x的情况，我们只要找 mod-y的余数个数有多少即可

同理我们可以推理到这个题:因为是连接 12 34 我们相当于看成是 1200+34即可，就成功转移到了以上问题

因为连接不同的数的时候后面紧跟的0的个数不同，我们只要存下一个0到十个0所有的都用map存下即可

然后特别的，最后判断下自身加自身会不会也可以被mod为0，如果是的话-1

map<ll,ll> mp[11]

mp[j][x] 代表的是 j个0余数为x的个数

#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<string>
#include<iostream>
#include<queue>
#include<algorithm>
#define mod 1000000007
using namespace std;
typedef long long ll;
int n,m;
int main()
{
    int a[200001];
    map<ll,ll> mp[11];
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
        ll x=a[i];
        for(int j=1;j<=10;j++)//预处理存余数个数
        {
            x*=10;
            x%=m;
            mp[j][x]++;
        }
    }
    ll sum=0;
    for(int i=0;i<n;i++)
    {
        int t=a[i]%m;
        int len=log10(a[i])+1;
        sum+=mp[len][(m-t)%m];  //加上与当前数连接余数为0的个数
        ll x=1;
        for(int j=1;j<=len;j++) x=(x*10)%m;  //除去自身
        if(((a[i]*x)%m+a[i]%m)%m==0) sum--;
    }
    printf("%I64d",sum);
}

Codeforces Round #506 (Div. 3) D. Concatenated Multiples

相关推荐