2019 计蒜之道 初赛 第二场 A 百度AI小课堂-矩阵问题 ( 等差数列求和公式)

#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 ***/
const ll mod = 332748118ll;
ll qmul(ll x, ll y) { // ??????????? ???p * p????ll??????????? O(1)??????????????????
    return (x * y - (long long)(x / (long double)mod * y + 1e-3) * mod + mod) % mod;
    /*
    ll ret = 0;
    while(y) {
        if(y & 1)
            ret = (ret + x) % mod;
        x = x * 2 % mod;
        y >>= 1;
    }
    return ret;
    */
}
ll exgcd(ll l, ll r, ll &x, ll &y)
{
    if (r == 0) {x = 1; y = 0; return l;}
    else
    {
        ll d = exgcd(r, l % r, y, x);
        y -= l / r * x;
        return d;
    }
}
ll mod_inverse(ll a, ll m)
{
    ll x, y;
    if (exgcd(a, m, x, y) == 1) //ax+my=1
        return (x % m + m) % m;
    return -1;//?????
}

int main()
{
    // freopen("D:\\common_text\\code_stream\\in.txt","r",stdin);
    //freopen("D:\\common_text\\code_stream\\out.txt","w",stdout);
    // ll test=2e18;
    // cout<<test<<endl;
    ll a, b, c, d;
    cin >> a >> b >> c >> d;
    ll num = c + a - 1ll;
    num %= mod;
    ll n = b - a + 1ll;
    n %= mod;
    // ll temp=((2ll*num)%mod)*n%mod+(n*(n-1ll))%mod;
    ll temp = (qmul(qmul(2ll, num), n) + qmul(n, n - 1ll)) % mod;
    temp %= mod;
    // db(temp);
    n = d - c + 1ll;
    n %= mod;
    // cout<<n<<endl;
    ll gd = (b - a + 1ll);
    ll inv = mod_inverse(2ll, mod);
    ll ans = (qmul(temp, n) + qmul(qmul(n, n - 1ll), gd)) % mod;
    // cout<<temp*n%mod<<" "<<((n*(n-1ll))%mod*6ll*inv)%mod<<endl;
    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‘;
        }
    }
}