結果
| 問題 |
No.2568 列辞書順列列
|
| コンテスト | |
| ユーザー |
 viral8
|
| 提出日時 | 2023-12-02 16:11:55 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 655 ms / 3,000 ms |
| コード長 | 18,032 bytes |
| コンパイル時間 | 4,872 ms |
| コンパイル使用メモリ | 87,128 KB |
| 実行使用メモリ | 65,448 KB |
| 最終ジャッジ日時 | 2024-09-26 19:57:11 |
| 合計ジャッジ時間 | 22,212 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 25 |
ソースコード
import java.util.*;
import java.io.*;
import java.awt.Point;
import java.math.BigInteger;
class Main{
private static final BufferedReader br =
new BufferedReader(new InputStreamReader(System.in));
private static final PrintWriter out =
new PrintWriter(System.out);
public static void main(String[] args)throws IOException{
final int mod = 998244353;
String[] str = br.readLine().split(" ");
int N = Integer.parseInt(str[0]);
int M = Integer.parseInt(str[1]);
int Q = Integer.parseInt(str[2]);
long[] subA = new long[N+1];
str = br.readLine().split(" ");
for(int i=0;i<N;i++){
subA[i+1] = subA[i]*M%mod+Integer.parseInt(str[i])-1;
if(subA[i+1]>=mod)
subA[i+1] -= mod;
}
while(Q-->0){
str = br.readLine().split(" ");
int l = Integer.parseInt(str[0]);
int r = Integer.parseInt(str[1]);
long ans = (subA[r]-subA[l-1]*MathFunction.modPow(M,r-l+1,mod)%mod+1)%mod;
out.println((mod+ans)%mod);
}
br.close();
out.close();
}
}
public final class MathFunction {
private static final long[] numberForPrime = {2, 7, 61, 325, 9375, 28178, 450775, 9780504, 1795265022};
/**
* aとbの最大公約数を求めます。戻り値は0以上であることが保証されます。
*
* @param a 公約数を求める整数
* @param b 公約数を求める整数
*
* @return aとbの最大公約数
*/
public static long gcd ( long a, long b ) {
a = Math.abs( a );
b = Math.abs( b );
if ( b == 0 ) {
return a;
}
long temp;
while ( ( temp = a % b ) != 0 ) {
a = b;
b = temp;
}
return b;
}
/**
* aとbの最小公倍数を求めます。
* オーバーフロー検知は出来ません。
*
* @param a 公倍数を求める整数
* @param b 公倍数を求める整数
*
* @return aとbの最小公倍数
*/
public static long lcm ( final long a, final long b ) {
return a / gcd( a, b ) * b;
}
/**
* 引数が素数か判定します。
*
* @param n 検査対象
*
* @return numが素数であるならtrue、素数でないならfalse
*/
public static boolean isPrime ( long n ) {
n = Math.abs( n );
if ( n == 2 ) {
return true;
}
if ( n == 1 || ( n & 1 ) == 0 ) {
return false;
}
long d = n - 1;
while ( ( d & 1 ) == 0 ) {
d >>= 1;
}
for ( final long a: numberForPrime ) {
if ( a >= n ) {
return true;
}
long t = d;
long y = bigModPow( a, t, n );
while ( t < n - 1 && y != 1 && y != n - 1 ) {
y = bigModPow( y, 2, n );
t <<= 1;
}
if ( y != n - 1 && ( t & 1 ) == 0 ) {
return false;
}
}
return true;
}
/**
* a**b mod mを計算します。
* Bigintegerを用いるのでオーバーフローは起こりません。
*
* @param a
* @param b
* @param m
* @return a**b mod m
*/
private static long bigModPow ( final long a, final long b, final long m ) {
return BigInteger.valueOf( a ).modPow( BigInteger.valueOf( b ), BigInteger.valueOf( m ) ).longValue();
}
/**
* num以下の素数を列挙します。
*
* @param num 素数を探す上限値
*
* @return num以下の素数のint型配列
*/
public static int[] primes ( final int num ) {
if ( num < 2 ) {
return new int[0];
}
final BitSet numbers = new BitSet( num + 1 );
numbers.set( 2, num + 1 );
final int limit = ( int )Math.sqrt( num );
for ( int i = 2; i <= limit; ++i ) {
if ( numbers.get( i ) ) {
for ( int j = i * i; j <= num; j += i ) {
numbers.clear( j );
}
}
}
final int[] answer = new int[numbers.cardinality()];
int i = 2, index = 0;
do {
i = numbers.nextSetBit( i );
answer[index++] = i++;
} while ( index != answer.length );
return answer;
}
/**
* a**bを計算します。
*
* @param a 被累乗数
* @param b 指数
*
* @return a**b
*/
public static long pow ( long a, long b ) {
long ans = 1;
while ( b > 0 ) {
if ( ( b & 1 ) == 1 ) {
ans *= a;
}
a *= a;
b >>= 1;
}
return ans;
}
/**
* a**bをmodで割ったあまりを計算します。
*
* @param a 被累乗数
* @param b 指数
* @param mod 法とする整数
*
* @return a**bをmodで割ったあまり
*/
public static long modPow ( long a, long b, final long mod ) {
long ans = 1;
a %= mod;
while ( b > 0 ) {
if ( ( b & 1 ) == 1 ) {
ans *= a;
}
ans %= mod;
a *= a;
a %= mod;
b >>= 1;
}
return ans;
}
/**
* nCrを計算します。
*
* @param n 二項係数を求めるのに用いる値
* @param r 二項係数を求めるのに用いる値
*
* @return nCr
*/
public static long combi ( final long n, long r ) {
if ( r < 0 || n < r ) {
return 0;
}
long ans = 1;
r = Math.min( n - r, r );
for ( int i = 0; i < r; ++i ) {
ans *= n - i;
ans /= i + 1;
}
return ans;
}
/**
* nCrをmodで割ったあまりを計算します。
*
* @param n 二項係数を求めるのに用いる値
* @param r 二項係数を求めるのに用いる値
* @param mod 法とする整数
*
* @return nCrをmodで割ったあまり
*/
public static long modCombi ( final long n, long r, final long mod ) {
if ( r < 0 || n < r ) {
return 0;
}
long ans = 1;
r = Math.min( n - r, r );
for ( int i = 0; i < r; ++i ) {
ans *= n - i;
ans %= mod;
ans *= modPow( i + 1, mod - 2, mod );
ans %= mod;
}
return ans;
}
/**
* 引数の前半二点、後半二点で構成される二線分が交差しているか返します。
*
* @param x1 点1のx座標
* @param y1 点1のy座標
* @param x2 点2のx座標
* @param y2 点2のy座標
* @param x3 点3のx座標
* @param y3 点3のy座標
* @param x4 点4のx座標
* @param y4 点4のy座標
*
* @return 交差している(線分の端が他方の線分上に存在する場合も含む)場合は1、同一線分直線上なら0、それ以外は-1
*/
public static int isCrossed ( final int x1, final int y1,
final int x2, final int y2,
final int x3, final int y3,
final int x4, final int y4 ) {
final long s1 = ( long )( x1 - x2 ) * ( y3 - y1 ) - ( long )( y1 - y2 ) * ( x3 - x1 );
final long t1 = ( long )( x1 - x2 ) * ( y4 - y1 ) - ( long )( y1 - y2 ) * ( x4 - x1 );
final long s2 = ( long )( x3 - x4 ) * ( y1 - y3 ) - ( long )( y3 - y4 ) * ( x1 - x3 );
final long t2 = ( long )( x3 - x4 ) * ( y2 - y3 ) - ( long )( y3 - y4 ) * ( x2 - x3 );
final long temp1 = s1 * t1;
final long temp2 = s2 * t2;
if ( temp1 > 0 || temp2 > 0 ) {
return -1;
}
if ( temp1 == 0 && temp2 == 0 ) {
return 0;
}
return 1;
}
/**
* 引数の前半二点、後半二点で構成される二線分が交差しているか返します。
*
* @param p1 点1
* @param p2 点2
* @param p3 点3
* @param p4 点4
*
* @return 交差している(線分の端が他方の線分上に存在する場合も含む)場合は1、同一線分直線上なら0、それ以外は-1
*/
public static int isCrossed ( final Point p1, final Point p2, final Point p3, final Point p4 ) {
return isCrossed( p1.x, p1.y, p2.x, p2.y, p3.x, p3.y, p4.x, p4.y );
}
/**
* numをmodで割ったあまりを返します。
* 戻り値は0以上mod未満であることが保証されます。
*
* @param num 被除算数
* @param mod 法とする値
*
* @return numをmodで割ったあまり
*/
public static long remainder ( long num, final long mod ) {
num %= mod;
if ( num < 0 ) {
num += mod;
}
return num;
}
/**
* numが何桁かを返します。
* 0は1桁として捉えます。
*
* @param num 調べる整数
*
* @return numの桁数
*/
public static int digit ( final long num ) {
if ( num < 10L ) {
return 1;
}
if ( num < 100L ) {
return 2;
}
if ( num < 1000L ) {
return 3;
}
if ( num < 10000L ) {
return 4;
}
if ( num < 100000L ) {
return 5;
}
if ( num < 1000000L ) {
return 6;
}
if ( num < 10000000L ) {
return 7;
}
if ( num < 100000000L ) {
return 8;
}
if ( num < 1000000000L ) {
return 9;
}
if ( num < 10000000000L ) {
return 10;
}
if ( num < 100000000000L ) {
return 11;
}
if ( num < 1000000000000L ) {
return 12;
}
if ( num < 10000000000000L ) {
return 13;
}
if ( num < 100000000000000L ) {
return 14;
}
if ( num < 1000000000000000L ) {
return 15;
}
if ( num < 10000000000000000L ) {
return 16;
}
if ( num < 100000000000000000L ) {
return 17;
}
if ( num < 1000000000000000000L ) {
return 18;
}
return 19;
}
/**
* 渡された値の最大値を求めます。
* @param nums
* @return
*/
public static int max ( final int... nums ) {
int ans = Integer.MIN_VALUE;
for ( int num: nums ) {
ans = Math.max( ans, num );
}
return ans;
}
/**
* 渡された値の最大値を求めます。
* @param nums
* @return
*/
public static long max ( final long... nums ) {
long ans = Long.MIN_VALUE;
for ( long num: nums ) {
ans = Math.max( ans, num );
}
return ans;
}
/**
* 渡された値の最大値を求めます。
* @param nums
* @return
*/
public static double max ( final double... nums ) {
double ans = -Double.MIN_VALUE;
for ( double num: nums ) {
ans = Math.max( ans, num );
}
return ans;
}
/**
* 渡された値の最大値を求めます。
* @param nums
* @return
*/
public static <E extends Comparable<E>> E max ( final E[] nums ) {
E ans = nums[0];
for ( E value: nums ) {
if ( ans.compareTo( value ) > 0 ) {
ans = value;
}
}
return ans;
}
/**
* 渡された値の最小値を求めます。
* @param nums
* @return
*/
public static int min ( final int... nums ) {
int ans = Integer.MAX_VALUE;
for ( int num: nums ) {
ans = Math.min( ans, num );
}
return ans;
}
/**
* 渡された値の最小値を求めます。
* @param nums
* @return
*/
public static long min ( final long... nums ) {
long ans = Long.MAX_VALUE;
for ( long num: nums ) {
ans = Math.min( ans, num );
}
return ans;
}
/**
* 渡された値の最小値を求めます。
* @param nums
* @return
*/
public static double min ( final double... nums ) {
double ans = Double.MAX_VALUE;
for ( double num: nums ) {
ans = Math.min( ans, num );
}
return ans;
}
/**
* 渡された値の最小値を求めます。
* @param nums
* @return
*/
public static <E extends Comparable<E>> E min ( final E[] nums ) {
E ans = nums[0];
for ( E value: nums ) {
if ( ans.compareTo( value ) < 0 ) {
ans = value;
}
}
return ans;
}
/**
* 渡された値の総和を求めます。
* @param nums
* @return
*/
public static long sum ( final int... nums ) {
long ans = 0;
for ( int num: nums ) {
ans += num;
}
return ans;
}
/**
* 渡された値の総和を求めます。
* @param nums
* @return
*/
public static long sum ( final long... nums ) {
long ans = 0;
for ( long num: nums ) {
ans += num;
}
return ans;
}
/**
* 渡された値の総和をmodで割ったあまりを求めます。
* @param nums
* @param mod
* @return
*/
public static long modSum ( final long mod, final int... nums ) {
long ans = 0;
for ( int num: nums ) {
ans += num;
ans %= mod;
}
if ( ans < 0 ) {
ans += mod;
}
return ans;
}
/**
* 渡された値の総和をmodで割ったあまりを求めます。
* @param nums
* @param mod
* @return
*/
public static long modSum ( final long mod, final long... nums ) {
long ans = 0;
for ( long num: nums ) {
ans += num;
ans %= mod;
}
if ( ans < 0 ) {
ans += mod;
}
return ans;
}
/**
* 渡された配列の指定された区間の総和を求めます。
* @param nums
* @param from
* @param to
* @return
*/
public static long sum ( final int[] nums, int from, int to ) {
long ans = 0;
for ( int i = from; i < to; ++i ) {
ans += nums[i];
}
return ans;
}
/**
* 渡された配列の指定された区間の総和を求めます。
* @param nums
* @param from
* @param to
* @return
*/
public static long sum ( final long[] nums, int from, int to ) {
long ans = 0;
for ( int i = from; i < to; ++i ) {
ans += nums[i];
}
return ans;
}
/**
* 渡された配列の指定された区間の総和をmodで割ったあまりを求めます。
* @param nums
* @param from
* @param to
* @param mod
* @return
*/
public static long modSum ( final int[] nums, int from, int to, long mod ) {
long ans = 0;
for ( int i = from; i < to; ++i ) {
ans += nums[i];
ans %= mod;
}
if ( ans < 0 ) {
ans += mod;
}
return ans;
}
/**
* 渡された配列の指定された区間の総和をmodで割ったあまりを求めます。
* @param nums
* @param from
* @param to
* @param mod
* @return
*/
public static long modSum ( final long[] nums, int from, int to, long mod ) {
long ans = 0;
for ( int i = from; i < to; ++i ) {
ans += nums[i];
ans %= mod;
}
if ( ans < 0 ) {
ans += mod;
}
return ans;
}
/**
* 引数numがl以上r未満の範囲内か判定します。
*
* @param num 判定する値
* @param l 下限(lを含む)
* @param r 上限(rを含まない)
*
* @return l <= num < rを満たしていればtrue 、 満たしていなければfalse
*/
public static boolean rangeCheck ( final int num, final int l, final int r ) {
return l <= num && num < r;
}
/**
* 引数numがl以上r未満の範囲内か判定します。
*
* @param num 判定する値
* @param l 下限(lを含む)
* @param r 上限(rを含まない)
*
* @return l <= num < rを満たしていればtrue 、 満たしていなければfalse
*/
public static boolean rangeCheck ( final long num, final long l, final long r ) {
return l <= num && num < r;
}
/**
* 引数numがl以上r未満の範囲内か判定します。
*
* @param num 判定する値
* @param l 下限(lを含む)
* @param r 上限(rを含まない)
*
* @return l <= num < rを満たしていればtrue 、 満たしていなければfalse
*/
public static boolean rangeCheck ( final double num, final double l, final double r ) {
return l <= num && num < r;
}
/**
* 引数numがl以上r未満の範囲内か判定します。
*
* @param num 判定する値
* @param l 下限(lを含む)
* @param r 上限(rを含まない)
*
* @return l <= num < rを満たしていればtrue 、 満たしていなければfalse
*/
public static <E extends Comparable<E>> boolean rangeCheck ( final E num, final E l, final E r ) {
return 0 <= l.compareTo( num ) && 0 < num.compareTo( r );
}
/**
* 引数numがlより大きく、r未満の範囲内か判定します。
*
* @param num 判定する値
* @param l 下限(lを含まない)
* @param r 上限(rを含まない)
*
* @return l < num < rを満たしていればtrue 、 満たしていなければfalse
*/
public static boolean rangeCheckOpen ( final int num, final int l, final int r ) {
return l < num && num < r;
}
/**
* 引数numがlより大きく、r未満の範囲内か判定します。
*
* @param num 判定する値
* @param l 下限(lを含まない)
* @param r 上限(rを含まない)
*
* @return l < num < rを満たしていればtrue 、 満たしていなければfalse
*/
public static boolean rangeCheckOpen ( final long num, final long l, final long r ) {
return l < num && num < r;
}
/**
* 引数numがlより大きく、r未満の範囲内か判定します。
*
* @param num 判定する値
* @param l 下限(lを含まない)
* @param r 上限(rを含まない)
*
* @return l < num < rを満たしていればtrue 、 満たしていなければfalse
*/
public static boolean rangeCheckOpen ( final double num, final double l, final double r ) {
return l < num && num < r;
}
/**
* 引数numがlより大きく、r未満の範囲内か判定します。
*
* @param num 判定する値
* @param l 下限(lを含まない)
* @param r 上限(rを含まない)
*
* @return l < num < rを満たしていればtrue 、 満たしていなければfalse
*/
public static <E extends Comparable<E>> boolean rangeCheckOpen ( final E num, final E l, final E r ) {
return 0 < l.compareTo( num ) && 0 < num.compareTo( r );
}
/**
* 引数numがl以上r以下の範囲内か判定します。
*
* @param num 判定する値
* @param l 下限(lを含む)
* @param r 上限(rを含む)
*
* @return l <= num <= rを満たしていればtrue 、 満たしていなければfalse
*/
public static boolean rangeCheckClose ( final int num, final int l, final int r ) {
return l <= num && num <= r;
}
/**
* 引数numがl以上r以下の範囲内か判定します。
*
* @param num 判定する値
* @param l 下限(lを含む)
* @param r 上限(rを含む)
*
* @return l <= num <= rを満たしていればtrue 、 満たしていなければfalse
*/
public static boolean rangeCheckClose ( final long num, final long l, final long r ) {
return l <= num && num <= r;
}
/**
* 引数numがl以上r以下の範囲内か判定します。
*
* @param num 判定する値
* @param l 下限(lを含む)
* @param r 上限(rを含む)
*
* @return l <= num <= rを満たしていればtrue 、 満たしていなければfalse
*/
public static boolean rangeCheckClose ( final double num, final double l, final double r ) {
return l <= num && num <= r;
}
/**
* 引数numがl以上r以下の範囲内か判定します。
*
* @param num 判定する値
* @param l 下限(lを含む)
* @param r 上限(rを含む)
*
* @return l <= num <= rを満たしていればtrue 、 満たしていなければfalse
*/
public static <E extends Comparable<E>> boolean rangeCheckClose ( final E num, final E l, final E r ) {
return 0 <= l.compareTo( num ) && 0 <= num.compareTo( r );
}
}