能不能正赛场上不要脑瘫啊。
简单题做不出来直接崩了/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;
}
|