Submission #10376319

---

Source Code Expand

using System;
using System.Linq;
using System.Collections.Generic;

namespace Contest
{
    partial class Program
    {
        static void Main(string[] args)
        {
            ABC104D();
        }

        static void ABC104D()
        {
            var str = ReadStr();
            var N = str.Length;
            var dp = new long[N + 1, 4];
            dp[0, 0] = 1;
            for(int i = 0; i < N; ++i)
            {
                var c = str[i];
                dp[i + 1, 0] = (dp[i, 0] * (c == '?' ? 3 : 1)) % Util.P;
                dp[i + 1, 1] = (dp[i, 1] * (c == '?' ? 3 : 1) + (c == '?' || c == 'A' ? 1 : 0) * dp[i, 0]) % Util.P;
                dp[i + 1, 2] = (dp[i, 2] * (c == '?' ? 3 : 1) + (c == '?' || c == 'B' ? 1 : 0) * dp[i, 1]) % Util.P;
                dp[i + 1, 3] = (dp[i, 3] * (c == '?' ? 3 : 1) + (c == '?' || c == 'C' ? 1 : 0) * dp[i, 2]) % Util.P;
            }
            Console.WriteLine(dp[N, 3]);
        }

        class Util
        {
            public static readonly long P = 1000000007;

            public static long Sum(long[] array)
            {
                return Sum(array, array.Length);
            }
            public static long Sum(long[] array, int n)
            {
                long total = 0;
                for(int i = 0; i < n; ++i)
                {
                    total += array[i];
                }
                return total;
            }
            public static long Count(long[] array, long x)
            {
                return Count(array, x, array.Length);
            }
            public static long Count(long[] array, long x, int n)
            {
                long total = 0;
                for (int i = 0; i < n; ++i)
                {
                    total += (array[i] == x ? 1 : 0);
                }
                return total;
            }

            public static long GCD(long a, long b)
            {
                while (b > 0)
                {
                    var c = a % b;
                    a = b;
                    b = c;
                }
                return a;
            }
            public static Dictionary<long,int> Factorize(long x)
            {
                var dict = new Dictionary<long, int>();
                long minp = 2;
                while (x > 1)
                {
                    bool ok = false;
                    for(long p = minp; p * p <= x; ++p)
                    {
                        if (x % p == 0)
                        {
                            if (!dict.ContainsKey(p))
                            {
                                dict.Add(p, 0);
                            }
                            dict[p]++;
                            minp = p;
                            x /= p;
                            ok = true;
                            break;
                        }
                    }
                    if (!ok)
                    {
                        if (!dict.ContainsKey(x)) { dict.Add(x, 0); }
                        dict[x]++;
                        break;
                    }
                }
                return dict;
            }
            public static long Inverse(long a, long p)
            {
                long b = p, c = 1, d = 0, e = 0, f = 0;
                while (b != 0)
                {
                    e = a / b;
                    f = b; b = a - e * b; a = f;
                    f = d; d = c - e * d; c = f;
                }
                c %= p;
                return c + (c < 0 ? p : 0);
            }
            public static long[] Facts(int n, long p)
            {
                var facts = new long[n + 1];
                facts[0] = 1;
                for (int i = 1; i <= n; ++i)
                {
                    facts[i] = (i * facts[i - 1]) % p;
                }
                return facts;
            }
            public static Func<int,int,long> Combin(int n, long P)
            {
                var fact = Facts(n, P);
                var inv = fact.Select(x => Inverse(x, P)).ToArray();
                return (N, M) =>
                {
                    if (N < 0 || N < M || M < 0) { return 0; }
                    return (((fact[N] * inv[M]) % P) * inv[N - M]) % P;
                };
            }

            /// <summary>
            /// Calc Combin(n,m) where n is large and m<=mMax
            /// </summary>
            public static Func<int,int,long> CombinLarge(int mMax, long p)
            {
                var inv = Enumerable.Range(0, mMax + 1).Select(x => Util.Inverse(x, Util.P)).ToArray();
                return (n, m) =>
                {
                    long mult = 1;
                    for (int i = 1; i <= m; ++i)
                    {
                        mult = (((mult * (n + 1 - i)) % Util.P) * inv[i]) % Util.P;
                    }
                    return mult;
                };
            }

