一、题目
题目描述
一个字符串 (T) 是由一个包含 (0,1,?) 的字符串 (S) 循环连接 (k) 次获得的。
字符串 (T) 中的每个 (?) 都可以换成 (0) 或 (1)，设得到的串是 (T')，求：
[sum F(T')
]
其中 (F(T')) 定义为把字符串通过区间异或 (1) 的方式变成相同的最小操作数。
(1leq |S|leq 10^5,1leq kleq 10^9)
解法
别被题目吓到了，其实是个水题。
首先想一想怎么才能做一个没有问号的序列 (S)，可以把 (S) 差分，即得到数组 (s_1oplus s_2....s_{n}oplus s_1)，不难发现这样做一定会有偶数个 (1)，而且每次通过区间操作可以消掉一对 (1)，并且 (S) 复制 (k) 次的差分数组就是 (S) 的差分数组复制 (k) 次获得的，不难写出答案：
[k imes frac{sum_{i=1}^n[s_i=s_{i\%n+1}]}{2}
]
然后再把问号考虑进来，可以先求出期望再乘以总方案数，只考虑 ([s_i=s_{i\%n+1}]) 的期望是好算的：
- 如果 (s_i=?or s_{i\% n+1}=?)，不难发现期望是 (50\%)
- 否则期望是 ([s_i=s_{i\%n+1}])
但是注意 (n=k=1) 并且字符是 (?) 的时候会出问题（期望算错了），需要特判。
#include <cstdio>
#include <cstring>
const int M = 100005;
const int MOD = 1e9+7;
const int i2 = (MOD+1)/2;
#define int long long
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int n,k,ans,t=1;char s[M];
int qkpow(int a,int b)
{
int r=1;
while(b>0)
{
if(b&1) r=r*a%MOD;
a=a*a%MOD;
b>>=1;
}
return r;
}
signed main()
{
scanf("%s",s+1);k=read();
n=strlen(s+1);
if(n*k==1) {puts("0");return 0;}
for(int i=1;i<=n;i++)
{
int j=i%n+1;
if(s[i]=='?') t=t*2%MOD;
if(s[i]=='?' || s[j]=='?') ans=(ans+i2)%MOD;
else if(s[i]!=s[j]) ans++;
}
ans=ans*k%MOD*i2%MOD*qkpow(t,k)%MOD;
printf("%lld
",ans);
}