z怎么建设视频网站淘宝客网站制作教程

z怎么建设视频网站,淘宝客网站制作教程,开发手机网站用什么好,北京国税局网站官网入口被组合数学动态规划整的不知天地为何物了#xff0c;这玩意经常遇到就算了#xff0c;还经常不会#xff0c;至此我打算开篇新的篇章专门记录组合数学➕动态规划的ac之路...... 简洁题意#xff1a;在给定整数 n [1,5000] 和 m [1e8,1.01e9] 的情况下#xff0c;m作为…被组合数学动态规划整的不知天地为何物了这玩意经常遇到就算了还经常不会至此我打算开篇新的篇章专门记录组合数学➕动态规划的ac之路......简洁题意在给定整数 n[1,5000] 和 m[1e8,1.01e9] 的情况下m作为最终答案的模数n是序列的长度序列总共有 (n1) ! 种序列中的每个元素保证小于等于该元素位置的索引大小比如序列上第 i 个元素的值只能是 [ 0 , i ] 按这个规则的话总共是有(n1) ! 种不同的合法序列对于每个序列求从左到右遍历一遍的情况下有几种不同的操作方法具体操作方法指的是对于当前 i 位上的元素x在x非0的情况下必须选择 [ x , i ]中的任何一个在之前没被选过的数也就是说1 到 n中的元素只能被选一次但不要求必须选择如果x0则什么都不能选可以发现遍历一边序列总共有n次操作每次操作要么选一个没被选过的非0的数要么不选可以认为是选00选择的次数不限制对于一个序列两种操作方法不同指的是只要存在任意次操作不一致也就是在遍历某位元素时选的数不一样。求对于 (n1) ! 种序列的不同的操作方法总和。比如n3,一个合法的序列是[0 , 2 , 1 ],那么一共有两种操作方法一选0,选2,选1. 二选0,选2,选3。要是没看懂题意的可以直接看原题https://codeforces.com/contest/2119/problem/D组合数学的套路基本是正面求解等于无解至少我目前的理解是这样的那么直接考虑从别的方向入手直接思考如果是每次都选0也就是一个元素都不选这里选元素指的是只选择非0元素的操作对应的序列有哪些再考虑操作只选一个元素的序列有哪些再考虑操作选两个元素的序列有哪些依次类推到选n个元素的序列有多少个直接把这些个数累加即是答案。选0个元素毋庸置疑只有一种序列那就是【00000.....】选一个元素的话可以只选1或者2或者3....或者n一个合理的思路是直接从大到小选元素比如一开始我可以考虑如果只操作一次选最大的元素n的话那么合理序列只有 [0 ,0 ,0 ,....., val ]最后的这个 val[ 1,n ],因为我可以选择 [ val , n ]的元素所以可选的序列有n种说白了就是对于现在的要操作的第k大的元素可以在某一位选的方法有(n-k1)种并且可选择的位置有( k - j )个j 指的是先操作过的更大的元素的个数现在考虑对于要操作第 i1 大的数已经操作了 j 个更大的数的情况下有两种情况一个是选择操作第 i1 大的数( dp[ i1 ][ j1 ] dp[ i ][ j ]*( n - i )*( i - j 1 ) )一个是选择不操作它( dp[ i1 ][ j ] dp[ i ][ j ] )对于第一个状态转移方程中的 dp[ i ][ j ] 的含义指的是在前 i 个大的数中操作了 j 个数那么还剩( i - j )个多余的位置可以让 第 i1 大的数选择为什么可以选因为对于越大的数它的范围( x, y ) 中的 y 是更大的完全满足大于第 i1 大的数注意第一大的数是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 ia;ib;i) #define per(i, a, b) for(ll ia;ib;i--) #define rall(a) a.rbegin(),a.rend() #define dbg() cerr|--------------------------------------------|endl; #define fir first #define sec second const ll mod 998244353; const int inf0x3f3f3f3f; const ll INF0x3f3f3f3f3f3f3f3f; 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 shiftmin(az,bz);aaz;ll dif0;while (b) {bbz;difb-a;if (dif0)dif-dif;ab,bdif;bz__builtin_ctz(b);}return ashift;} ll _x,_y,_px,_py; void exgcd(ll a,ll b){if(!b)_x1,_y0;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;cinnm; vectorvectorlldp(n1,vectorll(n1,0)); dp[0][0]1; rep(i,0,n-1) { rep(j,0,i) { (dp[i1][j1]dp[i][j]*(n-i)%m*(i-j1)%m)%m; (dp[i1][j]dp[i][j])%m; } } ll ans0; rep(i,0,n)(ansdp[n][i])%m; coutansendl; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); ll t;cint; for (ll i1;it;i) { // cerrcase - iendl; solve(); } return 0; }