            /// <summary>
            /// Calc 2^n mod p
            /// </summary>
            public static long Power2(long n, long p)
            {
                long res = 1;
                long mult = 2;
                for(int i = 0; i < 40; ++i)
                {
                    if ((n & ((long)1 << i)) > 0)
                    {
                        res = (res * mult) % p;
                    }
                    mult = (mult * mult) % p;
                }
                return res;
            }
        }
        class Geometric
        {
            /// <summary>
            /// 2点間の距離
            /// </summary>
            public static double Distance(Tuple<double, double> s, Tuple<double, double> t)
            {
                var diff1 = s.Item1 - t.Item1;
                var diff2 = s.Item2 - t.Item2;
                return Math.Sqrt(diff1 * diff1 + diff2 * diff2);
            }
            /// <summary>
            /// 2点の中点
            /// </summary>
            public static Tuple<double,double> Center(Tuple<double, double> s, Tuple<double, double> t)
            {
                return new Tuple<double, double>((s.Item1 + t.Item1) / 2, (s.Item2 + t.Item2) / 2);
            }

            /// <summary>
            /// 垂直二等分線 ax+by+c=0の係数(a,b,c)を出力
            /// </summary>
            public static Tuple<double,double,double> Bisector(Tuple<double, double> s, Tuple<double, double> t)
            {
                var a = t.Item1 - s.Item1;
                var b = t.Item2 - s.Item2;
                var c = -a * (s.Item1 + t.Item1) / 2 - b * (s.Item2 + t.Item2) / 2;
                return new Tuple<double, double, double>(a, b, c);
            }

            /// <summary>
            /// 2本の直線が平行か(絶対誤差Epsilon)
            /// </summary>
            public static bool IsParallel(Tuple<double, double, double> line1, Tuple<double, double, double> line2, double epsilon)
            {
                return Math.Abs(line1.Item1 * line2.Item2 - line1.Item2 * line2.Item1) < epsilon;
            }

            /// <summary>
            /// 2本の直線の交点(平行でないことを仮定)
            /// </summary>
            public static Tuple<double,double> Intersection(Tuple<double, double, double> line1, Tuple<double, double, double> line2)
            {
                var div = line1.Item1 * line2.Item2 - line1.Item2 * line2.Item1;
                var x = (line1.Item2 * line2.Item3 - line1.Item3 * line2.Item2) / div;
                var y = (line1.Item3 * line2.Item1 - line1.Item1 * line2.Item3) / div;
                return new Tuple<double, double>(x, y);
            }
        }

        static string ReadStr()
        {
            return Console.ReadLine();
        }
        static string[] ReadStrN()
        {
            return Console.ReadLine().Split(' ');
        }
        static int ReadInt()
        {
            return Convert.ToInt32(Console.ReadLine());
        }
        static int[] ReadIntN()
        {
            return Console.ReadLine().Split(' ').Select(s => Convert.ToInt32(s)).ToArray();
        }
        static long ReadLong()
        {
            return Convert.ToInt64(Console.ReadLine());
        }
        static long[] ReadLongN()
        {
            return Console.ReadLine().Split(' ').Select(s => Convert.ToInt64(s)).ToArray();
        }
        static Tuple<string, string>[] ReadTupleStr(int n)
        {
            List<Tuple<string, string>> list = new List<Tuple<string, string>>();
            for (int i = 0; i < n; ++i)
            {
                var ab = ReadStrN();
                list.Add(new Tuple<string, string>(ab[0], ab[1]));
            }
            return list.ToArray();
        }
        static Tuple<long, long>[] ReadTupleLong(int n)
        {
            List<Tuple<long, long>> list = new List<Tuple<long, long>>();
            for (int i = 0; i < n; ++i)
            {
                var ab = ReadLongN();
                list.Add(new Tuple<long, long>(ab[0], ab[1]));
            }
            return list.ToArray();
        }
        static Tuple<double, double>[] ReadTupleDouble(int n)
        {
            List<Tuple<double, double>> list = new List<Tuple<double, double>>();
            for (int i = 0; i < n; ++i)
            {
                var ab = ReadLongN();
                list.Add(new Tuple<double, double>(ab[0], ab[1]));
            }
            return list.ToArray();
        }
    }
}

Submission Info

Judge Result