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

2019/05/31 14:36

题目背景

91029102 年 99 月 11 日，百度在 X 市 XX 中学举办了一场 AI 知识小课堂，本场 AI 知识小课堂老师教授了一些矩阵的相关知识，因为矩阵在 AI 人工智能中也有相当的应用。

题目描述

1 2 3 4 5 6 7 8 9 ...
2 3 4 5 6 7 8 9 10 ...
3 4 5 6 7 8 9 10 11 ...
4 5 6 7 8 9 10 11 12 ...
5 6 7 8 9 10 11 12 13 ...
6 7 8 9 10 11 12 13 14 ...
7 8 9 10 11 12 13 14 15 ...
8 9 10 11 12 13 14 15 16 ...
9 10 11 12 13 14 15 16 17 ...
... ... ... ... ... ... ... ... ... ...

数据范围

a<b\le 10^{18},c<d\le 10^{18}a<b1018,c<d1018。

样例输入复制

1 3 4 6

样例输出复制

108

d为公差，

#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';
}
}
}

0
0 收藏

0 评论
0 收藏
0