点击查看代码
#include <bits/stdc++.h>
#define fi first
#define se second
using std :: cin;
using std :: min;
using std :: max;
using std :: cout;
using std :: vector;
constexpr int M = 2e6 + 5;
constexpr int INF = 0x3f3f3f3f, mod = 998244353;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef std :: pair < int, int > pii;
//char buf[1 << 23], *p1 = buf, *p2 = buf, obuf[1 << 23], *O = obuf;
//#define getchar() (p1 == p2) && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2)? EOF : *p1++
inline int read() {
int f = 1, s = 0; char ch = getchar();
while(!isdigit(ch)) (ch == '-') && (f = -1), ch = getchar();
while(isdigit(ch)) s = s * 10 + ch - '0', ch = getchar();
return f * s;
}
namespace Solver {
char _st;
int n, m, a[M], h[M], mu[M], prime[M], vis[M], w[M], pri[M];
inline void sieve(int n) {
mu[1] = 1; int cnt = 0; pri[1] = 1;
for(int i = 2; i <= n; ++i) {
if(!vis[i]) prime[++cnt] = i, mu[i] = -1, pri[i] = i;
for(int j = 1; j <= cnt && prime[j] * i <= n; ++j) {
vis[prime[j] * i] = 1, pri[prime[j] * i] = prime[j]; if(i % prime[j] == 0) break ;
mu[prime[j] * i] = -mu[i];
}
}
for(int i = 1, v; i <= n; ++i) if(mu[i]) for(int j = i, k = 1; j <= n; j += i, ++k) (h[k]) && (w[j] += mu[i]);
}
int id[M], cnt[M], deg[M], f1[M], f2[M];
inline int gcd(int a, int b) {return !b ? a : gcd(b, a % b);}
inline int link(int x, int y) {return ((a[x] < a[y]) ^ h[gcd(a[x], a[y])]);}
inline int rd(int n) {return (ll)rand() * rand() % n + 1;}
const int N = 1e6 + 5;
vector < pii > P[N]; int W, cur;
inline void dfs(int x, int z, int s) {
if(x == s) return W += cnt[z] * w[z], cnt[z] ++, void(); int lim = P[cur][x].se, b = P[cur][x].fi;
for(int i = 0, c = 1; i <= lim; ++i, c *= b) dfs(x + 1, z * c, s);
}
char _ed;
inline void mian() {
// fprintf(stderr, "%d\n", (&_st - &_ed) >> 20);
srand((unsigned)time(NULL));
n = read(), m = read(); for(int i = 1; i <= m; ++i) h[i] = read();
for(int i = 1; i <= n; ++i) a[i] = read(), id[i] = i; sieve(m);
std :: sort(id + 1, id + n + 1, [](int x, int y) {return a[x] < a[y];});
ll ans = (ll)n * (n - 1) * (n - 2) / 6;
for(int i = 1; i <= n; ++i) {
int x = id[i], z = a[x];
while(z > 1) {
int g = pri[z], c = 0; while(pri[z] == g) ++c, z /= g;
P[i].push_back(pii(g, c));
} cur = i, W = 0;
dfs(0, 1, P[i].size());
f1[i] = W;
} memset(cnt, 0, sizeof(cnt));
for(int i = n; i; --i) {
int x = id[i]; cur = i, W = 0; dfs(0, 1, P[i].size());
W = n - i - W, f2[i] = W, deg[x] = f1[i] + f2[i], ans -= (ll)deg[x] * (deg[x] - 1) / 2;
}
cout << ans << '\n';
std :: iota(id + 1, id + n + 1, 1), std :: sort(id + 1, id + n + 1, [] (int x, int y) {return deg[x] > deg[y];});
for(int i = 1, x; i <= n; ++i) if(deg[x = id[i]] != n - i) for(int j = i + 1; j <= n; ++j) if(link(id[j], id[i])) for(int k = i + 1; k <= n; ++k) if(k != j && link(id[k], id[j]) && link(id[i], id[k])) return cout << id[j] <<' ' << id[i] << ' ' << id[k] << '\n', void();
}
} ;
点击查看代码
#include<bits/stdc++.h>
#define ci const int
#define upd() (nx[a]=b,fr[b]=a)
using namespace std;
char buf[1<<20],*p1=buf,*p2=buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
int read(){int res(0);char ch(getchar());while(ch<48||ch>57)ch=getchar();while(ch>=48&&ch<=57)res=(res<<1)+(res<<3)+(ch^48),ch=getchar();return res;}
void out(ci x){x>9?out(x/10),putchar(x%10+48):putchar(x%10+48);}
ci N=2005;
int n,q1,q2,id[N],fr[N],nx[N];
int tmp[N],F[N];
bitset<N>ok[N];
bool in[N];
void ins(ci x){
int l=N,r=0;
for(int i=1;i<=n;++i)
if(in[i]){
if(ok[i][x])r=r>id[i]?r:id[i];
else l=l<id[i]?l:id[i];
}
nx[x]=fr[x]=x;
if(l==N&&r==0)id[x]=1;
else if(l==N){
id[x]=0;
for(int i=1;i<=n;++i)if(in[i]&&id[i]>=id[x])id[x]=id[i]+1;
}
else if(r==0){
id[x]=1;
for(int i=1;i<=n;++i)id[i]+=in[i];
}
else if(r+1==l){
for(int i=1;i<=n;++i)id[i]+=in[i]&&id[i]>=l;
id[x]=l;
}
else{
if(l!=r){
for(int i=l;i<=r;++i)tmp[i]=F[i]=0;
for(int i=1;i<=n;++i)
if(in[i]){
ci Id=id[i];
if(Id^l&&Id^r)tmp[Id]=i;
else if(Id==l){
if(ok[x][i])tmp[Id]=i;
}
else if(Id==r){
if(ok[fr[i]][x])tmp[Id]=i;
}
}
for(int i=l;i<=r;++i)if(tmp[i])F[i]=fr[tmp[i]];
for(int i=l;i<r;++i){
ci a=F[i],b=tmp[i+1];
upd();
}
int a=F[r],b=x;
upd(),a=x,b=tmp[l],upd();
}
else{
for(int i=1;i<=n;++i)
if(in[i]&&id[i]==l&&ok[i][x]&&ok[x][nx[i]]){
ci v=nx[i];
int a=i,b=x;
upd(),a=x,b=v,upd();
break;
}
}
for(int i=1;i<=n;++i)
if(in[i]){
if(l<=id[i]&&id[i]<=r)id[i]=l;
else if(id[i]>r)id[i]-=(r-l);
}
id[x]=l;
}
in[x]=1;
}
int pos[N],q[N];
struct Cir{
int len;
vector<int>nd;
vector<int>cur;
vector<vector<short> >sum;
void build(){
len=nd.size();
for(int i=0;i<len;++i)
pos[nd[i]]=i,
nd.push_back(nd[i]);
sum.resize(len<<1),cur.resize(len<<1);
for(int i=0;i<len<<1;++i){
sum[i].resize(len<<1);
for(int j=0;j<len<<1;++j)
sum[i][j]=(j?sum[i][j-1]:0)+ok[nd[i]][nd[j]];
}
}
vector<int>Get(int s,vector<int>del){
ci cnt=del.size();
vector<int>ans;
for(int x:del)if(x==s)return ans;
if(!cnt){
for(int i=pos[s];i<pos[s]+len;++i)ans.push_back(nd[i]);
return ans;
}
for(int i=0;i<len<<1;++i)cur[i]=0;
s=pos[s];
for(int i=0;i<cnt;++i)del[i]=pos[del[i]];
sort(del.begin(),del.end());
vector<int>l,r,suf;
for(int i=0;i<cnt;++i){
int j=(i+1)%cnt;
if(del[j]>del[i])l.push_back(del[i]+1),r.push_back(del[j]-1);
else l.push_back(del[i]+1),r.push_back(del[j]-1+len);
suf.push_back(r.back()+1);
if(l.back()>r.back())l.pop_back(),r.pop_back(),suf.pop_back();
}
ci siz=l.size();
int Id=0;
for(int i=0;i<siz;++i){
if(l[i]<=s&&s<=r[i]){
Id=i;
break;
}
if(l[i]<=s+len&&s+len<=r[i]){
Id=i,s+=len;
break;
}
}
suf[Id]=s;
int lq=0;
for(int i=s;i<=r[Id];++i)q[++lq]=i;
while(lq){
ci x=q[lq];
if(cur[x]==siz)ans.push_back(x),--lq;
else{
ci i=cur[x];
++cur[x];
for(int p=suf[i]-1;p>=l[i]-1;--p)
if(p==l[i]-1||sum[x][l[i]-1]==sum[x][p]){
for(int k=p+1;k<suf[i];++k)q[++lq]=k;
suf[i]=p+1;
break;
}
}
}
for(int i=0;i<ans.size();++i)ans[i]=nd[ans[i]];
reverse(ans.begin(),ans.end());
return ans;
}
vector<int>Getall(vector<int>del){
if(del.empty())return Get(nd[0],del);
else{
for(int x:del){
ci p=(pos[x]+1)%len;
vector<int>tmp=Get(nd[p],del);
if(tmp.size()==len-del.size())return tmp;
}
}
}
}C[N];
bool vis[N];
int cnt;
void Work(ci tp){
vector<int>del,ot;
ci s=read();
for(int k=read();k;--k)del.push_back(read());
for(int i=id[s];i<=cnt;++i){
vector<int>tmp;
for(int x:del)
if(id[x]==i)
tmp.push_back(x);
vector<int>gt;
if(i==id[s])gt=C[i].Get(s,tmp);
else gt=C[i].Getall(tmp);
for(int x:gt)ot.push_back(x);
}
out(ot.size());
if(tp)putchar(32);
if(tp)for(int x:ot)out(x),putchar(32);
puts("");
}
int main(){
freopen("star.in","r",stdin);
freopen("star.out","w",stdout);
n=read(),q1=read(),q2=read(),read();
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j){
char c=getchar();
while(c!='0'&&c!='1')c=getchar();
ok[i][j]=c=='1';
}
for(int i=1;i<=n;++i)ins(i);
memset(tmp,0,sizeof(tmp));
for(int i=1;i<=n;++i)tmp[id[i]]=i;
for(int i=1;i<=n;++i)
if(tmp[i]){
++cnt;
int x=tmp[i];
while(!vis[x])vis[x]=1,C[cnt].nd.push_back(x),x=nx[x];
}
for(int i=1;i<=cnt;++i)
C[i].build();
while(q1--)Work(1);
while(q2--)Work(0);
return 0;
}
点击查看代码
#include<bits/stdc++.h>
using namespace std;
namespace Solve{
typedef long long ll;
const int N=510,mod=1e9+7;
inline void Add(int&x,int y){
x=(x+y>=mod?x+y-mod:x+y);
}
inline void Sub(int&x,int y){
x=(x-y<0?x-y+mod:x-y);
}
int jc[N],ny[N];
int qmi(int a,int b){
int r=1;
for(;b;b>>=1){
if(b&1)r=(ll)r*a%mod;
a=(ll)a*a%mod;
}
return r;
}
void prepare_C(int nn){
jc[0]=1;
for(int i=1;i<=nn;i++)jc[i]=(ll)jc[i-1]*i%mod;
ny[nn]=qmi(jc[nn],mod-2);
for(int i=nn;i;i--)ny[i-1]=(ll)ny[i]*i%mod;
}
int n,A,B;
char s[N];
namespace SolveB1{
int f[N],g[N];
void solve(){
f[1]=1;
for(int i=2;i<=n;i++){
memset(g,0,sizeof g);
for(int j=1;j<i;j++)
if(f[j])
for(int k=1;k<=i;k++){
int oa=((j<k)==(s[i-1]=='<'));
if(oa){
Add(g[k],(ll)f[j]*A%mod);
}
else{
Add(g[k],f[j]);
}
}
memcpy(f,g,sizeof f);
}
int ans=0;
for(int i=1;i<=n;i++)Add(ans,f[i]);
cout<<ans;
}
}
int C[N][N];
int f[N][N][3],g[N][N][3];//len cnt
int h[N];
void main(){
cin>>n>>A>>B;
cin>>(s+1);
if(B==1){
SolveB1::solve();
return;
}
prepare_C(n);
for(int i=0;i<=n;i++){
C[i][0]=1;
for(int j=1;j<=i;j++)C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
}
f[0][1][0]=1;
f[0][0][1]=B-1;
f[1][1][2]=1;
f[0][1][2]=1;
for(int i=2;i<=n;i++){
memset(g,0,sizeof g);
memset(h,0,sizeof h);
for(int k=0;k<=n;k++){
int ct=0;
for(int j=0;j<=n;j++){
if(f[k][j][0]){
int v=f[k][j][0];
if(s[i-1]=='<'){
v=(ll)v*(1-A+mod)%mod;
}
else{
v=(ll)v*(A-1)%mod;
}
Add(g[k][j+1][0],v);
if(k)Add(g[k-1][j+1][0],(ll)v*k%mod);
v=(ll)v*(B-1)%mod*ny[j]%mod;
Add(h[k+j],v);
}
if(f[k][j][1]){
if(j){
int v=f[k][j][1];
if(s[i-1]=='<'){
v=(ll)v*(1-A+mod)%mod;
}
else{
v=(ll)v*(A-1)%mod;
}
Add(g[k][j-1][1],v);
Add(g[k-1][j-1][1],(ll)v*k%mod);
}
else{
int v=f[k][j][1]%mod;
if(s[i-1]=='<'){
v=(ll)v*A%mod;
}
else{
}
Add(ct,v);
}
}
if(f[k][j][2]){
//link
int v=f[k][j][2];
if(s[i-1]=='<'){
v=(ll)v*(1-A+mod)%mod;
}
else{
v=(ll)v*(A-1)%mod;
}
if(k){
Add(g[k-1][j+1][2],(ll)v*k%mod*k%mod);
Add(g[k][j+1][2],(ll)v*k*2%mod);
}
Add(g[k+1][j+1][2],v);
Add(g[k][j+1][2],v);
//cut
v=(ll)f[k][j][2]*ny[j]%mod;
if(s[i-1]=='<'){
v=(ll)v*A%mod;
}
else{
}
Add(ct,v);
}
}
if(ct){
int v=ct;
Add(g[k][1][0],v);
if(k)Add(g[k-1][1][0],(ll)v*k%mod);
if(k){
Add(g[k-1][1][2],(ll)v*k%mod*k%mod);
Add(g[k][1][2],(ll)v*k*2%mod);
}
Add(g[k+1][1][2],v);
Add(g[k][1][2],v);
v=(ll)v*(B-1)%mod;
Add(h[k],v);
}
}
for(int k=0;k<=n;k++)
if(h[k]){
for(int jj=0;jj<=k;jj++){
Add(g[k][jj][1],(ll)C[k][jj]*h[k]%mod);
}
}
memcpy(f,g,sizeof f);
}
int ans=0;
for(int j=0;j<=n;j++)
for(int k=0;k<=n;k++){
if(f[k][j][1]){
if(j==0&&k==0){
Add(ans,f[k][j][1]);
}
}
if(f[k][j][2]){
if(k==0){
Add(ans,(ll)f[k][j][2]*ny[j]%mod);
}
}
}
cout<<ans;
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
freopen("perm.in","r",stdin);
freopen("perm.out","w",stdout);
Solve::main();
return 0;
}