結果
問題 |
No.1171 Runs in Subsequences
|
ユーザー |
|
提出日時 | 2025-06-07 18:26:21 |
言語 | C# (.NET 8.0.404) |
結果 |
WA
|
実行時間 | - |
コード長 | 7,275 bytes |
コンパイル時間 | 15,508 ms |
コンパイル使用メモリ | 169,064 KB |
実行使用メモリ | 168,604 KB |
最終ジャッジ日時 | 2025-06-07 18:26:42 |
合計ジャッジ時間 | 14,906 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 6 WA * 5 TLE * 1 -- * 6 |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (86 ミリ秒)。 main -> /home/judge/data/code/bin/Release/net8.0/main.dll main -> /home/judge/data/code/bin/Release/net8.0/publish/
ソースコード
using System; using static System.Console; using System.Linq; using System.Collections.Generic; class Program { static int NN => int.Parse(ReadLine()); static int[] NList => ReadLine().Split().Select(int.Parse).ToArray(); public static void Main() { Solve(); } static void Solve() { var s = ReadLine(); var n = s.Length; var mod = 1_000_000_007; var cc = new ConvolutionCalculator(mod); var counts = new long[n]; for (var i = 1; i < n; ++i) counts[i] = n - i; for (var a = 'a'; a <= 'z'; ++a) { var list1 = new int[n]; for (var i = 0; i < n; ++i) { if (s[i] == a) list1[i] = 1; } var list2 = list1.ToArray(); Array.Reverse(list2); var c = cc.Calc(list1, list2); for (var i = 1; i < n; ++i) counts[i] -= c[i + n - 1]; } var mul = 1L; var ans = 0L; for (var i = n - 1; i >= 0; --i) { ++counts[i]; ans = (ans + counts[i] * mul % mod) % mod; mul = mul * 2 % mod; } WriteLine(ans); } class ConvolutionCalculator { int keyNum; public ConvolutionCalculator(int keyNum) { this.keyNum = keyNum; } public int[] Calc(int[] a, int[] b) { var n = a.Length; var m = b.Length; if (n == 0 || m == 0) { return new int[0]; } if (Math.Min(n, m) <= 60) { return ShortComvolution(a, b); } var z = 1 << CeilPow(n + m - 1); var za = new int[z]; var zb = new int[z]; Array.Copy(a, za, a.Length); Array.Copy(b, zb, b.Length); InitButterfly(); Butterfly(za); Butterfly(zb); for (var i = 0; i < z; ++i) { za[i] = (int)((long)za[i] * zb[i] % keyNum); } ButterflyInv(za); var iz = PowMod(z, keyNum - 2, keyNum); var ans = new int[n + m - 1]; for (var i = 0; i < ans.Length; ++i) { ans[i] = (int)((long)za[i] * iz % keyNum); } return ans; } int[] ShortComvolution(int[] a, int[] b) { if (a.Length < b.Length) { var tmp = a; a = b; b = tmp; } var ans = new int[a.Length + b.Length - 1]; for (var i = 0; i < a.Length; ++i) { for (var j = 0; j < b.Length; ++j) { ans[i + j] = (int)((ans[i + j] + (long)a[i] * b[j] % keyNum) % keyNum); } } return ans; } int[] sume = new int[30]; int[] sumie = new int[30]; void InitButterfly() { var g = PrimitiveRoot(keyNum); var es = new int[30]; var ies = new int[30]; var cnt2 = BSF(keyNum - 1); var e = PowMod(g, keyNum - 1 >> cnt2, keyNum); var ie = PowMod(e, keyNum - 2, keyNum); for (var i = cnt2; i >= 2; --i) { es[i - 2] = e; ies[i - 2] = ie; e = (int)((long)e * e % keyNum); ie = (int)((long)ie * ie % keyNum); } var now = 1L; var inow = 1L; for (var i = 0; i < cnt2 - 2; ++i) { sume[i] = (int)(es[i] * now % keyNum); now = now * ies[i] % keyNum; sumie[i] = (int)(ies[i] * inow % keyNum); inow = inow * es[i] % keyNum; } } void Butterfly(int[] a) { var h = CeilPow(a.Length); for (var ph = 1; ph <= h; ++ph) { var w = 1 << (ph - 1); var p = 1 << (h - ph); var now = 1L; for (var s = 0; s < w; ++s) { var offset = s << (h - ph + 1); for (var i = 0; i < p; ++i) { var l = a[i + offset]; var r = (int)(a[i + offset + p] * now % keyNum); a[i + offset] = (l + r) % keyNum; a[i + offset + p] = (int)((long)keyNum + l - r) % keyNum; } now = now * sume[BSF(~(uint)s)] % keyNum; } } } void ButterflyInv(int[] a) { var h = CeilPow(a.Length); for (var ph = h; ph >= 1; --ph) { var w = 1 << (ph - 1); var p = 1 << (h - ph); var inow = 1L; for (var s = 0; s < w; ++s) { var offset = s << (h - ph + 1); for (var i = 0; i < p; ++i) { var l = a[i + offset]; var r = a[i + offset + p]; a[i + offset] = (l + r) % keyNum; a[i + offset + p] = (int)(((long)keyNum + l - r) * inow % keyNum); } inow = inow * sumie[BSF(~(uint)s)] % keyNum; } } } static int PowMod(int n, int p, int keyNum) { long _n = n % keyNum; var _p = p; var result = 1L; if ((_p & 1) == 1) { result *= _n; } while (_p > 0) { _n = _n * _n % keyNum; _p >>= 1; if ((_p & 1) == 1) { result = (result * _n) % keyNum; } } return (int)result; } static int PrimitiveRoot(int m) { if (m == 2) return 1; if (m == 167772161) return 3; if (m == 469762049) return 3; if (m == 754974721) return 11; if (m == 998244353) return 3; if (m == 1000000007) return 5; throw new Exception("undefined primitive root"); } static int CeilPow(int n) { var x = 0; while ((1U << x) < (uint)n) x++; return x; } static int BSF(int n) { if (n == 0) return 0; var count = 0; while ((n & 1) == 0) { ++count; n >>= 1; } return count; } static int BSF(uint n) { if (n == 0) return 0; var count = 0; while ((n & 1) == 0) { ++count; n >>= 1; } return count; } } }