 D. Token Removing)
被组合数学+动态规划整的不知天地为何物了，这玩意经常遇到就算了，还经常不会，至此我打算开篇新的篇章专门记录组合数学➕动态规划的ac之路......
简洁题意：在给定整数 n[1,5000] 和 m
[1e8,1.01e9] 的情况下，m作为最终答案的模数，n是序列的长度，序列总共有 (n+1) ! 种，序列中的每个元素保证小于等于该元素位置的索引大小，比如序列上第 i 个元素的值只能是 [ 0 , i ] （按这个规则的话总共是有(n+1) ! 种不同的合法序列），对于每个序列，求从左到右遍历一遍的情况下，有几种不同的操作方法，具体操作方法指的是：对于当前 i 位上的元素x，在x非0的情况下，必须选择 [ x , i ]中的任何一个在之前没被选过的数（也就是说1 到 n中的元素只能被选一次，但不要求必须选择），如果x==0，则什么都不能选，可以发现遍历一边序列总共有n次操作（每次操作要么选一个没被选过的非0的数；要么不选，可以认为是选0，0选择的次数不限制），对于一个序列两种操作方法不同指的是只要存在任意次操作不一致（也就是在遍历某位元素时选的数不一样）。求对于 (n+1) ! 种序列的不同的操作方法总和。
比如n=3,一个合法的序列是[0 , 2 , 1 ],那么一共有两种操作方法：一：选0,选2,选1. 二：选0,选2,选3。
要是没看懂题意的可以直接看原题：https://codeforces.com/contest/2119/problem/D
组合数学的套路基本是正面求解等于无解，至少我目前的理解是这样的，那么直接考虑从别的方向入手，直接思考如果是每次都选0（也就是一个元素都不选，这里选元素指的是只选择非0元素）的操作对应的序列有哪些，再考虑操作只选一个元素的序列有哪些，再考虑操作选两个元素的序列有哪些，依次类推到选n个元素的序列有多少个，直接把这些个数累加即是答案。选0个元素毋庸置疑只有一种序列那就是【0，0，0，0，0.....】，选一个元素的话可以只选1或者2或者3....或者n，一个合理的思路是直接从大到小选元素，比如一开始我可以考虑如果只操作一次选最大的元素n的话，那么合理序列只有 [0 ,0 ,0 ,....., val ]，最后的这个 val[ 1,n ],因为我可以选择 [ val , n ]的元素，所以可选的序列有n种，说白了就是对于现在的要操作的第k大的元素可以在某一位选的方法有(n-k+1)种，并且可选择的位置有( k - j )个，j 指的是先操作过的更大的元素的个数，现在考虑对于要操作第 i+1 大的数，已经操作了 j 个更大的数的情况下，有两种情况，一个是选择操作第 i+1 大的数( dp[ i+1 ][ j+1 ] = dp[ i ][ j ]*( n - i )*( i - j + 1 ) )，一个是选择不操作它( dp[ i+1 ][ j ] = dp[ i ][ j ] )，对于第一个状态转移方程中的 dp[ i ][ j ] 的含义指的是在前 i 个大的数中，操作了 j 个数，那么还剩( i - j )个多余的位置可以让 第 i+1 大的数选择，为什么可以选？因为对于越大的数它的范围( x, y ) 中的 y 是更大的，完全满足大于第 i+1 大的数，注意第一大的数是n，这里理解可能有点难受，后面有( i - j) 个空余的位置，加上这个数自己本身的位置就是（ i - j + 1 ）个位置了，其中( n - i )的含义指的是，比如我要选x,那么对于 ( val , x ) 中的 val 的取值有 [1 , x ]，总共其实就是 ( n - ( i + 1 ) + 1)种选法，至此思路已经全部讲完了，这题的难点在于建立新的组合计数模型来用动态规划的方式计数。下面是本人ac代码：
#import "bits/stdc++.h" using namespace std; using ll = long long; using lll = __int128; using u64 = unsigned long long; using u128 = __uint128_t; using ldb = long double; using db = double; #define pb push_back #define ps push #define lowbit(x) x&-x #define all(a) a.begin(),a.end() #define all_(a,b) a.begin()+b,a.end() #define rep(i, a, b) for(ll i=a;i<=b;i++) #define per(i, a, b) for(ll i=a;i>=b;i--) #define rall(a) a.rbegin(),a.rend() #define dbg() cerr<<"|--------------------------------------------|"<<endl; #define fir first #define sec second const ll mod = 998244353; const int inf=0x3f3f3f3f; const ll INF=0x3f3f3f3f3f3f3f3f; inline u64 _pow(u64 x, u64 i, u64 mod, bool ok) {u64 ans = 1;while (i) {if (i & 1)ans = (ok ? (u128)ans * x % mod : ans * x);i >>= 1;x = (ok ? (u128)x * x % mod : x * x);}return ans;} std::mt19937_64 rng(time(0)); ll _gcd(ll a,ll b){ll az=__builtin_ctz(a),bz=__builtin_ctz(b);ll shift=min(az,bz);a>>=az;ll dif=0;while (b) {b>>=bz;dif=b-a;if (dif<0)dif=-dif;a=b,b=dif;bz=__builtin_ctz(b);}return a<<shift;} ll _x,_y,_px,_py; void exgcd(ll a,ll b){if(!b)_x=1,_y=0;else{exgcd(b,a%b);_px=_x;_py=_y;_x=_py;_y=_px-a/b*_py;}} u64 mul_mod(u64 a, u64 b, u64 mod) {return (u128)a * b % mod;} u64 pow_mod(u64 a, u64 d, u64 mod) {u64 res = 1;while (d) {if (d & 1) res = mul_mod(res, a, mod);a = mul_mod(a, a, mod);d >>= 1;}return res;} bool miller_rabin(u64 n) {if (n < 2) return false;u64 d = n - 1, s = 0;while ((d & 1) == 0) d >>= 1, ++s;auto check = [&](u64 a) {if (a % n == 0) return true;u64 x = pow_mod(a, d, n);if (x == 1 || x == n - 1) return true;for (u64 i = 1; i < s; ++i) {x = mul_mod(x, x, n);if (x == n - 1) return true;}return false;};u64 bases[] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022, 0};for (u64 a : bases) {if (a == 0) break;if (!check(a)) return false;}return true;} u64 f_rho(u64 x, u64 c, u64 mod) {return (mul_mod(x, x, mod) + c) % mod;} u64 pollard_rho(u64 n) {if (n % 2ULL == 0) return 2;static std::mt19937_64 rng((uint64_t)chrono::steady_clock::now().time_since_epoch().count());while (true) {u64 c = rng() % (n - 1) + 1;u64 x = rng() % n, y = x, d = 1;while (d == 1) {x = f_rho(x, c, n);y = f_rho(f_rho(y, c, n), c, n);u64 diff = x > y ? x - y : y - x;d = _gcd(diff, n);}if (d != n) return d; }} // 上述火车头完全不用管，只需要看下面代码就完全够用 void solve() { ll n,m;cin>>n>>m; vector<vector<ll>>dp(n+1,vector<ll>(n+1,0)); dp[0][0]=1; rep(i,0,n-1) { rep(j,0,i) { (dp[i+1][j+1]+=dp[i][j]*(n-i)%m*(i-j+1)%m)%=m; (dp[i+1][j]+=dp[i][j])%m; } } ll ans=0; rep(i,0,n)(ans+=dp[n][i])%=m; cout<<ans<<endl; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); ll t;cin>>t; for (ll i=1;i<=t;i++) { // cerr<<"case -> "<<i<<endl; solve(); } return 0; }
