首先有一个想法，翻转串后直接卷积看有没有0匹配上1。但这是必要而不充分的因为在原串和翻转串中?不能同时取两个值。

　　先有一些结论：

　　如果s中长度为len的前缀是border，那么其存在|s|-len的循环节（最后一段不一定完整）。

　　如果已知len不是s的循环节，那么显然len的因子也不是s的循环节。

　　如果位置差为len的两个位置无法匹配，那么len不是s的循环节。

　　于是可得：如果位置差为len的两个位置无法匹配，那么长度为|s|-(len的因子)的前缀不是border。

　　可以发现其实问号出现冲突的原因就在于此，即某两个01的位置差为len，而问号在两者之间且与其中一个的位置差是len的因子。

　　那么这是充分的，即只要不会被筛掉则一定是border。

　　那么我们卷完后只要枚举长度去看他的倍数有没有被筛掉就可以了。由调和级数，复杂度O(nlogn)。

　　LOJ过了，BZOJ上不出意外地T掉了。

 

#include
     
       #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;int read(){ int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') { if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f;}#define N 1050000#define P 998244353 #define inv3 332748118int n,t,s[N],a[N],b[N],f[N],r[N];long long ans;int ksm(int a,int k){ if (k==0) return 1; int tmp=ksm(a,k>>1); if (k&1) return 1ll*tmp*tmp%P*a%P; else return 1ll*tmp*tmp%P;}void DFT(int n,int *a,int p){ for (int i=0;i
           
            >1);k++,w=1ll*w*wn%P) { int x=a[k],y=1ll*w*a[k+(i>>1)]%P; a[k]=(x+y)%P,a[k+(i>>1)]=(x-y+P)%P; } } }}void mul(int n){ DFT(n,a,3),DFT(n,b,3); for (int i=0;i
            
             >1]>>1)|(i&1)*(t>>1); memset(a,0,sizeof(a));memset(b,0,sizeof(b)); for (int i=0;i
             
              0); memset(a,0,sizeof(a));memset(b,0,sizeof(b)); for (int i=0;i
              
               0); for (int i=1;i