Boi Tinh Ban

Code

#include <bits/stdc++.h>
#define int long long
#define endl "\n"

using namespace std;

const int N = 3e6+5;
const int MOD = 10;
const int phi10 = 4;

int n,m,a[N], fact[N];
int p2[N], p5[N];

int pw(int a, int b) {
    if (b == 0)
        return 1;
    int tmp = pw(a, b/2)%MOD;
    tmp = (tmp*tmp)%MOD;
    if (b&1)
        tmp = (tmp * (a%MOD))%MOD;
    return tmp;
}

int CKN(int k, int n) {
    int cnt2 = p2[n] - p2[n-k] - p2[k];
    int cnt5 = p5[n] - p5[n-k] - p5[k];
    int res = ((fact[n]*pw(fact[n-k], phi10-1)%MOD)*pw(fact[k], phi10-1))%MOD;
    res *= pw(2, cnt2);
    res %= MOD;
    res *= pw(5, cnt5);
    res %= MOD;
    return res;
}

void build() {
    int n = 1e6;
    fact[0] = 1;
    for (int i=1;i <= n;i++) {
        p2[i] = p2[i-1];
        p5[i] = p5[i-1];

        int v =i;
        while(v % 2 == 0) {
            v /= 2;
            p2[i]++;
        }
        while(v % 5 == 0) {
            v /= 5;
            p5[i]++;
        }
        fact[i] = fact[i-1]*v;
        fact[i] %= MOD;
    }
}

signed main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    build();
    cin >> n >> m;
    for (int i=1;i <= n;i++) {
        string s; cin >> s;
        a[i] = s.size();
    }
    for (int i=1;i <= m;i++) {
        string s; cin >> s;
        a[++n] = s.size();
    }
    int s1=0;
    int s2=0;
    for (int i=1;i < n;i++) {
        int val = CKN(i-1, n-2);
//        cout << val*a[i] << ' ';
        s1 += val*a[i];
        s1 %= MOD;
    }
    for (int i=2;i <=  n;i++) {
        s2 += CKN(i-2, n-2)*a[i];
        s2 %= MOD;
    }
    cout << s1 << s2;


    return 0;
}