提出 #41973897

---

ソースコード 拡げる

import java.io.*;
import java.util.*;
import static java.lang.Math.*;
import static java.util.Map.*;
import static java.util.Arrays.*;
import static java.util.Collections.*;
import static java.lang.System.*;
public class Main
{
    public void tq() throws Exception
    {
        int n=i();
        char ar[]=s().toCharArray();
        long f[]=new long[n+1];
        for(int x=1;x<n;x++)
        {
            if(n%x==0)
            {
                long t=1l;
                for(int y=0;y<x;y++)
                {
                    int k=0;
                    int b=0;
                    for(int z=y;z<n;z+=x)
                    {
                        if(ar[z]=='.')k++;
                        else b++;
                    }
                    if(k==0)t=(t*2)%mod;
                }
                f[x]=t;
            }
        }
        long c=0l;
        for(int x=1;x<n;x++)
        {
            if(n%x==0)
            {
                for(int y=x*2;y<n;y+=x)
                {
                    f[y]-=f[x];
                    f[y]+=mod;
                    f[y]%=mod;
                }
                c=(c+f[x])%mod;
            }
        }
        pl(c);
    }
    StringBuilder sb;//=new StringBuilder(2000000);
    long mod=998244353l;
    int max=Integer.MAX_VALUE,min=Integer.MIN_VALUE;long maxl=Long.MAX_VALUE,minl=Long.MIN_VALUE;
    String nl="No",nu="NO",yl="Yes",yu="YES",ssp=" ";
    char ne='\n',sp=' ';
    BufferedReader bq = new BufferedReader(new InputStreamReader(in));
    StringTokenizer st=new StringTokenizer(bq.readLine());
    public Main() throws Exception{}
    public static void main(String[] a)throws Exception{new Main().tq();}
    int di[][]={{-1,0},{1,0},{0,-1},{0,1}};
    int de[][]={{-1,0},{1,0},{0,-1},{0,1},{-1,-1},{1,1},{-1,1},{1,-1}};
    void f1(int ar[],int v){fill(ar,v);}
    void f2(int ar[][],int v){for(int a[]:ar)fill(a,v);}
    void f3(int ar[][][],int v){for(int a[][]:ar)for(int b[]:a)fill(b,v);}
    void f1(long ar[],long v){fill(ar,v);}
    void f2(long ar[][],long v){for(long a[]:ar)fill(a,v);}
    void f3(long ar[][][],long v){for(long a[][]:ar)for(long b[]:a)fill(b,v);}
    void f(){out.flush();}
    int p(int i,int p[]){return p[i]<0?i:(p[i]=p(p[i],p));}
    boolean c(int x,int y,int n,int m){return x>=0&&x<n&&y>=0&&y<m;}
    int[] so(int ar[])
    {
        Integer r[] = new Integer[ar.length];for (int x = 0; x < ar.length; x++) r[x] = ar[x];sort(r);
        for (int x = 0; x < ar.length; x++) ar[x] = r[x];return ar;
    }
    long[] so(long ar[])
    {
        Long r[] = new Long[ar.length];for (int x = 0; x < ar.length; x++) r[x] = ar[x];sort(r);
        for (int x = 0; x < ar.length; x++) ar[x] = r[x];return ar;
    }
    char[] so(char ar[])
    {
        Character r[] = new Character[ar.length];for (int x = 0; x < ar.length; x++) r[x] = ar[x];sort(r);
        for (int x = 0; x < ar.length; x++) ar[x] = r[x];return ar;
    }
    int m(int i,int j){return i+(j-i)/2;};
    long m(long i,long j){return i+(j-i)/2;};
    int l(int v) {return 31 - Integer.numberOfLeadingZeros(v);}
    long l(long v) {return 63 - Long.numberOfLeadingZeros(v);}
    int sq(int a)
    {
        int i=1;
        int j=44721;
        int b=0;
        while(i<=j)
        {
            int m=(i+j)/2;
            int mm=m*m;
            if(mm<=a)
            {
                b=m;
                i=m+1;
            }
            else j=m-1;
        }
        return b;
    }
    int sq(long a)
    {
        long i=1l;
        long j=1000000000l;
        int b=0;
        while(i<=j)
        {
            long m=(i+j)/2;
            long mm=m*m;
            if(mm<=a)
            {
                b=(int)m;
                i=m+1;
            }
            else j=m-1;
        }
        return b;
    }
    int gcd(int a, int b) {while (b > 0) {int c = a % b;a = b;b = c;}return a;}
    long gcd(long a, long b) {while (b > 0l) {long c = a % b;a = b;b = c;}return a;}
    boolean p(String s, int i, int j) {while (i < j) if (s.charAt(i++) != s.charAt(j--)) return false;return true;}
    boolean[] si(int n)
    {
        boolean bo[] = new boolean[n + 1];bo[0] = bo[1] = true;for (int x = 4; x <= n; x += 2) bo[x] = true;
        for (int x = 3; x * x <= n; x += 2) {if (!bo[x]) {int vv = (x << 1);for (int y = x * x; y <= n; y += vv) bo[y] = true;}}
        return bo;
    }
    long mul(long a, long b, long m) {long r = 1l;a %= m;while (b > 0) {if ((b & 1) == 1) r = (r * a) % m;b >>= 1;a = (a * a) % m;}return r;}
    int i() throws IOException {return Integer.parseInt(st.hasMoreTokens()?st.nextToken():(st=new StringTokenizer(bq.readLine())).nextToken());}
    long l() throws IOException {return Long.parseLong(st.hasMoreTokens()?st.nextToken():(st=new StringTokenizer(bq.readLine())).nextToken());}
    char c() throws IOException {return (st.hasMoreTokens()?st.nextToken().charAt(0):(st=new StringTokenizer(bq.readLine())).nextToken().charAt(0));}
    String s() throws IOException {return st.hasMoreTokens()?st.nextToken():new StringTokenizer(bq.readLine()).nextToken();}
    double d() throws IOException {return Double.parseDouble(st.hasMoreTokens()?st.nextToken():(st=new StringTokenizer(bq.readLine())).nextToken());}
    int[] ari(int n) throws IOException
    {
        int ar[] = new int[n];if(!st.hasMoreTokens())st = new StringTokenizer(bq.readLine());
        for (int x = 0; x < n; x++) ar[x] = Integer.parseInt(st.nextToken());return ar;
    }
    long[] arl(int n) throws IOException
    {
        long ar[] = new long[n];if(!st.hasMoreTokens())st = new StringTokenizer(bq.readLine());
        for (int x = 0; x < n; x++) ar[x] = Long.parseLong(st.nextToken());return ar;
    }
    char[] arc(int n) throws IOException
    {
        char ar[] = new char[n];if(!st.hasMoreTokens())st = new StringTokenizer(bq.readLine());
        for (int x = 0; x < n; x++) ar[x] = st.nextToken().charAt(0);return ar;
    }
    double[] ard(int n) throws IOException
    {
        double ar[] = new double[n];if(!st.hasMoreTokens())st = new StringTokenizer(bq.readLine());
        for (int x = 0; x < n; x++) ar[x] = Double.parseDouble(st.nextToken());return ar;
    }
    String[] ars(int n) throws IOException
    {
        String ar[] = new String[n];if(!st.hasMoreTokens())st = new StringTokenizer(bq.readLine());
        for (int x = 0; x < n; x++) ar[x] = st.nextToken();return ar;
    }
    int[][] ari(int n, int m) throws IOException {int ar[][] = new int[n][];for (int x = 0; x < n; x++)ar[x]=ari(m);return ar;}
    long[][] arl(int n, int m) throws IOException {long ar[][] = new long[n][];for (int x = 0; x < n; x++)ar[x]=arl(m);return ar;}
    char[][] arc(int n,int m) throws IOException {char ar[][] = new char[n][];for (int x=0;x < n; x++) ar[x]=bq.readLine().toCharArray();return ar;}
    char[][] arcs(int n,int m) throws IOException {char ar[][] = new char[n][];for (int x=0;x < n; x++) ar[x]=arc(m);return ar;}
    double[][] ard(int n, int m) throws IOException {double ar[][] = new double[n][];for (int x = 0; x < n; x++)ar[x]=ard(m);return ar;}
    void s(String s) {sb.append(s);}
    void s(int s) {sb.append(s);}
    void s(long s) {sb.append(s);}
    void s(char s) {sb.append(s);}
    void s(double s) {sb.append(s);}
    void ss() {sb.append(sp);}
    void sl(String s) {sb.append(s).append(ne);}
    void sl(int s) {sb.append(s).append(ne);}
    void sl(long s) {sb.append(s).append(ne);}
    void sl(char s) {sb.append(s).append(ne);}
    void sl(double s) {sb.append(s).append(ne);}
    void sl() {sb.append(ne);}
    void sl(Object... ar) {for (Object e : ar)sb.append(e).append(sp);sb.append(ne);}
    void s(int a[]) {for (int e : a)sb.append(e).append(sp);sb.append(ne);}
    void s(long a[]) {for (long e : a)sb.append(e).append(sp);sb.append(ne);}
    void s(double a[]) {for (double e : a)sb.append(e).append(sp);sb.append(ne);}
    void s(char a[]) {for (char e : a)sb.append(e).append(sp);sb.append(ne);}
    void s(String a[]) {for (String e : a)sb.append(e).append(sp);sb.append(ne);}
    void s(int ar[][]) {for (int a[] : ar) s(a);}
    void s(long ar[][]) {for (long a[] : ar) s(a);}
    void s(double ar[][]) {for (double a[] : ar) s(a);}
    void ss(char ar[][]) {for (char a[] : ar) s(a);}
    void s(char ar[][]) {for (char a[] : ar) sb.append(new String(a)).append(ne);}
    void p(Object p) {out.print(p);}
    void pl(Object p) {out.println(p);}
    void pl() {out.println();}
    void p(int ar[]) {for (int a : ar)p(a+ssp);pl();}
    void p(long ar[]) {for (long a : ar)p(a+ssp);pl();}
    void p(double ar[]) {for (double a : ar)p(a+ssp);pl();}
    void p(char ar[]) {for (char a : ar)p(a+ssp);pl();}
    void p(String ar[]) {for (String a : ar)p(a+ssp);pl();}
    void p(int ar[][]) {for (int a[] : ar) p(a);}
    void p(long ar[][]) {for (long a[] : ar) p(a);}
    void p(double ar[][]) {for (double a[] : ar) p(a);}
    void ps(char ar[][]) {for (char a[] : ar) p(a);}
    void p(char ar[][]) {for (char a[] : ar) pl(new String(a));}
    void pl(Object... ar) {for (Object e : ar) p(e + ssp);pl();}
}

提出情報

ジャッジ結果