外包公司做网站的流程,免费自建商城网站,河北网站建设与制作,注册公司邮箱需要什么Codeforces 1065 E. Side Transmutations
题目描述
题意#xff1a;一个字符串长度为#xff0c;字符集大小为 #xff0c;再给出种交换方式#xff0c;表示可以交换。如果两个不同的串能够通过任意的交换方式得到相同的串#xff0c;则视为相同#xff0c;求方案数。…Codeforces 1065 E. Side Transmutations
题目描述
题意一个字符串长度为字符集大小为 再给出种交换方式表示可以交换。如果两个不同的串能够通过任意的交换方式得到相同的串则视为相同求方案数。
Solution
同构求方案数按剧本Burnside。
若字符串中每个字符都不同则我们任意选择中的交换方式都可以得到一个新的字符串即任意选择的元素都能得到不同的置换因此置换有种。 现在考虑置换中的不动点个数和。
题目中的递增我们先让 没有限制方案数为。
现在考虑每一对相邻的显然每一对的方案数相互独立总方案数是各自方案数的乘积。
如果选择区间 那么这个区间必须和的串相同因此该区间字符确定方案数为1。
如果不选择这个区间那么这也是无限制的区间方案数为。
因此一对的方案数为。
总方案数 时间复杂度是线性的。
#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;
}
int inv2(mods1)1,a[MAXN];
int solve(int x,int y)
{if (y0) return 1;int qsolve(x,y1);return (y1)?1ll*q*q%mods*x%mods:1ll*q*q%mods;
}
int main()
{int nread(),mread(),kread();for (int i1;im;i) a[i]read();int anssolve(k,n-a[m]);for (int im;i1;i--) a[i]-a[i-1],ans1ll*ans*(1solve(k,a[i]))%mods*inv2%mods;printf(%d\n,ans);return 0;
}
