题意描述

小 T 有 $n$ 个桶和 $2n − 1$ 个球,其中第 $i$ 个桶能装前 $2i − 1$ 个球。每个桶只能
装一个球。

现在小 T 取了 $m$ 个桶和 $m$ 个球,并将这些球各自放在这些桶里。问这样的方案有多少?两种方案不同当且仅当选择了不同的桶或球或者同一个桶在两种方案放了不同的球。

由于方案的数量可能很大,所以只需要求方案数模 $998244353$ 后的结果。


输入格式

从输入文件 ball.in 中读入数据。

第一行一个整数 $T$,表示数据组数。

接下来 $T$ 行,每行两个整数 $n, m$,含义见【问题描述】。


输出格式

输出到文件 ball.out 中。

输出共 $T$ 行,每行一个整数表示一组数据的答案。


Input & Output ‘s examples

Input ‘s eg

4
1 1
2 1
2 2
3 2

Output ‘s eg

4
1 1
2 1
2 2
3 2

数据范围与约定

测试点编号 $n \leq$ $m \leq$
$1$ $5$ $5$
$2$ $10$ $10$
$3$ $15$ $15$
$4$ $100$ $100$
$5$ $100000$ $100$
$6$ $100000$ $100$
$7$ $100000$ $100$
$8$ $100000$ $100000$
$9$ $10^7$ $10^7$
$10$ $10^7$ $10^7$

对于 $100\%$ 的测试点,保证 $1 ≤ T ≤ 10^5 , 1 ≤ m ≤ n ≤ 10^7$。


分析

考场上找出了规律,然后抄错式子就爆零了

70pts

$70$ 分的做法是一个比较直观的 $\text{dp}$。

设 $f[i][j]$ 为用了 $i$ 个桶,$j$ 个球的方案数。

之后分两种情况进行转移:

  • 若第 $i$ 个桶没有放球,则有 $f[i - 1][j]$ 种方案。
  • 若第 $i$ 个桶放了球,则先考虑前 $i - 1$ 个桶的状况,一共有 $f[i - 1][j - 1]$ 种不同的方案,而第 $i$ 个桶放的球必须在剩下的 $(2i - 1) - (j - 1) = 2i - j$ 个球中选择,则共有 $(2i - j) \times f[i - 1][j - 1]$ 种不同的方案。

综上所述,有 $f[i][j] = f[i - 1][j] + (2i - j) \times f[i - 1][j - 1]$。

初始化为 $f[i][0] = 1 (i \in \lbrack 0 , 10^5 \rbrack)$

代码也很好写:

#include <algorithm>
#include <iostream>
#include <cstring>
#include <iomanip>
#include <cstdlib>
#include <climits>
#include <cstdio>
#include <bitset>
#include <string>
#include <vector>
#include <cctype>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
#include <set>

#define I inline
#define fi first
#define se second
#define pb push_back
#define MP make_pair
#define PII pair<int , int>
#define PSL pair<string , long long>
#define PLL pair<long long , long long>
#define all(x) (x).begin() , (x).end()
#define copy(a , b) memcpy(a , b , sizeof(b))
#define clean(a , b) memset(a , b , sizeof(a))
#define rep(i , l , r) for (int i = (l); i <= (r); i ++)
#define per(i , r , l) for (int i = (r); i >= (l); i --)
#define PE(i , x) for(int i = head[x]; i; i = edge[i].last)
#define DEBUG(x) std :: cerr << #x << '=' << x << std :: endl

typedef long long ll;
typedef unsigned long long ull;

template <class T>
inline void read(T &x) {
char c = getchar(), f = 0; x = 0;
while (!isdigit(c)) f = (c == '-'), c = getchar();
while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
x = f ? -x : x;
}

using namespace std;

const int N = 10000 + 5;
const int M = 100000 + 5;
const int HA = 998244353;

ll f[100005][105];

void prepare(){
f[0][0] = 1;
f[1][1] = 1;

rep(i , 0 , 100000) f[i][0] = 1;

rep(i , 2 , 100000){
rep(j , 1 , min(i , 100)){
ll tmp = 1ll * (2 * i - j) % HA * f[i - 1][j - 1] % HA;
f[i][j] = f[i - 1][j] + tmp % HA , f[i][j] %= HA;
}
}
}


void solve() {
ll n , m;
read(n) , read(m);
printf("%lld\n" , f[n][m] % HA);
}

#define LOCAL

int main() {
#ifdef LOCAL
freopen("ball.in" , "r" , stdin);
freopen("ball.out" , "w" , stdout);
#endif
prepare();
int t; read(t);
while(t --) solve();

return 0;
}

100pts

$10^7$ 的数据范围与 $10^5$ 的询问次数已经明确表示标算一定是 $O(T \log n)$ 或 $O(T)$ 的。

考虑打表找规律(其实表也不用打因为有大样例)可知:

证明如下:


Code[Accepted]

#include <algorithm>
#include <iostream>
#include <cstring>
#include <iomanip>
#include <cstdlib>
#include <climits>
#include <cstdio>
#include <bitset>
#include <string>
#include <vector>
#include <cctype>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
#include <set>

#define I inline
#define fi first
#define se second
#define pb push_back
#define MP make_pair
#define PII pair<int , int>
#define PSL pair<string , long long>
#define PLL pair<long long , long long>
#define all(x) (x).begin() , (x).end()
#define copy(a , b) memcpy(a , b , sizeof(b))
#define clean(a , b) memset(a , b , sizeof(a))
#define rep(i , l , r) for (int i = (l); i <= (r); i ++)
#define per(i , r , l) for (int i = (r); i >= (l); i --)
#define PE(i , x) for(int i = head[x]; i; i = edge[i].last)
#define DEBUG(x) std :: cerr << #x << '=' << x << std :: endl

typedef long long ll;
typedef unsigned long long ull;

template <class T>
inline void read(T &x) {
char c = getchar(), f = 0; x = 0;
while (!isdigit(c)) f = (c == '-'), c = getchar();
while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
x = f ? -x : x;
}

using namespace std;

const int N = 10000 + 5;
const int M = 10000000 + 5;
const int HA = 998244353;

ll fac[M] , inv[M];

ll Pow(ll a , ll n){
if(n == 0) return 1;
if(n == 1) return a % HA;
ll mid = Pow(a , n / 2) % HA;
if(n & 1) return mid * mid % HA * a % HA;
else return mid * mid % HA;
}

void prepare(int lim){
fac[0] = 1;
rep(i , 1 , lim){
fac[i] = fac[i - 1] * i % HA;
}
inv[lim] = Pow(fac[lim] , HA - 2);
per(i , lim , 1){
inv[i - 1] = inv[i] * i % HA;
}
}

ll C(ll n , ll m){
return fac[n] * inv[m] % HA * inv[n - m] % HA;
}

void solve() {
ll n , m;
read(n) , read(m);
printf("%lld\n" , C(n , m) * C(n , m) % HA * fac[m] % HA);
}

//#define LOCAL

int main() {
#ifdef LOCAL
freopen("ball.in" , "r" , stdin);
freopen("ball.out" , "w" , stdout);
#endif
prepare((int)1e7 + 1);

int t; read(t);
while(t --) solve();


return 0;
}



THE END