Ebi-chan and Integer Sequences [ACPC2017 Day3 B]

http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=ACPC2017Day3&pid=B

解法

http://judge.u-aizu.ac.jp/onlinejudge/creview.jsp?rid=2539904&cid=ACPC2017Day3

まず、等差数列の基本であるが、初項a,公差d,長さnの数列の末項はa+(n-1)*dとなる。

次に何かを全探索して答えを導く解法を考えてみる。
ここで公差dを固定して考えてみると、

ll d = 1;
while(1) {
    ll a = 0;
    ll b = 1LL * (N - 1) * d;
    if (M < b) break;
    ans += M - b + 1;
    d++;
}

という感じになる。
答えにM - b + 1としているのは、初項を0と仮定すると[0,b]までの数になるということは、bがMになるまで初項を増やせるということ。
末項をbとすると、初項は[0,M-b]まで取りうるので、(M-b+1)通りある。

あとは、公差dが負の時は正の時と全く同じで、公差d=0の時は(M+1)通りの初項が考えられるので、答えは「(公差0の組み合わせ) + 2*(公差が正の組み合わせ)」である。

この解法では、公差が正の時の計算方法でTLEする。
ここで取りうる公差の最大をokとして考えてみると、組み合わせは

{M - (N - 1) * 1 + 1} + {M - (N - 1) * 2 + 1} + ... + {M - (N - 1) * ok + 1}
= (M + 1) * ok - (N - 1) (1 + 2 + ... + ok)
= (M + 1) * ok - (N - 1) ok (ok + 1) / 2

あとは、okが求まれば答えであるが、二分探索で求めよう。
ちなみに二分探索の計算過程で10^18越える可能性があるので、上限付きmulを使おう。

typedef long long ll;
typedef long double ld;
#define INF 1LL<<60
ld lginf = -1;
ll mul(ll a, ll b) {
    if (lginf < 0) lginf = log10l(INF); ld aa = log10l(a), bb = log10l(b);
    if (lginf <= aa + bb) return INF; return a * b;
}




ll N, M;
int mod = 1000000007;
//--------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
 
    if (N == 1) {
        int ans = (M + 1) % mod;
        cout << ans << endl;
        return;
    }
 
    ll ok = 0, ng = M + 1;
    while (ok + 1 != ng) {
        ll d = (ok + ng) / 2;
        ll b = mul(N - 1, d);
        if (M < b) ng = d;
        else ok = d;
    }
 
    mint ans = mint((M + 1) % mod) * mint(ok % mod);
    ans -= mint(ok%mod) / 2 * (mint((N - 1) % mod) + mint((N - 1) % mod) * mint(ok % mod));
    ans *= 2;
    ans += (M + 1) % mod;
    cout << ans << endl;
}