木门行业网站该怎么做,网站seo监测,丽之鑫科技网站后台怎么做,团员建设网站uoj#422. 【集训队作业2018】小Z的礼物
题目描述
Solution
所有礼物全部取到的方案数并不好求#xff0c;因此我们考虑min−maxmin-maxmin−max容斥#xff0c;转化为第一次取到集合中某一个的期望时间。
令pn∗(m−1)m∗(n−1)pn*(m-1)m*(n-1)pn∗(m−1)m∗(n−1)表示有…uoj#422. 【集训队作业2018】小Z的礼物
题目描述
Solution
所有礼物全部取到的方案数并不好求因此我们考虑min−maxmin-maxmin−max容斥转化为第一次取到集合中某一个的期望时间。
令pn∗(m−1)m∗(n−1)pn*(m-1)m*(n-1)pn∗(m−1)m∗(n−1)表示有多少个1∗21*21∗2矩阵的选取方案。 倘若此时有xxx种1∗21*21∗2的矩阵与枚举的集合TTT有交不难证明期望的步数即为px\frac{p}{x}xp。
所以我们直接枚举集合TTT计算xxx就可以以O(2numnum)O(2^{num}num)O(2numnum)的时间求出答案numnumnum表示有多少个∗*∗号。
这样显然会超时。
我们发现n≤6n\leq 6n≤6因此考虑状压dpdpdp从第一列开始一列一列转移记录轮廓线上的信息令f[S][j]f[S][j]f[S][j]表示轮廓线的状态为SSS目前有jjj个1∗21*21∗2矩阵与TTT有交的方案数并且将容斥系数一起带入其中计算。
时间复杂度O(2nnmp)O(2^nnmp)O(2nnmp)。
#include vector
#include list
#include map
#include set
#include deque
#include queue
#include stack
#include bitset
#include algorithm
#include functional
#include numeric
#include utility
#include sstream
#include iostream
#include iomanip
#include cstdio
#include cmath
#include cstdlib
#include cctype
#include string
#include cstring
#include ctime
#include cassert
#include string.h
//#include unordered_set
//#include unordered_map
//#include bits/stdc.h#define MP(A,B) make_pair(A,B)
#define PB(A) push_back(A)
#define SIZE(A) ((int)A.size())
#define LEN(A) ((int)A.length())
#define FOR(i,a,b) for(int i(a);i(b);i)
#define fi first
#define se secondusing namespace std;templatetypename Tinline bool upmin(T x,T y) { return yx?xy,1:0; }
templatetypename Tinline bool upmax(T x,T y) { return xy?xy,1:0; }typedef long long ll;
typedef unsigned long long ull;
typedef long double lod;
typedef pairint,int PR;
typedef vectorint VI;const lod eps1e-11;
const lod piacos(-1);
const int oo130;
const ll loo1ll62;
const int mods998244353;
const int MAXN600005;
const int INF0x3f3f3f3f;//1061109567
/*--------------------------------------------------------------------*/
inline int read()
{int f1,x0; char cgetchar();while (c0||c9) { if (c-) f-1; cgetchar(); }while (c0c9) { x(x3)(x1)(c^48); cgetchar(); }return x*f;
}
char st[10][105];
int f[2][105][1205],inv[1205];
inline int upd(int x,int y){ return xymods?xy-mods:xy; }
int main()
{int nread(),mread(),pn*(m-1)m*(n-1);for (int i1;in;i) scanf(%s,st[i]1);inv[0]inv[1]1;for (int i2;i1200;i) inv[i]1ll*inv[mods%i]*(mods-mods/i)%mods;int pre1,now0;f[now][0][0]mods-1;for (int i1;im;i)for (int j1;jn;j){now^1,pre^1;memset(f[now],0,sizeof f[now]);for (int S0;S1n;S)for (int k0;kp;k)if (f[pre][S][k]){if (st[j][i]*){int _SS|(1(j-1)),_kk(jn)(im);_k(!((S(j-2))1)j1);_k(!((S(j-1))1)i1);f[now][_S][_k]upd(f[now][_S][_k],mods-f[pre][S][k]);}int _SS(((1n)-1)^(1(j-1)));f[now][_S][k]upd(f[now][_S][k],f[pre][S][k]);}}int ans0;for (int i0;i1n;i)for (int j1;jp;j) ansupd(ans,1ll*f[now][i][j]*p%mods*inv[j]%mods);printf(%d\n,ans); return 0;
}
