并不是很能蚌。同时让我意识到了我打 D2 就只有保龄的份。劈里啪啦彩笔。
我多项式确实很菜，而且是有经过实际观察得到的依据的。
热知识：今天是霍金逝世 5 周年。
另一个热知识：今天是马克思逝世 140 周年。
巴萨
csp 的时候还在嘲讽巴萨怎么连十六强都进不去了呢。现在被巴萨薄纱了。
本人确实不了解足球，csp 住宾馆看欧冠是第一次看足球比赛。
原题 CF1510J。
先考虑给定一个想法怎么求出必须染的块。显然就是贪心填最左，贪心填最右，重合的就是答案。
考虑怎么倒过来。假设全放左的时候最后边剩下 \(k\) 个没染，那么必须染的就是对于所有 \(p_i\) 在最左边放时去掉最左边 \(k\) 个。
那么我们枚举这个 \(k\)，每个染色的连续段前面加上 \(k\) 个，如果不是第一段要前后空两格。那么对于剩下的一段连续的空白段，我们需要找到方法填满它们而且让它们都可以挪动，即不是必须涂色。那么我们可以隔着填 \(1\) ，最后看情况填一个 \(2\) 来解决。同时 \(k\ge 4\) 的时候可以直接中间填数变成更小的情况，因此只需要枚举 \(k=0-3\)。
细节比较吊诡。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int n,cnt,l[5000010],r[5000010],pos[5000010];
char s[5000010];
void solve(int x){
pos[0]=0;
for(int i=1;i<=cnt;i++){
int ret=l[i]-r[i-1]-x-2;
if(ret<0||ret==1)return;
if(ret>0){
if(!x)return;
for(int j=1;j<=(ret>>1);j++)pos[++pos[0]]=1;
if(ret&1){
if(x>1)pos[pos[0]]=2;
else return;
}
}
pos[++pos[0]]=r[i]-l[i]+1+x;
}
int ret=n-r[cnt]-x;
if(ret<0||ret==1)return;
if(ret>0){
if(!x)return;
for(int j=1;j<=(ret>>1);j++)pos[++pos[0]]=1;
if(ret&1){
if(x>1)pos[pos[0]]=2;
else return;
}
}
int len=0;puts("Yes");
for(int i=1;i<=pos[0];i++){
for(int j=1;j<=pos[i];j++)putchar('B');
len+=pos[i];if(len<n)putchar('R'),len++;
}
for(int i=len+1;i<=n;i++)putchar('R');
exit(0);
}
int main(){
scanf("%d%s",&n,s+1);int mn=3;
r[0]=-1;
for(int i=1;i<=n;i++){
if(s[i]=='1'){
l[++cnt]=i;r[cnt]=i;
while(s[r[cnt]+1]=='1')r[cnt]++;
i=r[cnt]+1;mn=min(mn,l[cnt]-r[cnt-1]);
}
}
mn=min(mn,n-r[cnt]);
for(int i=0;i<=mn;i++)solve(i);
puts("No");
return 0;
}
拜仁
csp 考完回来住宾馆看的最后一场是拜仁和谁来着。
原题 CF794G。
CF *3400，感觉难度全都在前面发现性质。数学题卡住我好像大多数在数学前面的性质而不是数学部分。
A 老师告诉我少做推式子题多做思维题，拜谢。于是应当把板刷 AGC 拾起来。同时也可以缓解一下不知道颓什么的感觉。
这个题的性质：\(s,t\) 一定可以拆成同一个循环节不断重复的形式。只有这样才能保证在任意地方都可以匹配。
知道这个结论其实就不难了。先考虑没有 \(?\) 的情况。
首先特判 \(a=b\) 的答案是
\[\left(\sum_{i=1}^n2^i\right)^2 \]然后设 \(a\) 中 F 比 \(b\) 多 \(p\) 个，\(b\) 中 D 比 \(a\) 多 \(q\) 个。那么有两种情况：（以下记作 \(f(p,q)\)）
- \(p=q=0\)，即无所谓。此时答案为\[\sum_{i=1}^n\sum_{j=1}^n2^{\gcd(i,j)} \]憨憨式子，这个就是\[\sum_{d=1}^n2^d\sum_{e=1}^{\lfloor\frac nd\rfloor}\mu(e)\left\lfloor\frac n{de}\right\rfloor^2 \]
- \(p,q\neq 0\)。首先显然除以 \(\gcd(p,q)\) 后答案没有影响。然后容易发现此时答案就是\[\sum_{i=1}^{\frac n{\max(p,q)}}2^i \]
然后考虑问号的影响。首先判两个串相等时同位置出现问号的贡献，此时可以有两种情况。设 \(cnt\) 个位置满足两个都是问号，则会有 \(2^{cnt}(\left(\sum_{i=1}^n2^i\right)^2-f(0,0))\) 的贡献。然后设 $a 有 \(x\) 个问号，\(b\) 有 \(y\) 个问号，枚举问号是 F 的个数：
\[\begin{aligned} &\sum_{i=0}^x\sum_{j=0}^yf(p+i-j,q+y-x+i-j)\binom xi\binom yj\\ =&\sum_{i=-y}^xf(p+i,q+y-x+i)\sum_j\binom x{i+j}\binom y{y-j}\\ =\sum_{i=-y}^xf(p+i,q+y-x+i)\binom{x+y}{i+y} \end{aligned} \]结束。
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#define int long long
using namespace std;
const int mod=1000000007;
int n,p,q,x,y,wsnd,ans;
char a[2000010],b[2000010];
int prm[2000010],miu[2000010],pw[2000010];
bool v[2000010];
int gcd(int a,int b){
return b?gcd(b,a%b):a;
}
int calc(int n){
int ans=0;
for(int l=1,r;l<=n;l=r+1){
r=n/(n/l);
ans=(ans+1ll*(miu[r]-miu[l-1]+mod)%mod*(n/l)%mod*(n/l))%mod;
}
return ans;
}
void get(int n){
miu[1]=1;pw[1]=2;
for(int i=2;i<=n;i++){
pw[i]=(pw[i-1]<<1)%mod;
if(!v[i])prm[++prm[0]]=i,miu[i]=-1;
for(int j=1;j<=prm[0]&&i*prm[j]<=n;j++){
v[i*prm[j]]=true;
if(i%prm[j]==0)break;
miu[i*prm[j]]=-miu[i];
}
}
for(int i=1;i<=n;i++)pw[i]=(pw[i]+pw[i-1])%mod,miu[i]=(miu[i]+miu[i-1])%mod;
for(int l=1,r;l<=n;l=r+1){
r=n/(n/l);
wsnd=(wsnd+1ll*(pw[r]-pw[l-1]+mod)%mod*calc(n/l))%mod;
}
}
int f(int p,int q){
if(!p&&!q)return wsnd;
if(p<=0&&q<=0)p=-p,q=-q;
if(p<=0||q<=0)return 0;
int d=gcd(p,q);p/=d;q/=d;
return pw[n/max(p,q)];
}
int jc[4000010],inv[4000010];
int C(int n,int m){
return 1ll*jc[n]*inv[m]%mod*inv[n-m]%mod;
}
void solve(int i,int a,int b,int x,int y){
a+=i;b+=i;
if(!a&&!b){
ans=(ans+1ll*wsnd*C(x+y,i+y))%mod;return;
}
if(1ll*a*b<=0)return;
int c=gcd(a,b);a/=c;b/=c;
ans=(ans+1ll*C(x+y,i+y)*pw[n/max(a,b)])%mod;
}
signed main(){
scanf("%s%s%lld",a+1,b+1,&n);jc[0]=inv[0]=inv[1]=1;
int lena=strlen(a+1),lenb=strlen(b+1);
for(int i=2;i<=lena+lenb;i++)inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
for(int i=1;i<=lena+lenb;i++)jc[i]=1ll*jc[i-1]*i%mod,inv[i]=1ll*inv[i-1]*inv[i]%mod;
get(n);
if(lena==lenb){
bool jud=true;
for(int i=1;i<=lena;i++){
if(a[i]!=b[i]||a[i]=='?'){
jud=false;break;
}
}
if(jud){printf("%lld\n",1ll*pw[n]*pw[n]%mod);
return 0;}
}
for(int i=1;i<=lena;i++){
if(a[i]=='F')p++;
if(a[i]=='D')q--;
if(a[i]=='?')x++;
}
for(int i=1;i<=lenb;i++){
if(b[i]=='F')p--;
if(b[i]=='D')q++;
if(b[i]=='?')y++;
}
for(int i=-y;i<=x;i++)solve(i,p,q+y-x,x,y);
if(lena==lenb){
int ret=1;
for(int i=1;i<=lena;i++){
if(a[i]=='?'&&b[i]=='?'){ret=(ret<<1)%mod;continue;}
if(a[i]=='?'||b[i]=='?'||a[i]==b[i])continue;
ret=0;break;
}
ans=(ans+1ll*(1ll*pw[n]*pw[n]%mod-wsnd+mod)%mod*ret)%mod;
}
printf("%lld\n",ans);
return 0;
}
大巴黎
没看过大巴黎比赛。
原题 P6818。大佬们看见计算几何就跑路了。感觉不是很计算几何啊。
摆了。写不动。有空再补。
标签：2000010,return,省选,sum,pos,int,联测,武汉,include From： https://www.cnblogs.com/gtm1514/p/17216166.html