statement:https://www.jisuanke.com/contest/5530
赛中过题: B C E G L
J.Summon
看到循环同构问题就想到polya计数.
然后相当于求解无循环同构下的子问题.
我们可以状压, 设
为开头状态为S1,末尾状态为S2的方案数...
和
只要取到
即可..
这样子暴力转移的复杂度为，算一下极限情况下1.6e9.
但是有用的值只有
（
的约数个数）个,打表发现[1,n]约数个数最多的数只有128个，然后我们可以用矩阵来做
转移,这样复杂度为
,算一下大概3e8左右.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < n; i++)
const int N = 1e5 + 7;
const int mod = 7*17<<23|1;
int power_mod(int a, int b) {
int res = 1;
for(; b; b >>= 1, a = (ll) a * a % mod)
if(b & 1) res = (ll) res * a % mod;
return res;
}
struct Matrix {
static const int S = 64;
int e[S][S];
void clear() { memset(e, 0, sizeof e);}
Matrix() { clear();}
void E() { clear(); rep(i,S)e[i][i]=1;}
Matrix operator * (const Matrix&rhs)const {
Matrix res;
rep(i,S)rep(k,S)if(e[i][k])rep(j,S)
res.e[i][j]=(res.e[i][j]+(ll)e[i][k]*rhs.e[k][j])%mod;
return res;
}
Matrix power(ll n) const {
Matrix a = *this, res;
for(res.E(); n; n>>=1,a=a*a)
if(n&1) res=res*a;
return res;
}
};
Matrix A;
struct Info {
int e, phi;
Info operator * (const Info &rhs) const {
return Info{e*rhs.e, phi*rhs.phi};
}
};
vector<Info> getInfo(int n) {
vector<Info> res(1, Info{1, 1});
for(int i = 2; i * i <= n; i++) {
if(n % i == 0) {
Info a = {i, i - 1};
int t = 1;
while(n % i == 0) n /= i, t++;
int sz = res.size(), nsz = sz * t;
res.resize(nsz);
for(int j = sz; j < nsz; j++) {
if(j == 2 * sz) a.phi++;
res[j] = res[j - sz] * a;
}
}
}
if(n != 1) {
int sz = res.size(), nsz = sz * 2;
res.resize(nsz);
Info a = {n, n - 1};
for(int j = sz; j < nsz; j++) {
res[j] = res[j - sz] * a;
}
}
return res;
}
const int S1 = (1 << 6) - 1;
const int S2 = (1 << 8) - 1;
int n, m;
bool ok[256];
bool can[64][64];
int sum[64];
int main() {
#ifdef local
freopen("in.txt", "r", stdin);
// freopen("out1.txt", "w", stdout);
#endif
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> m;
for(int i = 0, x; i < m; i++) {
int mask = 0;
for(int j = 0; j < 4; j++) {
cin >> x;
mask = mask << 2 | x;
}
ok[mask] = 1;
}
for(int j = 0; j < 64; j++)
for(int i = 0; i < 64; i++)
for(int z = 2; z <= 6; z += 2)
can[j][i] |= ok[(i<<z|j>>6-z)&S2];
for(int i = 0; i < 64; i++)
for(int j = 0; j < 4; j++)
A.e[i][(i<<2|j)&S1] = !ok[i<<2|j];
vector<Info> Z = getInfo(n);
int sz = Z.size();
for(int i = 0; i < sz - 1 - i; i++)
swap(Z[i].phi, Z[sz - 1- i].phi);
int res = 0;
int t1 = 0, t2 = 0;
for(int i = 0; i < 4; i++) {
int mask = i << 6 | i << 4 | i << 2 | i;
if(!ok[mask]) t1 += 1;
}
for(int i = 0; i < 16; i++) {
int mask = i << 8 | i << 4 | i;
if(!ok[mask&S2]&&!ok[mask>>2&S2]) t2 += 1;
}
for(auto &e : Z) {
if(e.e >= 3) {
Matrix t = A.power(e.e - 3);
int tans = 0;
for(int i = 0; i < 64; i++)
for(int j = 0; j < 64; j++)
if(!can[i][j]) tans = (tans + t.e[i][j]) % mod;
res = (res + (ll) tans * e.phi) % mod;
} else if(e.e == 2) {
res = (res + (ll) t2 * e.phi) % mod;
} else if(e.e == 1) {
res = (res + (ll) t1 * e.phi) % mod;
}
}
res = (ll) res * power_mod(n, mod - 2) % mod;
cout << res << '\n';
return 0;
} K.Tree
树上启发式合并+线段树合并(计蒜客评测机太慢了,加快读勉强卡过...)
还有一种方法是pb_ds+启发式合并.
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define fi first
#define se second
const int N = 2e5 + 10;
int root[N], ch[N*80][2], val[N*80], tot;
void init() {
tot = 0;
}
int newnode() {
++tot;
val[tot] = 0;
memset(ch[tot], 0, sizeof ch[0]);
return tot;
}
void ins(int &o, int l, int r, int x, int v) {
if(!o) o = newnode();
val[o] += v;
if(l == r) return;
int mid = (l + r) >> 1;
if(mid >= x) ins(ch[o][0], l, mid, x, v);
else ins(ch[o][1], mid + 1, r, x, v);
}
int query(int o, int l, int r, int x) {
if(!o || r <= x) return val[o];
int mid = (l + r) >> 1;
int res = query(ch[o][0], l, mid, x);
if(mid < x) res += query(ch[o][1], mid + 1, r, x);
return res;
}
int Union(int u, int v) {
if(!u || !v) return u + v;
int rt = newnode();
val[rt] = val[u] + val[v];
ch[rt][0] = Union(ch[u][0], ch[v][0]);
ch[rt][1] = Union(ch[u][1], ch[v][1]);
return rt;
}
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
using namespace __gnu_pbds;
int n, k;
vector<int> E[N];
map<int, int> S[N];
int a[N], dep[N];
int maxdep = 0;
ll res = 0;
void calc(int o1, int o2, int l, int r, int du) {
if(!o2 || k < l - du * 2) return;
if(l == r) {
res += 2 * val[o2] * query(o1, 1, maxdep, min(k - l + du * 2, maxdep));
return;
}
int mid = (l + r) >> 1;
calc(o1, ch[o2][0], l, mid, du);
calc(o1, ch[o2][1], mid + 1, r, du);
}
void U(map<int, int> &a, map<int, int> &b, int v, int du) {
if(a.size() < b.size()) swap(a, b);
for(auto &e : b) {
auto it = a.find(2 * v - e.fi);
if(it != a.end()) {
calc(it->se, e.se, 1, maxdep, du);
}
}
for(auto &e : b) {
a[e.fi] = Union(a[e.fi], e.se);
}
}
void prepare(int u, int f) {
dep[u] = dep[f] + 1;
maxdep = max(maxdep, dep[u]);
for(auto &v : E[u]) prepare(v, u);
}
void dfs(int u, int f) {
for(auto &v : E[u]) {
dfs(v, u);
U(S[u], S[v], a[u], dep[u]);
}
ins(root[u], 1, maxdep, dep[u], 1);
S[u][a[u]] = Union(S[u][a[u]], root[u]);
}
namespace Fastio {
inline char nextchar() {
static char buf[N], *p1=buf, *p2=buf;
return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,N,stdin),p1==p2)?EOF:*p1++;
}
template<class T> int _R(T &x) {
char c = nextchar(); T sign = 1;
while(!isdigit(c)&&c!=EOF)
c=nextchar(),sign=c=='-'?-1:sign;
if(c==EOF) return -1;
for(x=0; isdigit(c); c=nextchar())
x=(x<<3)+(x<<1)+(c&15);
x *= sign;
return 1;
}
template<class T, class...Args>
int _R(T &x, Args&...args) { return min(_R(args...), _R(x));}
template<class T> void W(T x) { if(x)W(x/10), putchar(x%10+'0');}
template<class T> void _W(T x) { if(!x)putchar('0'); if(x<0)putchar('-'),x=-x; W(x);}
template<class T> void _Wn(T x) { _W(x); putchar('\n');}
template<class T, class...Args>
void _Wn(T x, Args...args) { _W(x), putchar(' '), _Wn(args...);}
};
using namespace Fastio;
int main() {
#ifdef local
freopen("in.txt", "r", stdin);
#endif
_R(n, k);
for(int i = 1; i <= n; i++) {
_R(a[i]);
}
for(int i = 2, f; i <= n; i++) {
_R(f);
E[f].push_back(i);
}
prepare(1, 0);
dfs(1, 0);
_Wn(res);
return 0;
} M.XOR Sum
对于我们对
分奇偶讨论一下就能得到表达式...
最后会化成若干项比较好求和的部分和一个自然幂级数.
用多项式求逆预处理出伯努利数然后做卷积即可.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
const int p = 1e9 + 7;
const db pi = acos(-1.0);
int power_mod(int a, int b) {
int res = 1;
for(; b; b >>= 1, a = (ll) a * a % p)
if(b & 1) res = (ll) res * a % p;
return res;
}
namespace FFT {
struct Comp {
db x, y;
Comp(){}
Comp(db _x, db _y = 0) : x(_x), y(_y){}
Comp operator + (const Comp &rhs) const {
return Comp(x + rhs.x, y + rhs.y);
}
Comp operator - (const Comp &rhs) const {
return Comp(x - rhs.x, y - rhs.y);
}
Comp operator * (const Comp &rhs) const {
return Comp(x * rhs.x - y * rhs.y, x * rhs.y + y * rhs.x);
}
Comp operator / (const db &r) const {
return Comp(x / r, y / r);
}
friend Comp conj(const Comp &r) { return Comp(r.x, -r.y);}
};
Comp Exp(const db &r) { return Comp(cos(r), sin(r));}
const int L = 18, N = 1 << L;
Comp roots[N];
int rev[N];
void fft_init() {
for(int i = 0; i < N; i++) {
rev[i] = (rev[i>>1]>>1)|((i&1)<<L-1);
}
roots[1] = {1, 0};
for(int i = 1; i < L; i++) {
db angle = 2 * pi / (1 << i + 1);
for(int j = 1 << i - 1; j < 1 << i; j++) {
roots[j << 1] = roots[j];
roots[j<<1|1] = Exp((j * 2 + 1 - (1 << i)) * angle);
}
}
}
void fft(Comp *a, int n, int idft = 0) {
assert((n & (n - 1)) == 0);
int zeros = __builtin_ctz(n), shift = L - zeros;
for(int i = 0; i < n; i++) {
if(i < (rev[i] >> shift)) {
swap(a[i], a[rev[i] >> shift]);
}
}
for(int i = 1; i < n; i <<= 1) {
for(int j = 0; j < n; j += i * 2) {
for(int k = 0; k < i; k++) {
Comp z = a[i + j + k] * (idft ? conj(roots[i + k]) : roots[i + k]);
a[i + j + k] = a[j + k] - z;
a[j + k] = a[j + k] + z;
}
}
}
if(idft) for(int i = 0; i < n; i++) a[i] = a[i] / n;
}
const Comp half = 0.5, zero = 0;
const int M = (1 << 15) - 1;
Comp fa[N], fb[N];
void conv(int *a, int *b, int *c, int l1, int l2, int eq = 0) {
int need = l1 + l2 - 1, sz = 1 << (32 - __builtin_clz(need - 1));
for(int i = 0; i < sz; i++) {
fa[i] = i < l1 ? Comp(a[i]&M, a[i]>>15) : zero;
}
fft(fa, sz);
if(eq) memcpy(fb, fa, sz * sizeof(Comp));
else {
for(int i = 0; i < sz; i++) {
fb[i] = i < l2 ? Comp(b[i]&M, b[i]>>15) : zero;
}
fft(fb, sz);
}
for(int i = 0; i <= (sz >> 1); i++) {
int j = (sz - i) & (sz - 1);
Comp xx = fa[i] * fb[i];
Comp yy = conj(fa[j]) * fb[i];
Comp zz = fa[i] * conj(fb[j]);
Comp ww = conj(fa[j]) * conj(fb[j]);
if(i != j) {
Comp _x = fa[j] * fb[j];
Comp _y = conj(fa[i]) * fb[j];
Comp _z = fa[j] * conj(fb[i]);
Comp _w = conj(fa[i]) * conj(fb[i]);
fa[j] = (_x + _y) * half;
fb[j] = (_z - _w) * half;
}
fa[i] = (xx + yy) * half;
fb[i] = (zz - ww) * half;
}
fft(fa, sz, 1);
fft(fb, sz, 1);
ll d[4];
for(int i = 0; i < need; i++) {
d[0] = fa[i].x + 0.5;
d[1] = fa[i].y + 0.5;
d[2] = fb[i].x + 0.5;
d[3] = fb[i].y + 0.5;
c[i] = (((d[2] % p) << 30) + d[0] + ((d[1] + d[3]) % p << 15)) % p;
}
}
void sqr(int *a, int *b, int l) { conv(a, a, b, l, l, 1);}
void poly_inv(int *a, int *b, int len) {
static int t[N];
if(len == 1) return b[0] = power_mod(a[0], p - 2), void(b[1] = 0);
poly_inv(a, b, (len + 1) >> 1);
sqr(b, t, (len + 1) >> 1);
conv(a, t, t, len, len);
for(int i = (len + 1) >> 1; i < len; i++) {
b[i] = (-t[i] + p) % p;
}
}
}
using namespace FFT;
int fac[N], ifac[N], B[N];
int a[N], b[N], c[N];
int t;
ll x, y;
int ff(ll n) {
if(n == 0) return 0;
int z = (n + 1) % p, now = z;
b[0] = 0;
for(int i = 1; i <= t + 1; i++) {
b[i] = (ll) now * ifac[i] % p;
now = (ll) now * z % p;
}
conv(a, b, c, t + 1, t + 2);
int res = 0, aa = 1;
for(int k = 1; k <= t; k++) {
aa = (ll) aa * 2ll * k % p;
res = (res + (ll) c[k + 1] * aa) % p;
}
return res;
}
int g(ll n) {
if(n == 0) return 0;
ll t1 = (n + 3) / 4 % p * t % p;
ll t2 = (n + 2) / 4 % p;
ll t3 = (n + 1) / 4 % p * (t / 2) % p;
ll t4 = ff(n / 2);
return (t1 + t2 + t3 + t4) % p;
}
int test_k = 1;
int C(int n, int m) {
if(n < m || m < 0) return 0;
return (ll) fac[n] * ifac[m] % p * ifac[n - m] % p;
}
int test(ll n) {
int res = 0, now = (n + 1) % p;
for(int i = test_k; i >= 0; i--) {
res = (res + (ll) C(test_k + 1, i) * B[i] % p * now) % p;
now = (ll) now * (n + 1) % p;
}
res = (ll) res * fac[test_k] % p * ifac[test_k + 1] % p;
return res;
}
int main() {
#ifdef local
freopen("in.txt", "r", stdin);
#endif
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
fft_init();
cin >> t >> x >> y;
/*
int r = 0;
for(int i = x; i <= y; i++) {
r += F(i, t);
}
cout << r << endl;*/
//t = 1000;
fac[0] = ifac[0] = 1;
for(int i = 1; i <= t + 10; i++) {
fac[i] = (ll) fac[i - 1] * i % p;
}
ifac[t + 10] = power_mod(fac[t + 10], p - 2);
for(int i = t + 9; i; i--) {
ifac[i] = (ll) ifac[i + 1] * (i + 1) % p;
}
poly_inv(ifac + 1, B, t + 5);
for(int i = 0; i <= t + 5; i++) {
a[i] = B[i];
B[i] = (ll) B[i] * fac[i] % p;
}
int res = (g(y) - g(x - 1)) % p;
if(res < 0) res += p;
cout << res << '\n';
return 0;
}
京公网安备 11010502036488号