能不能正赛场上不要脑瘫啊。
简单题做不出来直接崩了/kk。
题意
现在有 个人和 和球队,满足如下条件:
- 任何一个人都至少是一个球队的球迷,并且没有人同时是所有球队的球迷;
- 对于任意两个球队 ,都恰好存在一个球队
,满足球队 的球迷恰好是 的并;
- 对于任意两个球队 ,都恰好存在一个球队
,满足球队 的球迷恰好是 的交;
计算方案数。多测。
,。
题解
考虑球迷最多的队伍
和任意一个其他队伍 。
此时一定要存在一个队伍 ,使得
的球迷是 的并,那么 的球迷个数显然是 的。
所以唯一的可能是 ,这说明
的球迷应该包含其他所有球队的球迷。
又因为每一个人至少是一个球队的球迷,所以所有人肯定都是 的球迷。
所以意思就是说,肯定有一个球队,使得 个人都是他的球迷。
同理,肯定还有一个球队,没有球迷。
所以现在已经只需要确定剩下 个队伍的方案数。
考虑直接暴搜。
此时所有的人可以被分为
类。
那么直接
枚举一下,每一类人的个数是 还是
。
然后暴力判断是否合法即可。
后面还需要计算把 个人分入
组的方案数,可能需要一个容斥。
时间复杂度 。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111
| #include<bits/stdc++.h> #define inf 0x3f3f3f3f3f3f3f3fll #define debug(x) cerr<<#x<<"="<<x<<endl using namespace std; using ll=long long; using ld=long double; using pli=pair<ll,int>; using pi=pair<int,int>; template<typename A> using vc=vector<A>; inline int read() { int s=0,w=1;char ch; while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1; while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar(); return s*w; } inline ll lread() { ll s=0,w=1;char ch; while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1; while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar(); return s*w; } const int mod=1000000007; const int L=20; const int P=4; bool vis[100005]; ll C[25][25]; ll dp[25][25]; int v[6]; inline ll qow(ll a,ll b) { ll ans=1; while(b) { if(b&1) ans=ans*a%mod; a=a*a%mod; b>>=1; } return ans; } void dfs(int num,int now) { if(num==(1<<P)) { if(!now) return ; for(int j=0;j<P;j++) vis[v[j]]=1; vis[0]=vis[now]=1; for(int j=1;j<=P;j++) { bool f=1; for(int p=0;p<j;p++) if(!v[p]||v[p]==now) f=0; for(int p=j;p<P;p++) if(v[p]) f=0; for(int p=0;p<j;p++) for(int q=p+1;q<j;q++) { if(v[p]==v[q]) f=0; if(!vis[v[p]&v[q]]) f=0; if(!vis[v[p]|v[q]]) f=0; } if(f) dp[j+2][__builtin_popcount(now)]++; } for(int j=0;j<P;j++) vis[v[j]]=0; vis[0]=vis[now]=0; return ; } for(int i=0;i<2;i++) { int V=i<<num; for(int j=0;j<P;j++) if(num&(1<<j)) v[j]^=V; dfs(num+1,now|V); for(int j=0;j<P;j++) if(num&(1<<j)) v[j]^=V; } } int main() { for(int i=0;i<=L;i++) { C[i][0]=C[i][i]=1; for(int j=1;j<i;j++) C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod; } dfs(0,0);
int T=read(); while(T--) { ll n=lread();int m=read();ll ans=0; if(m==2) { printf("2\n"); continue; } for(int i=1;i<=L;i++) if(dp[m][i]) { ll V=0; for(int j=0;j<=i;j++) { ll val=qow(i-j,n)*C[i][j]%mod; if(j&1) V-=val; else V+=val; } (ans+=dp[m][i]*V)%=mod; } ans=(ans%mod+mod)%mod; ans=ans*m%mod*(m-1)%mod; printf("%lld\n",ans); } return 0; }
|
题意
有
次操作和一个初始为空的字符串。
每一次操作是往这个字符串开头或结尾加入一个字符。
每次操作结束后输出当前的字符串有多少种循环节。
。
题解
我觉得这没做出来也太脑瘫了
考虑一个长度
在什么时候会是这个字符串的循环节。
可以发现,这个范围一定是一段区间,并且这个区间的左端点为 。
考虑二分右端点,问题变为如何判断一个字符串是否有长度为 的循环节。
假设这个字符串为 。
当
时,可以发现只需要判断是否有 。
当
时,先把前面完整的段判完,在单独判后面一小段即可。
哈希,启动。时间复杂度 。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93
| #include<bits/stdc++.h> #define inf 0x3f3f3f3f3f3f3f3fll #define debug(x) cerr<<#x<<"="<<x<<endl using namespace std; using ll=long long; using ld=long double; using pli=pair<ll,int>; using pi=pair<int,int>; template<typename A> using vc=vector<A>; inline int read() { int s=0,w=1;char ch; while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1; while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar(); return s*w; } const int mod=1004535809; const int base=173; int pre[1000005]; int a[2000005]; ll h[2000005]; ll p[2000005]; int l[1000005]; int r[1000005]; char s[20]; int n; inline int get1() { scanf("%s",s+1); if(s[1]=='p') return 0; return 1; } inline int get2() { scanf("%s",s+1); if(s[1]=='d') return 1; if(s[1]=='r') return 2; if(s[1]=='m') return 3; if(s[1]=='f') return 4; if(s[2]=='o') return 5; if(s[1]=='l') return 6; return 7; } inline ll get(int l,int r) { ll ans=h[r]-h[l-1]*p[r-l+1]; return (ans%mod+mod)%mod; } inline bool check(int len,int id) { int L=l[id],R=r[id]; int num=(R-(L+len-1))/len,RR=L+(num+1)*len-1; if(get(L,RR-len)!=get(L+len,RR)) return false; int s=R-RR; return get(RR+1,R)==get(L,L+s-1); } inline ll get(int len) { int ans=len; for(int i=524288;i;i>>=1) if(ans+i<=n&&check(len,ans+i)) ans+=i; return ans; } int main() { n=read(); get1();l[1]=r[1]=n;a[n]=get2()+114; for(int i=2;i<=n;i++) { int op=get1(); if(op==1) { l[i]=l[i-1]-1,r[i]=r[i-1]; a[l[i]]=get2()+114; } else { l[i]=l[i-1],r[i]=r[i-1]+1; a[r[i]]=get2()+114; } } p[0]=1; for(int i=1;i<2*n;i++) { h[i]=(h[i-1]*base+a[i])%mod; p[i]=p[i-1]*base%mod; }
for(int i=1;i<=n;i++) pre[i]++,pre[get(i)+1]--; for(int i=1;i<=n;i++) pre[i]+=pre[i-1],printf("%d\n",pre[i]); return 0; }
|