結果

問題 No.802 だいたい等差数列
コンテスト
ユーザー zengyongxu-jerry
提出日時 2026-06-24 22:21:38
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
RE  
実行時間 -
コード長 2,013 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,312 ms
コンパイル使用メモリ 331,820 KB
実行使用メモリ 15,360 KB
最終ジャッジ日時 2026-06-24 22:21:49
合計ジャッジ時間 10,696 ms
ジャッジサーバーID
（参考情報） 		judge1_1 / judge3_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 29 RE * 1
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second
const int N = 1.5e6 + 5, M = 1e6 + 5;
const int inf = 1e9, mod = 1e9 + 7;
const ll INF = 1e18;

int fac[N], inv[N];

int qpow(int a, int b){
	int res = 1;
	while (b){
		if (b & 1) res = 1ll * res * a % mod;
		a = 1ll * a * a % mod, b >>= 1;
	}
	return res;
}
void init(){
	fac[0] = 1;
	for (int i = 1; i < N; i ++ ) fac[i] = 1ll * fac[i - 1] * i % mod;
	inv[N - 1] = qpow(fac[N - 1], mod - 2);
	for (int i = N - 2; i >= 0; i -- ) inv[i] = 1ll * inv[i +1] * (i + 1) % mod; 
}
int C(int n, int m){
	if (n < m) return 0;
	return 1ll * fac[n] * inv[m] % mod * inv[n - m] % mod;
}
void solve(){
	int n, m, D1, D2;
	cin >> n >> m >> D1 >> D2;
	
	int res = 0, lim = m - (n - 1) * D1 - 1;
	if (lim < 0){
		cout << "0\n";
		return ;
	}
	for (int i = 0; i < n; i ++ ){
		if (lim - i * (D2 - D1 + 1) < 0) break;
		int cnt = 1ll * C(n - 1, i) * C(lim - i * (D2 - D1 + 1) + n, n) % mod;
		if (i & 1) res = ((res - cnt) % mod + mod) % mod;
		else res = (res + cnt) % mod;
	}
	cout << res << "\n";
}

signed main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int T = 1; //cin >> T;
	while (T -- ) init(), solve();
}

/*

T3 好似神秘题
b[i] = a[i] - a[i - 1] 
b[1] = a[1]

于是 sigma b[i] <= m, 1 <= b[1]
D1 <= b[i] <= D2

c[i] = b[i] - D1
c[1] = b[1]
于是 sigma c[i] <= m - (n - 1)D1, 1 <= c[1]
0 <= c[i] <= D2 - D1

c[1] = b[1] - 1
0 <= c[1 .. n]
c[2 .. n] <= D2 - D1
sigma c[i] <= m - (n - 1)D1 - 1

并不是 = m - (n - 1)D1 - 1，咋办
考虑，<= 我们就新增一个 c[0] = (m - ...) - c[1 .. n] 
lim = m - ...
lim + n + 1 个数，分成 n + 1 个正整数 
不考虑上界，就是 C(lim + n, n) 

我去经典容斥，前几天刚听 apiadu 讲完啊！/cy 

如果 x 个违反
0 <= c[0 .. n]
sigma c[i] <= lim

变成了
0 <= d[0 .. n]
sigma d[i] <= lim - x(D2 - D1 + 1) 

C(lim + n, n) 变成了 C(lim - x(D2 - D1 + 1) + n, n)
轻松！ 
 
*/
0