結果
問題 | No.1325 Subsequence Score |
ユーザー |
![]() |
提出日時 | 2020-12-24 23:44:00 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 849 ms / 2,000 ms |
コード長 | 11,219 bytes |
コンパイル時間 | 3,183 ms |
コンパイル使用メモリ | 118,484 KB |
実行使用メモリ | 25,600 KB |
最終ジャッジ日時 | 2024-09-21 17:08:22 |
合計ジャッジ時間 | 12,963 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System;using System.Collections;using System.Collections.Generic;using System.Diagnostics;using System.Globalization;using System.IO;using System.Text;using System.Linq;using E = System.Linq.Enumerable;using System.Threading;internal partial class Solver {public void Run() {var n = ni();var a = ni(n);// 1*xC0 + 2*xC1 + 3*xC2 ... n*xCn-1= 2^(x-1)*xvar mod = ModInt.SetMod998244353();var b = new Binomial(100000, mod);ModInt ans = 0;for (int i = 0; i < n; i++) {int k = n - (i + 1);ans += ModInt.Pow(2, k) * ModInt.Pow(2, i - 1) * (i + 2) * a[i];}cout.WriteLine(ans);}}public class Binomial {private readonly long[] factorial;private readonly long[] inverseFactorial;private readonly long[] inverse;private readonly int mod;public Binomial(int size, int primeMod) {size++;factorial = new long[size];inverseFactorial = new long[size];inverse = new long[size];mod = primeMod;Setup(size);}private void Setup(int size) {factorial[0] = factorial[1] = 1;inverseFactorial[0] = inverseFactorial[1] = 1;inverse[1] = 1;for (int i = 2; i < size; i++) {factorial[i] = factorial[i - 1] * i % mod;inverse[i] = (mod - (mod / i) * inverse[mod % i] % mod);inverseFactorial[i] = inverseFactorial[i - 1] * inverse[i] % mod;}}public long C(int s, int t) {if (s < 0 || t < 0 || s < t) {return 0;}if (t == 0 || s == t) {return 1;}if (s >= mod) {return C(s % mod, t % mod) * C(s / mod, t / mod) % mod; // Lucas' theorem}return factorial[s] * inverseFactorial[t] % mod * inverseFactorial[s - t] % mod;}public long this[int s, int t] {get {return C(s, t);}}public long P(int s, int t) {if (s < 0 || t < 0 || s < t) return 0;return factorial[s] * inverseFactorial[s - t] % mod;}/// <summary>/// s 種類のものから重複を許して t 個選ぶ場合の数////// </summary>public long H(int s, int t) {if (s < 0 || t < 0) return 0;if (s == 0 && t == 0) return 1;return C(s + t - 1, t);}public long H1(int s, int t) {return H(s, t - s);}}public partial struct ModInt : IEquatable<ModInt> {private static int mod = 0;private long _value;public ModInt(long x) {_value = x;Normalize();}private static long RegularMod(long x, int mod) {if (x >= mod) {if (x < 2 * mod) {return x - mod;}return x % mod;}if (x >= 0) {return x;}x = mod - RegularMod(-x, mod);return x == mod ? 0 : x;}public static int SetModValue(int m) {return mod = m;}public static int SetMod998244353() { return SetModValue(998244353); }public static int SetMod1000000007() { return SetModValue(1000000007); }private void Normalize() {_value = RegularMod(_value, mod);}public override string ToString() {return _value.ToString(CultureInfo.InvariantCulture);}public int ToInt() {return (int)_value;}public static bool operator ==(ModInt c1, ModInt c2) {return c1._value == c2._value;}public static bool operator !=(ModInt c1, ModInt c2) {return !(c1 == c2);}public static ModInt operator +(ModInt x, ModInt y) {return new ModInt(x._value + y._value);}public static ModInt operator -(ModInt x, ModInt y) {return new ModInt(x._value - y._value);}public static ModInt operator -(ModInt x) {return new ModInt(-x._value);}public static ModInt operator *(ModInt x, ModInt y) {return new ModInt(x._value * y._value);}public static ModInt operator /(ModInt x, ModInt y) {return new ModInt(x._value * Inverse(y._value, mod));}public static ModInt operator ++(ModInt x) {return x + 1;}public static ModInt operator --(ModInt x) {return x - 1;}public static ModInt Pow(ModInt x, long n) {if (n < 0) return new ModInt(1) / Pow(x, -n);ModInt r = 1;while (n > 0) {if ((n & 1) != 0) {r *= x;}x *= x;n >>= 1;}return r;}private static long ExtendedGcd(long a, long b, out long x, out long y) {if (b == 0) {x = 1; y = 0;return a;} else {var d = ExtendedGcd(b, a % b, out y, out x);y -= a / b * x;return d;}}private static long Inverse(long a, long mod) {long x = 0, y = 0;if (ExtendedGcd(a, mod, out x, out y) == 1) {return (x + mod) % mod;} else {throw new Exception("Invalid inverse " + a + " " + mod);}}public static implicit operator ModInt(long x) {return new ModInt(x);}public override bool Equals(object obj) {if (obj == null) {return false;}return _value.Equals(((ModInt)obj)._value);}public override int GetHashCode() {return _value.GetHashCode();}public bool Equals(ModInt other) {return _value.Equals(other._value);}object ToDump() { return _value; }}// PREWRITEN CODE BEGINS FROM HEREstatic public class StringExtensions {static public string JoinToString<T>(this IEnumerable<T> source, string separator = " ") {return string.Join(separator, source);}}internal partial class Solver : Scanner {static readonly int? StackSizeInMebiByte = null; //50;public static void StartAndJoin(Action action, int maxStackSize) {var thread = new Thread(new ThreadStart(action), maxStackSize);thread.Start();thread.Join();}public static void Main() {#if LOCALbyte[] inputBuffer = new byte[1000000];var inputStream = Console.OpenStandardInput(inputBuffer.Length);using (var reader = new StreamReader(inputStream, Console.InputEncoding, false, inputBuffer.Length)) {Console.SetIn(reader);new Solver(Console.In, Console.Out).Run();}#elseConsole.SetOut(new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false });if (StackSizeInMebiByte.HasValue) {StartAndJoin(() => new Solver(Console.In, Console.Out).Run(), StackSizeInMebiByte.Value * 1024 * 1024);} else {new Solver(Console.In, Console.Out).Run();}Console.Out.Flush();#endif}#pragma warning disable IDE0052private readonly TextReader cin;private readonly TextWriter cout;private readonly TextWriter cerr;#pragma warning restore IDE0052public Solver(TextReader reader, TextWriter writer): base(reader) {cin = reader;cout = writer;cerr = Console.Error;}public Solver(string input, TextWriter writer): this(new StringReader(input), writer) {}#pragma warning disable IDE1006#pragma warning disable IDE0051private int ni() { return NextInt(); }private int[] ni(int n) { return NextIntArray(n); }private long nl() { return NextLong(); }private long[] nl(int n) { return NextLongArray(n); }private double nd() { return NextDouble(); }private double[] nd(int n) { return NextDoubleArray(n); }private string ns() { return Next(); }private string[] ns(int n) { return NextArray(n); }#pragma warning restore IDE1006#pragma warning restore IDE0051}#if DEBUGinternal static class LinqPadExtension {public static string TextDump<T>(this T obj) {if (obj is IEnumerable) return (obj as IEnumerable).Cast<object>().JoinToString().Dump();else return obj.ToString().Dump();}public static T Dump<T>(this T obj) {return LINQPad.Extensions.Dump(obj);}}#endifpublic class Scanner {private readonly TextReader Reader;private readonly CultureInfo ci = CultureInfo.InvariantCulture;private readonly char[] buffer = new char[2 * 1024];private int cursor = 0, length = 0;private string Token;private readonly StringBuilder sb = new StringBuilder(1024);public Scanner(): this(Console.In) {}public Scanner(TextReader reader) {Reader = reader;}public int NextInt() { return checked((int)NextLong()); }public long NextLong() {var s = Next();long r = 0;int i = 0;bool negative = false;if (s[i] == '-') {negative = true;i++;}for (; i < s.Length; i++) {r = r * 10 + (s[i] - '0');#if DEBUGif (!char.IsDigit(s[i])) throw new FormatException();#endif}return negative ? -r : r;}public double NextDouble() { return double.Parse(Next(), ci); }public string[] NextArray(int size) {string[] array = new string[size];for (int i = 0; i < size; i++) {array[i] = Next();}return array;}public int[] NextIntArray(int size) {int[] array = new int[size];for (int i = 0; i < size; i++) {array[i] = NextInt();}return array;}public long[] NextLongArray(int size) {long[] array = new long[size];for (int i = 0; i < size; i++) {array[i] = NextLong();}return array;}public double[] NextDoubleArray(int size) {double[] array = new double[size];for (int i = 0; i < size; i++) {array[i] = NextDouble();}return array;}public string Next() {if (Token == null) {if (!StockToken()) {throw new Exception();}}var token = Token;Token = null;return token;}public bool HasNext() {if (Token != null) {return true;}return StockToken();}private bool StockToken() {while (true) {sb.Clear();while (true) {if (cursor >= length) {cursor = 0;if ((length = Reader.Read(buffer, 0, buffer.Length)) <= 0) {break;}}var c = buffer[cursor++];if (33 <= c && c <= 126) {sb.Append(c);} else {if (sb.Length > 0) break;}}if (sb.Length > 0) {Token = sb.ToString();return true;}return false;}}}