Hello, Codeforces.
Today, as the main manager of a contest, I have decided to release the code for TheForce Round # 42 Top 10.
The reason for this decision is that during the middle of the contest, we noticed unusual standings:
As a convention of codeforces, the code of all participants after the contest will be made public. I have decided to do the same thing here, and I believe that if you are a normal and honest participant, it will not infringe upon any of your rights. Also, we are checking the code of the participants and making cautious judgments.
The allocation of prizes and the calculation of TheForce Rating will be delayed. Sorry for any inconvenience caused.
We sincerely hope to maintain a fair and honest competitive environment for all participants. Integrity is the cornerstone of programming contests, and we believe that upholding these values benefits everyone in the community.
Best regards,
TheForce Round #42 Contest Team
ayush_295
A
#include<bits/stdc++.h>
using namespace std;
#define int long long int
const int log(int x , int y){
int count = 0;
while(x!=0){
x=x/y;
count++;
}
return count;
}
const int ceil(int x , int y){
if(x%y == 0) return x/y;
else return (x/y)+1;
}
bool isPrime(int n){
if (n <= 1) return false;
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) return false;
}
return true;
}
int lcm(int x , int y){
int alpha = (x*y)/(__gcd(x,y));
return alpha;
}
// int t[1000007];
int myPow(int x, int n) {
int ans = 1.0;
for (int i = 0; i < n; i++) {
ans = ans * x;
}
return ans;
}
int stringtonum(string s) {
int num = 0;
for (char c : s) {
num = num * 10 + (c - '0');
}
return num;
}
bool contains_seven(int n) {
while (n > 0) {
if (n % 10 == 7) return true;
n /= 10;
}
return false;
}
bool check_sqrt(int n){
int x = sqrt(n);
if(x*x == n) return true;
else return false;
}
void solve(int tests){
int n;
cin>>n;
cout<<n<<endl;
}
int32_t main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int tests;
cin>>tests;
for(int i=0;i<tests;i++){
solve(i);
}
}
B
#include<bits/stdc++.h>
using namespace std;
#define int long long int
const int log(int x , int y){
int count = 0;
while(x!=0){
x=x/y;
count++;
}
return count;
}
const int ceil(int x , int y){
if(x%y == 0) return x/y;
else return (x/y)+1;
}
bool isPrime(int n){
if (n <= 1) return false;
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) return false;
}
return true;
}
int lcm(int x , int y){
int alpha = (x*y)/(__gcd(x,y));
return alpha;
}
// int t[1000007];
int myPow(int x, int n) {
int ans = 1.0;
for (int i = 0; i < n; i++) {
ans = ans * x;
}
return ans;
}
int stringtonum(string s) {
int num = 0;
for (char c : s) {
num = num * 10 + (c - '0');
}
return num;
}
bool contains_seven(int n) {
while (n > 0) {
if (n % 10 == 7) return true;
n /= 10;
}
return false;
}
bool check_sqrt(int n){
int x = sqrt(n);
if(x*x == n) return true;
else return false;
}
void solve(int tests){
int n,x;
cin>>n>>x;
int c[n] , a[n];
for(int i=0;i<n;i++){
cin>>c[i];
}
for(int i=0;i<n;i++){
cin>>a[i];
}
int max_op = n;
vector<vector<int>> dp(n+1 , vector<int>(max_op+1 , -1 ));
dp[0][0] = x;
for(int i=0;i<n;i++){
for(int op = 0; op<= max_op ; op ++){
if(dp[i][op] <0 ) continue;
if(dp[i][op] >= c[i]){
dp[i+1][op] = max(dp[i+1][op] , dp[i][op] - c[i] + a[i]);
}
if(op+1 <= max_op){
dp[i+1][op+1] = max(dp[i+1][op+1] , dp[i][op] + a[i]);
}
}
}
int ans = -1;
for(int i=0;i<=max_op;i++){
if(dp[n][i] >= 0){
ans = i;
break;
}
}
cout<<ans<<endl;
}
int32_t main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int tests;
cin>>tests;
for(int i=0;i<tests;i++){
solve(i);
}
}
C
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
vector<int> sieve_primes(int MAXP) {
vector<bool> is_composite(MAXP+1,false);
vector<int> primes;
for (int i = 2; i <= MAXP; ++i) {
if (!is_composite[i]) {
primes.push_back(i);
if ((int64)i * i <= MAXP) {
for (int j = i*i; j <= MAXP; j += i)
is_composite[j] = true;
}
}
}
return primes;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
vector<int> ns(t);
int max_n = 0;
for(int i = 0; i < t; i++){
cin >> ns[i];
max_n = max(max_n, ns[i]);
}
int limit = floor(sqrt(max_n)) + 1;
auto primes = sieve_primes(limit);
for (int n : ns) {
int64 nn = n;
int64 sigma = 1;
int64 tau = 1;
for (int p : primes) {
if ((int64)p * p > nn) break;
if (nn % p == 0) {
int e = 0;
int64 p_pow = 1;
while (nn % p == 0) {
nn /= p;
e++;
p_pow *= p;
}
int64 sum_p = (p_pow * p - 1) / (p - 1);
sigma *= sum_p;
tau *= (e + 1);
}
}
if (nn > 1) {
sigma *= (1 + nn);
tau *= 2;
}
cout << (sigma - tau) << "\n";
}
return 0;
}
D
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 998244353;
inline int add(int a, int b) {
a += b;
if (a >= MOD) a -= MOD;
return a;
}
inline int mul(ll a, ll b) {
return int((a * b) % MOD);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
vector<int> ns(T);
int mx = 0;
for(int i = 0; i < T; i++){
cin >> ns[i];
mx = max(mx, ns[i]);
}
vector<int> fact(mx+1), der(mx+1);
fact[0] = 1;
for(int i = 1; i <= mx; i++){
fact[i] = mul(fact[i-1], i);
}
der[0] = 1;
if(mx >= 1) der[1] = 0;
for(int i = 2; i <= mx; i++){
der[i] = mul(i - 1, add(der[i-1], der[i-2]));
}
for(int n : ns){
if(n % 2 == 0){
cout << 1 << "\n";
} else {
cout << mul(fact[n], der[n]) << "\n";
}
}
return 0;
}
E
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 1000000007;
inline int add(int a, int b) {
a += b;
if (a >= MOD) a -= MOD;
return a;
}
inline int sub(int a, int b) {
a -= b;
if (a < 0) a += MOD;
return a;
}
inline int mul(ll a, ll b) {
return int((a * b) % MOD);
}
int modInv(int x) {
int res = 1, power = MOD - 2;
ll base = x;
while (power) {
if (power & 1) res = int((res * base) % MOD);
base = (base * base) % MOD;
power >>= 1;
}
return res;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
vector<int> ns(T);
vector<vector<int>> allA(T);
int max_n = 0;
for(int tc = 0; tc < T; tc++){
int n;
cin >> n;
ns[tc] = n;
max_n = max(max_n, n);
allA[tc].resize(n);
for(int i = 0; i < n; i++){
cin >> allA[tc][i];
}
}
const int P = 8;
const int primes[P] = {2,3,5,7,11,13,17,19};
static int e_exp[21][P];
for(int v = 1; v <= 20; v++){
int x = v;
for(int j = 0; j < P; j++){
int p = primes[j];
e_exp[v][j] = 0;
while(x % p == 0) {
e_exp[v][j]++;
x /= p;
}
}
}
int Mmask = 1<<P;
static int lsbIdx[1<<P], popc[1<<P];
for(int m = 1; m < Mmask; m++){
lsbIdx[m] = __builtin_ctz(m);
popc[m] = popc[m>>1] + (m&1);
}
popc[0] = 0;
int maxInv = 4 * max_n + 5;
vector<int> inv(maxInv);
inv[1] = 1;
for(int i = 2; i < maxInv; i++){
inv[i] = int((ll)(MOD - MOD/i) * inv[MOD % i] % MOD);
}
for(int tc = 0; tc < T; tc++){
int n = ns[tc];
auto &A = allA[tc];
int S[P] = {0};
vector<int> sum_U(Mmask, 0);
sum_U[0] = 1;
int answer = 0;
vector<int> Q(Mmask), Aprod(Mmask);
for(int idx = 0; idx < n; idx++){
int val = A[idx];
for(int j = 0; j < P; j++){
S[j] += e_exp[val][j];
}
int CP1[P];
for(int j = 0; j < P; j++){
CP1[j] = S[j] + 1;
}
int B_fullset = 1;
for(int j = 0; j < P; j++){
B_fullset = mul(B_fullset, CP1[j]);
}
Q[0] = 1;
Aprod[0] = 1;
for(int m = 1; m < Mmask; m++){
int b = lsbIdx[m];
int pm = m ^ (1<<b);
Q[m] = mul(Q[pm], inv[ CP1[b] ]);
Aprod[m] = mul(Aprod[pm], S[b]);
}
ll curSum = 0;
for(int m = 0; m < Mmask; m++){
int sign = (popc[m] & 1) ? MOD - 1 : 1;
int PU = mul(B_fullset, Q[m]);
ll t = (ll)sum_U[m] * PU % MOD;
curSum += sign * t;
if(curSum >= (1LL<<62)) curSum %= MOD;
}
curSum %= MOD;
answer = int((answer + curSum) % MOD);
for(int m = 0; m < Mmask; m++){
sum_U[m] = add(sum_U[m], Aprod[m]);
}
}
cout << answer << "\n";
}
return 0;
}
arnabmanna
A
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(br.readLine().trim());
StringBuilder sb = new StringBuilder();
while (t-- > 0) {
long n = Long.parseLong(br.readLine().trim());
sb.append(n).append('\n');
}
System.out.print(sb);
}
}
B
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer tok = new StringTokenizer(in.readLine());
int t = Integer.parseInt(tok.nextToken());
final long NEG_INF = Long.MIN_VALUE / 4;
while (t-- > 0) {
tok = new StringTokenizer(in.readLine());
int n = Integer.parseInt(tok.nextToken());
long x = Long.parseLong(tok.nextToken());
int[] c = new int[n];
int[] a = new int[n];
tok = new StringTokenizer(in.readLine());
for (int i = 0; i < n; i++) {
c[i] = Integer.parseInt(tok.nextToken());
}
tok = new StringTokenizer(in.readLine());
for (int i = 0; i < n; i++) {
a[i] = Integer.parseInt(tok.nextToken());
}
long[] dp = new long[n + 1];
Arrays.fill(dp, NEG_INF);
dp[0] = x;
for (int i = 0; i < n; i++) {
long[] dp2 = new long[n + 1];
Arrays.fill(dp2, NEG_INF);
for (int j = 0; j <= i; j++) {
if (dp[j] < 0) continue;
if (dp[j] >= c[i]) {
dp2[j] = Math.max(dp2[j], dp[j] - c[i] + a[i]);
}
dp2[j + 1] = Math.max(dp2[j + 1], dp[j] + a[i]);
}
dp = dp2;
}
int answer = 0;
while (answer <= n && dp[answer] < 0) {
answer++;
}
System.out.println(answer);
}
}
}
C
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(r.readLine());
List<Integer> p = sieve(31623);
StringBuilder o = new StringBuilder();
while (t-- > 0) {
long n = Long.parseLong(r.readLine());
long x = n, s = 1, c = 1;
for (int d : p) {
if ((long) d * d > x) break;
if (x % d == 0) {
int e = 0;
while (x % d == 0) {
x /= d;
e++;
}
long pw = 1;
for (int i = 0; i <= e; i++) pw *= d;
long sum = (pw - 1) / (d - 1);
s *= sum;
c *= (e + 1);
}
}
if (x > 1) {
s *= (1 + x);
c *= 2;
}
o.append(s - c).append('\n');
}
System.out.print(o);
}
private static List<Integer> sieve(int n) {
boolean[] a = new boolean[n + 1];
List<Integer> l = new ArrayList<>();
for (int i = 2; i <= n; i++) {
if (!a[i]) {
l.add(i);
if ((long) i * i <= n) {
for (int j = i * i; j <= n; j += i) a[j] = true;
}
}
}
return l;
}
}
D
import java.io.*;
public class Main {
static final int MOD = 998244353;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(br.readLine());
int[] ns = new int[t];
int maxOdd = 1;
for (int i = 0; i < t; i++) {
ns[i] = Integer.parseInt(br.readLine());
if ((ns[i] & 1) == 1) {
maxOdd = Math.max(maxOdd, ns[i]);
}
}
long[] fact = new long[maxOdd + 1];
fact[0] = 1;
for (int i = 1; i <= maxOdd; i++) {
fact[i] = fact[i - 1] * i % MOD;
}
long[] der = new long[maxOdd + 1];
der[0] = 1;
if (maxOdd >= 1) der[1] = 0;
for (int i = 2; i <= maxOdd; i++) {
der[i] = ( (i - 1L) * (der[i - 1] + der[i - 2]) ) % MOD;
}
StringBuilder sb = new StringBuilder();
for (int n : ns) {
if ((n & 1) == 0) {
sb.append(1);
} else {
sb.append( fact[n] * der[n] % MOD );
}
sb.append('\n');
}
System.out.print(sb);
}
}
E
import java.io.*;
import java.util.*;
public class Main {
static final long M = 1_000_000_007L;
static final int[] P = {2, 3, 5, 7, 11, 13, 17, 19};
@SuppressWarnings("unchecked")
static List<int[]>[] L = new ArrayList[21];
public static void main(String[] args) throws Exception {
f();
F s = new F(System.in);
StringBuilder o = new StringBuilder();
int t = s.ni();
while (t-- > 0) {
int n = s.ni();
int[] a = new int[n];
for (int i = 0; i < n; i++) a[i] = s.ni();
o.append(sv(a)).append('\n');
}
System.out.print(o);
}
static long sv(int[] a) {
int n = a.length;
long[] p = new long[256];
long[] mp = new long[256];
p[0] = 1;
long ans = (long) n * (n + 1) / 2 % M;
for (int i = 0; i < n; i++) {
List<int[]> c = L[a[i]];
if (c.isEmpty()) continue;
long[] np = p.clone(), nm = mp.clone(), d = new long[256];
for (int[] pr : c) {
int msk = pr[0], w = pr[1];
for (int j = 0; j < 256; j++) {
if ((j & msk) != 0 || (j != 0 && p[j] == 0)) continue;
int nmj = j | msk;
long pp = (p[j] * w) % M;
np[nmj] = (np[nmj] + pp) % M;
long min = (j == 0) ? (long) (i + 1) * w % M : (mp[j] * w) % M;
nm[nmj] = (nm[nmj] + min) % M;
d[nmj] = (d[nmj] + min) % M;
}
}
long rw = n - i;
for (int j = 1; j < 256; j++) {
if (d[j] != 0) ans = (ans + d[j] * rw) % M;
}
p = np;
mp = nm;
}
return ans;
}
static void f() {
for (int v = 1; v <= 20; v++) {
int[] e = new int[8];
int x = v;
for (int i = 0; i < 8; i++) {
while (x % P[i] == 0) { e[i]++; x /= P[i]; }
}
int m = 0;
for (int i = 0; i < 8; i++) if (e[i] != 0) m |= 1 << i;
List<int[]> list = new ArrayList<>();
for (int s = m; s > 0; s = (s - 1) & m) {
int w = 1;
for (int i = 0; i < 8; i++) if ((s & (1 << i)) != 0) w *= e[i];
list.add(new int[]{s, w});
}
L[v] = list;
}
}
private static class F {
private final byte[] b = new byte[1 << 16];
private int l = 0, p = 0;
private final InputStream in;
F(InputStream in) { this.in = in; }
int ni() throws IOException {
int c, s = 1, x = 0;
while ((c = r()) <= ' ') ;
if (c == '-') { s = -1; c = r(); }
do { x = x * 10 + (c - '0'); } while ((c = r()) > ' ');
return x * s;
}
private int r() throws IOException {
if (p >= l) {
l = in.read(b);
p = 0;
if (l <= 0) return -1;
}
return b[p++];
}
}
}
nika-skybytska
A
#ifndef IO_HPP
#define IO_HPP 1
#include <array>
#include <cstdint>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
namespace io {
void __read(char& c) { std::cin >> c; }
void __read(std::string& s) { std::cin >> s; }
template <typename T>
void __read_real(T& x) {
std::string s;
__read(s);
x = std::stod(s);
}
template <typename T>
void __read_integer(T& x) {
std::cin >> x;
}
void __read(int& x) { __read_integer(x); }
void __read(unsigned int& x) { __read_integer(x); }
void __read(long& x) { __read_integer(x); }
void __read(unsigned long& x) { __read_integer(x); }
void __read(long long& x) { __read_integer(x); }
void __read(unsigned long long& x) { __read_integer(x); }
void __read(double& x) { __read_real(x); }
void __read(long double& x) { __read_real(x); }
template <class U, class V>
void __read(std::pair<U, V>& p) {
__read(p.first);
__read(p.second);
}
template <size_t N = 0, typename T>
void __read_tuple(T& t) {
if constexpr (N < std::tuple_size<T>::value) {
auto& x = std::get<N>(t);
__read(x);
__read_tuple<N + 1>(t);
}
}
template <class... T>
void __read(std::tuple<T...>& t) {
__read_tuple(t);
}
template <size_t N = 0, typename T>
void __read(std::array<T, N>& a) {
for (auto& x : a) {
__read(x);
}
}
template <class T>
void __read(std::vector<T>& v) {
for (auto& x : v) {
__read(x);
}
}
void read() {}
template <class H, class... T>
void read(H& h, T&... t) {
__read(h), read(t...);
}
void __write(const char c) { std::cout << c; }
void __write(const std::string s) {
for (char c : s) {
__write(c);
}
}
void __write(const char* s) {
size_t len = strlen(s);
for (size_t i = 0; i < len; ++i) {
__write(s[i]);
}
}
template <typename T>
void __write_integer(T x) {
std::cout << x;
}
template <typename T>
void __write_real(T x) {
std::ostringstream oss;
oss << std::fixed << std::setprecision(15) << double(x);
std::string s = oss.str();
__write(s);
}
void __write(int x) { __write_integer(x); }
void __write(unsigned int x) { __write_integer(x); }
void __write(long x) { __write_integer(x); }
void __write(unsigned long x) { __write_integer(x); }
void __write(long long x) { __write_integer(x); }
void __write(unsigned long long x) { __write_integer(x); }
void __write(double x) { __write_real(x); }
void __write(long double x) { __write_real(x); }
template <class U, class V>
void __write(const std::pair<U, V> p) {
__write(p.first);
__write(' ');
__write(p.second);
}
template <size_t N = 0, typename T>
void __write_tuple(const T t) {
if constexpr (N < std::tuple_size<T>::value) {
if constexpr (N > 0) {
__write(' ');
}
const auto x = std::get<N>(t);
__write(x);
__write_tuple<N + 1>(t);
}
}
template <class... T>
void __write(std::tuple<T...> t) {
__write_tuple(t);
}
template <class T, size_t S>
void __write(const std::array<T, S> a) {
auto n = a.size();
for (size_t i = 0; i < n; i++) {
if (i) {
__write(' ');
}
__write(a[i]);
}
}
template <class T>
void __write(const std::vector<T> v) {
auto n = v.size();
for (size_t i = 0; i < n; i++) {
if (i) {
__write(' ');
}
__write(v[i]);
}
}
template <class T>
void __write(const std::set<T> s) {
__write(std::vector<T>{s.cbegin(), s.cend()});
}
template <class K, class V>
void __write(const std::map<K, V> m) {
__write(std::vector<std::pair<K, V>>{m.cbegin(), m.cend()});
}
void write() { __write('\n'); }
template <class Head, class... Tail>
void write(Head&& head, Tail&&... tail) {
__write(head);
if (sizeof...(Tail)) {
__write(' ');
}
write(std::forward<Tail>(tail)...);
}
} // namespace io
#endif // IO_HPP
#ifdef ONLINE_JUDGE
#include <bits/allocator.h>
#pragma GCC optimize("Ofast,unroll-loops,inline")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#endif
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
// using namespace atcoder;
using namespace io;
template <typename T>
using ordered_set =
tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
void solve() {
int64_t n;
read(n);
write(n);
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int t;
read(t);
while (t--) {
solve();
}
}
B
#ifndef IO_HPP
#define IO_HPP 1
#include <array>
#include <cstdint>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
namespace io {
void __read(char& c) { std::cin >> c; }
void __read(std::string& s) { std::cin >> s; }
template <typename T>
void __read_real(T& x) {
std::string s;
__read(s);
x = std::stod(s);
}
template <typename T>
void __read_integer(T& x) {
std::cin >> x;
}
void __read(int& x) { __read_integer(x); }
void __read(unsigned int& x) { __read_integer(x); }
void __read(long& x) { __read_integer(x); }
void __read(unsigned long& x) { __read_integer(x); }
void __read(long long& x) { __read_integer(x); }
void __read(unsigned long long& x) { __read_integer(x); }
void __read(double& x) { __read_real(x); }
void __read(long double& x) { __read_real(x); }
template <class U, class V>
void __read(std::pair<U, V>& p) {
__read(p.first);
__read(p.second);
}
template <size_t N = 0, typename T>
void __read_tuple(T& t) {
if constexpr (N < std::tuple_size<T>::value) {
auto& x = std::get<N>(t);
__read(x);
__read_tuple<N + 1>(t);
}
}
template <class... T>
void __read(std::tuple<T...>& t) {
__read_tuple(t);
}
template <size_t N = 0, typename T>
void __read(std::array<T, N>& a) {
for (auto& x : a) {
__read(x);
}
}
template <class T>
void __read(std::vector<T>& v) {
for (auto& x : v) {
__read(x);
}
}
void read() {}
template <class H, class... T>
void read(H& h, T&... t) {
__read(h), read(t...);
}
void __write(const char c) { std::cout << c; }
void __write(const std::string s) {
for (char c : s) {
__write(c);
}
}
void __write(const char* s) {
size_t len = strlen(s);
for (size_t i = 0; i < len; ++i) {
__write(s[i]);
}
}
template <typename T>
void __write_integer(T x) {
std::cout << x;
}
template <typename T>
void __write_real(T x) {
std::ostringstream oss;
oss << std::fixed << std::setprecision(15) << double(x);
std::string s = oss.str();
__write(s);
}
void __write(int x) { __write_integer(x); }
void __write(unsigned int x) { __write_integer(x); }
void __write(long x) { __write_integer(x); }
void __write(unsigned long x) { __write_integer(x); }
void __write(long long x) { __write_integer(x); }
void __write(unsigned long long x) { __write_integer(x); }
void __write(double x) { __write_real(x); }
void __write(long double x) { __write_real(x); }
template <class U, class V>
void __write(const std::pair<U, V> p) {
__write(p.first);
__write(' ');
__write(p.second);
}
template <size_t N = 0, typename T>
void __write_tuple(const T t) {
if constexpr (N < std::tuple_size<T>::value) {
if constexpr (N > 0) {
__write(' ');
}
const auto x = std::get<N>(t);
__write(x);
__write_tuple<N + 1>(t);
}
}
template <class... T>
void __write(std::tuple<T...> t) {
__write_tuple(t);
}
template <class T, size_t S>
void __write(const std::array<T, S> a) {
auto n = a.size();
for (size_t i = 0; i < n; i++) {
if (i) {
__write(' ');
}
__write(a[i]);
}
}
template <class T>
void __write(const std::vector<T> v) {
auto n = v.size();
for (size_t i = 0; i < n; i++) {
if (i) {
__write(' ');
}
__write(v[i]);
}
}
template <class T>
void __write(const std::set<T> s) {
__write(std::vector<T>{s.cbegin(), s.cend()});
}
template <class K, class V>
void __write(const std::map<K, V> m) {
__write(std::vector<std::pair<K, V>>{m.cbegin(), m.cend()});
}
void write() { __write('\n'); }
template <class Head, class... Tail>
void write(Head&& head, Tail&&... tail) {
__write(head);
if (sizeof...(Tail)) {
__write(' ');
}
write(std::forward<Tail>(tail)...);
}
} // namespace io
#endif // IO_HPP
#ifdef ONLINE_JUDGE
#include <bits/allocator.h>
#pragma GCC optimize("Ofast,unroll-loops,inline")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#endif
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
// using namespace atcoder;
using namespace io;
template <typename T>
using ordered_set =
tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
void solve() {
int n, x;
read(n, x);
vector<int> c(n), a(n);
read(c, a);
int op{};
priority_queue<int> q;
for (int i{}; i < n; ++i) {
x -= c[i];
q.push(c[i]);
while (x < 0) {
++op;
x += q.top();
q.pop();
}
x += a[i];
}
write(op);
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int t;
read(t);
while (t--) {
solve();
}
}
C
#ifndef IO_HPP
#define IO_HPP 1
#include <array>
#include <cstdint>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
namespace io {
void __read(char& c) { std::cin >> c; }
void __read(std::string& s) { std::cin >> s; }
template <typename T>
void __read_real(T& x) {
std::string s;
__read(s);
x = std::stod(s);
}
template <typename T>
void __read_integer(T& x) {
std::cin >> x;
}
void __read(int& x) { __read_integer(x); }
void __read(unsigned int& x) { __read_integer(x); }
void __read(long& x) { __read_integer(x); }
void __read(unsigned long& x) { __read_integer(x); }
void __read(long long& x) { __read_integer(x); }
void __read(unsigned long long& x) { __read_integer(x); }
void __read(double& x) { __read_real(x); }
void __read(long double& x) { __read_real(x); }
template <class U, class V>
void __read(std::pair<U, V>& p) {
__read(p.first);
__read(p.second);
}
template <size_t N = 0, typename T>
void __read_tuple(T& t) {
if constexpr (N < std::tuple_size<T>::value) {
auto& x = std::get<N>(t);
__read(x);
__read_tuple<N + 1>(t);
}
}
template <class... T>
void __read(std::tuple<T...>& t) {
__read_tuple(t);
}
template <size_t N = 0, typename T>
void __read(std::array<T, N>& a) {
for (auto& x : a) {
__read(x);
}
}
template <class T>
void __read(std::vector<T>& v) {
for (auto& x : v) {
__read(x);
}
}
void read() {}
template <class H, class... T>
void read(H& h, T&... t) {
__read(h), read(t...);
}
void __write(const char c) { std::cout << c; }
void __write(const std::string s) {
for (char c : s) {
__write(c);
}
}
void __write(const char* s) {
size_t len = strlen(s);
for (size_t i = 0; i < len; ++i) {
__write(s[i]);
}
}
template <typename T>
void __write_integer(T x) {
std::cout << x;
}
template <typename T>
void __write_real(T x) {
std::ostringstream oss;
oss << std::fixed << std::setprecision(15) << double(x);
std::string s = oss.str();
__write(s);
}
void __write(int x) { __write_integer(x); }
void __write(unsigned int x) { __write_integer(x); }
void __write(long x) { __write_integer(x); }
void __write(unsigned long x) { __write_integer(x); }
void __write(long long x) { __write_integer(x); }
void __write(unsigned long long x) { __write_integer(x); }
void __write(double x) { __write_real(x); }
void __write(long double x) { __write_real(x); }
template <class U, class V>
void __write(const std::pair<U, V> p) {
__write(p.first);
__write(' ');
__write(p.second);
}
template <size_t N = 0, typename T>
void __write_tuple(const T t) {
if constexpr (N < std::tuple_size<T>::value) {
if constexpr (N > 0) {
__write(' ');
}
const auto x = std::get<N>(t);
__write(x);
__write_tuple<N + 1>(t);
}
}
template <class... T>
void __write(std::tuple<T...> t) {
__write_tuple(t);
}
template <class T, size_t S>
void __write(const std::array<T, S> a) {
auto n = a.size();
for (size_t i = 0; i < n; i++) {
if (i) {
__write(' ');
}
__write(a[i]);
}
}
template <class T>
void __write(const std::vector<T> v) {
auto n = v.size();
for (size_t i = 0; i < n; i++) {
if (i) {
__write(' ');
}
__write(v[i]);
}
}
template <class T>
void __write(const std::set<T> s) {
__write(std::vector<T>{s.cbegin(), s.cend()});
}
template <class K, class V>
void __write(const std::map<K, V> m) {
__write(std::vector<std::pair<K, V>>{m.cbegin(), m.cend()});
}
void write() { __write('\n'); }
template <class Head, class... Tail>
void write(Head&& head, Tail&&... tail) {
__write(head);
if (sizeof...(Tail)) {
__write(' ');
}
write(std::forward<Tail>(tail)...);
}
} // namespace io
#endif // IO_HPP
#ifdef ONLINE_JUDGE
#include <bits/allocator.h>
#pragma GCC optimize("Ofast,unroll-loops,inline")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#endif
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
// using namespace atcoder;
using namespace io;
template <typename T>
using ordered_set =
tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
int f(int n, int d) {
const auto k{n - d};
assert(k % (n - k) == 0);
return k / (n - k);
}
void solve() {
int n;
read(n);
int64_t s{};
for (int d{1}; d * d <= n; ++d) {
if (n % d) {
continue;
}
s += f(n, d);
if (n / d != d) {
s += f(n, n / d);
}
}
write(s);
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int t;
read(t);
while (t--) {
solve();
}
}
D
#ifndef ATCODER_INTERNAL_MATH_HPP
#define ATCODER_INTERNAL_MATH_HPP 1
#include <utility>
#ifdef _MSC_VER
#include <intrin.h>
#endif
namespace atcoder {
namespace internal {
// @param m `1 <= m`
// @return x mod m
constexpr long long safe_mod(long long x, long long m) {
x %= m;
if (x < 0) x += m;
return x;
}
// Fast modular multiplication by barrett reduction
// Reference: https://en.wikipedia.org/wiki/Barrett_reduction
// NOTE: reconsider after Ice Lake
struct barrett {
unsigned int _m;
unsigned long long im;
// @param m `1 <= m`
explicit barrett(unsigned int m)
: _m(m), im((unsigned long long)(-1) / m + 1) {}
// @return m
unsigned int umod() const { return _m; }
// @param a `0 <= a < m`
// @param b `0 <= b < m`
// @return `a * b % m`
unsigned int mul(unsigned int a, unsigned int b) const {
// [1] m = 1
// a = b = im = 0, so okay
// [2] m >= 2
// im = ceil(2^64 / m)
// -> im * m = 2^64 + r (0 <= r < m)
// let z = a*b = c*m + d (0 <= c, d < m)
// a*b * im = (c*m + d) * im = c*(im*m) + d*im = c*2^64 + c*r + d*im
// c*r + d*im < m * m + m * im < m * m + 2^64 + m <= 2^64 + m * (m + 1) <
// 2^64 * 2
// ((ab * im) >> 64) == c or c + 1
unsigned long long z = a;
z *= b;
#ifdef _MSC_VER
unsigned long long x;
_umul128(z, im, &x);
#else
unsigned long long x =
(unsigned long long)(((unsigned __int128)(z)*im) >> 64);
#endif
unsigned long long y = x * _m;
return (unsigned int)(z - y + (z < y ? _m : 0));
}
};
// @param n `0 <= n`
// @param m `1 <= m`
// @return `(x ** n) % m`
constexpr long long pow_mod_constexpr(long long x, long long n, int m) {
if (m == 1) return 0;
unsigned int _m = (unsigned int)(m);
unsigned long long r = 1;
unsigned long long y = safe_mod(x, m);
while (n) {
if (n & 1) r = (r * y) % _m;
y = (y * y) % _m;
n >>= 1;
}
return r;
}
// Reference:
// M. Forisek and J. Jancina,
// Fast Primality Testing for Integers That Fit into a Machine Word
// @param n `0 <= n`
constexpr bool is_prime_constexpr(int n) {
if (n <= 1) return false;
if (n == 2 || n == 7 || n == 61) return true;
if (n % 2 == 0) return false;
long long d = n - 1;
while (d % 2 == 0) d /= 2;
constexpr long long bases[3] = {2, 7, 61};
for (long long a : bases) {
long long t = d;
long long y = pow_mod_constexpr(a, t, n);
while (t != n - 1 && y != 1 && y != n - 1) {
y = y * y % n;
t <<= 1;
}
if (y != n - 1 && t % 2 == 0) {
return false;
}
}
return true;
}
template <int n>
constexpr bool is_prime = is_prime_constexpr(n);
// @param b `1 <= b`
// @return pair(g, x) s.t. g = gcd(a, b), xa = g (mod b), 0 <= x < b/g
constexpr std::pair<long long, long long> inv_gcd(long long a, long long b) {
a = safe_mod(a, b);
if (a == 0) return {b, 0};
// Contracts:
// [1] s - m0 * a = 0 (mod b)
// [2] t - m1 * a = 0 (mod b)
// [3] s * |m1| + t * |m0| <= b
long long s = b, t = a;
long long m0 = 0, m1 = 1;
while (t) {
long long u = s / t;
s -= t * u;
m0 -= m1 * u; // |m1 * u| <= |m1| * s <= b
// [3]:
// (s - t * u) * |m1| + t * |m0 - m1 * u|
// <= s * |m1| - t * u * |m1| + t * (|m0| + |m1| * u)
// = s * |m1| + t * |m0| <= b
auto tmp = s;
s = t;
t = tmp;
tmp = m0;
m0 = m1;
m1 = tmp;
}
// by [3]: |m0| <= b/g
// by g != b: |m0| < b/g
if (m0 < 0) m0 += b / s;
return {s, m0};
}
// Compile time primitive root
// @param m must be prime
// @return primitive root (and minimum in now)
constexpr int primitive_root_constexpr(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;
int divs[20] = {};
divs[0] = 2;
int cnt = 1;
int x = (m - 1) / 2;
while (x % 2 == 0) x /= 2;
for (int i = 3; (long long)(i)*i <= x; i += 2) {
if (x % i == 0) {
divs[cnt++] = i;
while (x % i == 0) {
x /= i;
}
}
}
if (x > 1) {
divs[cnt++] = x;
}
for (int g = 2;; g++) {
bool ok = true;
for (int i = 0; i < cnt; i++) {
if (pow_mod_constexpr(g, (m - 1) / divs[i], m) == 1) {
ok = false;
break;
}
}
if (ok) return g;
}
}
template <int m>
constexpr int primitive_root = primitive_root_constexpr(m);
// @param n `n < 2^32`
// @param m `1 <= m < 2^32`
// @return sum_{i=0}^{n-1} floor((ai + b) / m) (mod 2^64)
unsigned long long floor_sum_unsigned(unsigned long long n,
unsigned long long m,
unsigned long long a,
unsigned long long b) {
unsigned long long ans = 0;
while (true) {
if (a >= m) {
ans += n * (n - 1) / 2 * (a / m);
a %= m;
}
if (b >= m) {
ans += n * (b / m);
b %= m;
}
unsigned long long y_max = a * n + b;
if (y_max < m) break;
// y_max < m * (n + 1)
// floor(y_max / m) <= n
n = (unsigned long long)(y_max / m);
b = (unsigned long long)(y_max % m);
std::swap(m, a);
}
return ans;
}
} // namespace internal
} // namespace atcoder
#endif // ATCODER_INTERNAL_MATH_HPP
#ifndef ATCODER_INTERNAL_TYPE_TRAITS_HPP
#define ATCODER_INTERNAL_TYPE_TRAITS_HPP 1
#include <cassert>
#include <numeric>
#include <type_traits>
namespace atcoder {
namespace internal {
#ifndef _MSC_VER
template <class T>
using is_signed_int128 =
typename std::conditional<std::is_same<T, __int128_t>::value ||
std::is_same<T, __int128>::value,
std::true_type, std::false_type>::type;
template <class T>
using is_unsigned_int128 =
typename std::conditional<std::is_same<T, __uint128_t>::value ||
std::is_same<T, unsigned __int128>::value,
std::true_type, std::false_type>::type;
template <class T>
using make_unsigned_int128 =
typename std::conditional<std::is_same<T, __int128_t>::value, __uint128_t,
unsigned __int128>;
template <class T>
using is_integral =
typename std::conditional<std::is_integral<T>::value ||
is_signed_int128<T>::value ||
is_unsigned_int128<T>::value,
std::true_type, std::false_type>::type;
template <class T>
using is_signed_int =
typename std::conditional<(is_integral<T>::value &&
std::is_signed<T>::value) ||
is_signed_int128<T>::value,
std::true_type, std::false_type>::type;
template <class T>
using is_unsigned_int =
typename std::conditional<(is_integral<T>::value &&
std::is_unsigned<T>::value) ||
is_unsigned_int128<T>::value,
std::true_type, std::false_type>::type;
template <class T>
using to_unsigned = typename std::conditional<
is_signed_int128<T>::value, make_unsigned_int128<T>,
typename std::conditional<std::is_signed<T>::value, std::make_unsigned<T>,
std::common_type<T>>::type>::type;
#else
template <class T>
using is_integral = typename std::is_integral<T>;
template <class T>
using is_signed_int =
typename std::conditional<is_integral<T>::value && std::is_signed<T>::value,
std::true_type, std::false_type>::type;
template <class T>
using is_unsigned_int =
typename std::conditional<is_integral<T>::value &&
std::is_unsigned<T>::value,
std::true_type, std::false_type>::type;
template <class T>
using to_unsigned =
typename std::conditional<is_signed_int<T>::value, std::make_unsigned<T>,
std::common_type<T>>::type;
#endif
template <class T>
using is_signed_int_t = std::enable_if_t<is_signed_int<T>::value>;
template <class T>
using is_unsigned_int_t = std::enable_if_t<is_unsigned_int<T>::value>;
template <class T>
using to_unsigned_t = typename to_unsigned<T>::type;
} // namespace internal
} // namespace atcoder
#endif // ATCODER_INTERNAL_TYPE_TRAITS_HPP
#ifndef ATCODER_MODINT_HPP
#define ATCODER_MODINT_HPP 1
#include <cassert>
#include <numeric>
#include <type_traits>
#ifdef _MSC_VER
#include <intrin.h>
#endif
namespace atcoder {
namespace internal {
struct modint_base {};
struct static_modint_base : modint_base {};
template <class T>
using is_modint = std::is_base_of<modint_base, T>;
template <class T>
using is_modint_t = std::enable_if_t<is_modint<T>::value>;
} // namespace internal
template <int m, std::enable_if_t<(1 <= m)>* = nullptr>
struct static_modint : internal::static_modint_base {
using mint = static_modint;
public:
static constexpr int mod() { return m; }
static mint raw(int v) {
mint x;
x._v = v;
return x;
}
static_modint() : _v(0) {}
template <class T, internal::is_signed_int_t<T>* = nullptr>
static_modint(T v) {
long long x = (long long)(v % (long long)(umod()));
if (x < 0) x += umod();
_v = (unsigned int)(x);
}
template <class T, internal::is_unsigned_int_t<T>* = nullptr>
static_modint(T v) {
_v = (unsigned int)(v % umod());
}
unsigned int val() const { return _v; }
mint& operator++() {
_v++;
if (_v == umod()) _v = 0;
return *this;
}
mint& operator--() {
if (_v == 0) _v = umod();
_v--;
return *this;
}
mint operator++(int) {
mint result = *this;
++*this;
return result;
}
mint operator--(int) {
mint result = *this;
--*this;
return result;
}
mint& operator+=(const mint& rhs) {
_v += rhs._v;
if (_v >= umod()) _v -= umod();
return *this;
}
mint& operator-=(const mint& rhs) {
_v -= rhs._v;
if (_v >= umod()) _v += umod();
return *this;
}
mint& operator*=(const mint& rhs) {
unsigned long long z = _v;
z *= rhs._v;
_v = (unsigned int)(z % umod());
return *this;
}
mint& operator/=(const mint& rhs) { return *this = *this * rhs.inv(); }
mint operator+() const { return *this; }
mint operator-() const { return mint() - *this; }
mint pow(long long n) const {
assert(0 <= n);
mint x = *this, r = 1;
while (n) {
if (n & 1) r *= x;
x *= x;
n >>= 1;
}
return r;
}
mint inv() const {
if (prime) {
assert(_v);
return pow(umod() - 2);
} else {
auto eg = internal::inv_gcd(_v, m);
assert(eg.first == 1);
return eg.second;
}
}
friend mint operator+(const mint& lhs, const mint& rhs) {
return mint(lhs) += rhs;
}
friend mint operator-(const mint& lhs, const mint& rhs) {
return mint(lhs) -= rhs;
}
friend mint operator*(const mint& lhs, const mint& rhs) {
return mint(lhs) *= rhs;
}
friend mint operator/(const mint& lhs, const mint& rhs) {
return mint(lhs) /= rhs;
}
friend bool operator==(const mint& lhs, const mint& rhs) {
return lhs._v == rhs._v;
}
friend bool operator!=(const mint& lhs, const mint& rhs) {
return lhs._v != rhs._v;
}
private:
unsigned int _v;
static constexpr unsigned int umod() { return m; }
static constexpr bool prime = internal::is_prime<m>;
};
template <int id>
struct dynamic_modint : internal::modint_base {
using mint = dynamic_modint;
public:
static int mod() { return (int)(bt.umod()); }
static void set_mod(int m) {
assert(1 <= m);
bt = internal::barrett(m);
}
static mint raw(int v) {
mint x;
x._v = v;
return x;
}
dynamic_modint() : _v(0) {}
template <class T, internal::is_signed_int_t<T>* = nullptr>
dynamic_modint(T v) {
long long x = (long long)(v % (long long)(mod()));
if (x < 0) x += mod();
_v = (unsigned int)(x);
}
template <class T, internal::is_unsigned_int_t<T>* = nullptr>
dynamic_modint(T v) {
_v = (unsigned int)(v % mod());
}
unsigned int val() const { return _v; }
mint& operator++() {
_v++;
if (_v == umod()) _v = 0;
return *this;
}
mint& operator--() {
if (_v == 0) _v = umod();
_v--;
return *this;
}
mint operator++(int) {
mint result = *this;
++*this;
return result;
}
mint operator--(int) {
mint result = *this;
--*this;
return result;
}
mint& operator+=(const mint& rhs) {
_v += rhs._v;
if (_v >= umod()) _v -= umod();
return *this;
}
mint& operator-=(const mint& rhs) {
_v += mod() - rhs._v;
if (_v >= umod()) _v -= umod();
return *this;
}
mint& operator*=(const mint& rhs) {
_v = bt.mul(_v, rhs._v);
return *this;
}
mint& operator/=(const mint& rhs) { return *this = *this * rhs.inv(); }
mint operator+() const { return *this; }
mint operator-() const { return mint() - *this; }
mint pow(long long n) const {
assert(0 <= n);
mint x = *this, r = 1;
while (n) {
if (n & 1) r *= x;
x *= x;
n >>= 1;
}
return r;
}
mint inv() const {
auto eg = internal::inv_gcd(_v, mod());
assert(eg.first == 1);
return eg.second;
}
friend mint operator+(const mint& lhs, const mint& rhs) {
return mint(lhs) += rhs;
}
friend mint operator-(const mint& lhs, const mint& rhs) {
return mint(lhs) -= rhs;
}
friend mint operator*(const mint& lhs, const mint& rhs) {
return mint(lhs) *= rhs;
}
friend mint operator/(const mint& lhs, const mint& rhs) {
return mint(lhs) /= rhs;
}
friend bool operator==(const mint& lhs, const mint& rhs) {
return lhs._v == rhs._v;
}
friend bool operator!=(const mint& lhs, const mint& rhs) {
return lhs._v != rhs._v;
}
private:
unsigned int _v;
static internal::barrett bt;
static unsigned int umod() { return bt.umod(); }
};
template <int id>
internal::barrett dynamic_modint<id>::bt(998244353);
using modint998244353 = static_modint<998244353>;
using modint1000000007 = static_modint<1000000007>;
using modint = dynamic_modint<-1>;
namespace internal {
template <class T>
using is_static_modint = std::is_base_of<internal::static_modint_base, T>;
template <class T>
using is_static_modint_t = std::enable_if_t<is_static_modint<T>::value>;
template <class>
struct is_dynamic_modint : public std::false_type {};
template <int id>
struct is_dynamic_modint<dynamic_modint<id>> : public std::true_type {};
template <class T>
using is_dynamic_modint_t = std::enable_if_t<is_dynamic_modint<T>::value>;
} // namespace internal
} // namespace atcoder
#endif // ATCODER_MODINT_HPP
#ifndef IO_HPP
#define IO_HPP 1
#include <array>
#include <cstdint>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
namespace io {
void __read(char& c) { std::cin >> c; }
void __read(std::string& s) { std::cin >> s; }
template <typename T>
void __read_real(T& x) {
std::string s;
__read(s);
x = std::stod(s);
}
template <typename T>
void __read_integer(T& x) {
std::cin >> x;
}
void __read(int& x) { __read_integer(x); }
void __read(unsigned int& x) { __read_integer(x); }
void __read(long& x) { __read_integer(x); }
void __read(unsigned long& x) { __read_integer(x); }
void __read(long long& x) { __read_integer(x); }
void __read(unsigned long long& x) { __read_integer(x); }
void __read(double& x) { __read_real(x); }
void __read(long double& x) { __read_real(x); }
template <class U, class V>
void __read(std::pair<U, V>& p) {
__read(p.first);
__read(p.second);
}
template <size_t N = 0, typename T>
void __read_tuple(T& t) {
if constexpr (N < std::tuple_size<T>::value) {
auto& x = std::get<N>(t);
__read(x);
__read_tuple<N + 1>(t);
}
}
template <class... T>
void __read(std::tuple<T...>& t) {
__read_tuple(t);
}
template <size_t N = 0, typename T>
void __read(std::array<T, N>& a) {
for (auto& x : a) {
__read(x);
}
}
template <class T>
void __read(std::vector<T>& v) {
for (auto& x : v) {
__read(x);
}
}
void read() {}
template <class H, class... T>
void read(H& h, T&... t) {
__read(h), read(t...);
}
void __write(const char c) { std::cout << c; }
void __write(const std::string s) {
for (char c : s) {
__write(c);
}
}
void __write(const char* s) {
size_t len = strlen(s);
for (size_t i = 0; i < len; ++i) {
__write(s[i]);
}
}
template <typename T>
void __write_integer(T x) {
std::cout << x;
}
template <typename T>
void __write_real(T x) {
std::ostringstream oss;
oss << std::fixed << std::setprecision(15) << double(x);
std::string s = oss.str();
__write(s);
}
void __write(int x) { __write_integer(x); }
void __write(unsigned int x) { __write_integer(x); }
void __write(long x) { __write_integer(x); }
void __write(unsigned long x) { __write_integer(x); }
void __write(long long x) { __write_integer(x); }
void __write(unsigned long long x) { __write_integer(x); }
void __write(double x) { __write_real(x); }
void __write(long double x) { __write_real(x); }
template <class U, class V>
void __write(const std::pair<U, V> p) {
__write(p.first);
__write(' ');
__write(p.second);
}
template <size_t N = 0, typename T>
void __write_tuple(const T t) {
if constexpr (N < std::tuple_size<T>::value) {
if constexpr (N > 0) {
__write(' ');
}
const auto x = std::get<N>(t);
__write(x);
__write_tuple<N + 1>(t);
}
}
template <class... T>
void __write(std::tuple<T...> t) {
__write_tuple(t);
}
template <class T, size_t S>
void __write(const std::array<T, S> a) {
auto n = a.size();
for (size_t i = 0; i < n; i++) {
if (i) {
__write(' ');
}
__write(a[i]);
}
}
template <class T>
void __write(const std::vector<T> v) {
auto n = v.size();
for (size_t i = 0; i < n; i++) {
if (i) {
__write(' ');
}
__write(v[i]);
}
}
template <class T>
void __write(const std::set<T> s) {
__write(std::vector<T>{s.cbegin(), s.cend()});
}
template <class K, class V>
void __write(const std::map<K, V> m) {
__write(std::vector<std::pair<K, V>>{m.cbegin(), m.cend()});
}
void write() { __write('\n'); }
template <class Head, class... Tail>
void write(Head&& head, Tail&&... tail) {
__write(head);
if (sizeof...(Tail)) {
__write(' ');
}
write(std::forward<Tail>(tail)...);
}
} // namespace io
#endif // IO_HPP
#ifdef ONLINE_JUDGE
#include <bits/allocator.h>
#pragma GCC optimize("Ofast,unroll-loops,inline")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#endif
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
using namespace atcoder;
using namespace io;
using mint = modint998244353;
template <typename T>
using ordered_set =
tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
constexpr auto mx{1'000'000};
array<mint, mx + 1> factorial, derangements;
void precompute() {
derangements[0] = factorial[0] = 1;
for (int i{1}; i <= mx; ++i) {
factorial[i] = i * factorial[i - 1];
}
for (int i{2}; i <= mx; ++i) {
derangements[i] = (i - 1) * (derangements[i - 1] + derangements[i - 2]);
}
}
void solve() {
int n;
read(n);
if (n & 1) {
write((factorial[n] * derangements[n]).val());
} else {
write(1);
}
}
int main() {
cin.tie(0)->sync_with_stdio(0);
precompute();
int t;
read(t);
while (t--) {
solve();
}
}
E
#ifndef ATCODER_INTERNAL_MATH_HPP
#define ATCODER_INTERNAL_MATH_HPP 1
#include <utility>
#ifdef _MSC_VER
#include <intrin.h>
#endif
namespace atcoder {
namespace internal {
// @param m `1 <= m`
// @return x mod m
constexpr long long safe_mod(long long x, long long m) {
x %= m;
if (x < 0) x += m;
return x;
}
// Fast modular multiplication by barrett reduction
// Reference: https://en.wikipedia.org/wiki/Barrett_reduction
// NOTE: reconsider after Ice Lake
struct barrett {
unsigned int _m;
unsigned long long im;
// @param m `1 <= m`
explicit barrett(unsigned int m)
: _m(m), im((unsigned long long)(-1) / m + 1) {}
// @return m
unsigned int umod() const { return _m; }
// @param a `0 <= a < m`
// @param b `0 <= b < m`
// @return `a * b % m`
unsigned int mul(unsigned int a, unsigned int b) const {
// [1] m = 1
// a = b = im = 0, so okay
// [2] m >= 2
// im = ceil(2^64 / m)
// -> im * m = 2^64 + r (0 <= r < m)
// let z = a*b = c*m + d (0 <= c, d < m)
// a*b * im = (c*m + d) * im = c*(im*m) + d*im = c*2^64 + c*r + d*im
// c*r + d*im < m * m + m * im < m * m + 2^64 + m <= 2^64 + m * (m + 1) <
// 2^64 * 2
// ((ab * im) >> 64) == c or c + 1
unsigned long long z = a;
z *= b;
#ifdef _MSC_VER
unsigned long long x;
_umul128(z, im, &x);
#else
unsigned long long x =
(unsigned long long)(((unsigned __int128)(z)*im) >> 64);
#endif
unsigned long long y = x * _m;
return (unsigned int)(z - y + (z < y ? _m : 0));
}
};
// @param n `0 <= n`
// @param m `1 <= m`
// @return `(x ** n) % m`
constexpr long long pow_mod_constexpr(long long x, long long n, int m) {
if (m == 1) return 0;
unsigned int _m = (unsigned int)(m);
unsigned long long r = 1;
unsigned long long y = safe_mod(x, m);
while (n) {
if (n & 1) r = (r * y) % _m;
y = (y * y) % _m;
n >>= 1;
}
return r;
}
// Reference:
// M. Forisek and J. Jancina,
// Fast Primality Testing for Integers That Fit into a Machine Word
// @param n `0 <= n`
constexpr bool is_prime_constexpr(int n) {
if (n <= 1) return false;
if (n == 2 || n == 7 || n == 61) return true;
if (n % 2 == 0) return false;
long long d = n - 1;
while (d % 2 == 0) d /= 2;
constexpr long long bases[3] = {2, 7, 61};
for (long long a : bases) {
long long t = d;
long long y = pow_mod_constexpr(a, t, n);
while (t != n - 1 && y != 1 && y != n - 1) {
y = y * y % n;
t <<= 1;
}
if (y != n - 1 && t % 2 == 0) {
return false;
}
}
return true;
}
template <int n>
constexpr bool is_prime = is_prime_constexpr(n);
// @param b `1 <= b`
// @return pair(g, x) s.t. g = gcd(a, b), xa = g (mod b), 0 <= x < b/g
constexpr std::pair<long long, long long> inv_gcd(long long a, long long b) {
a = safe_mod(a, b);
if (a == 0) return {b, 0};
// Contracts:
// [1] s - m0 * a = 0 (mod b)
// [2] t - m1 * a = 0 (mod b)
// [3] s * |m1| + t * |m0| <= b
long long s = b, t = a;
long long m0 = 0, m1 = 1;
while (t) {
long long u = s / t;
s -= t * u;
m0 -= m1 * u; // |m1 * u| <= |m1| * s <= b
// [3]:
// (s - t * u) * |m1| + t * |m0 - m1 * u|
// <= s * |m1| - t * u * |m1| + t * (|m0| + |m1| * u)
// = s * |m1| + t * |m0| <= b
auto tmp = s;
s = t;
t = tmp;
tmp = m0;
m0 = m1;
m1 = tmp;
}
// by [3]: |m0| <= b/g
// by g != b: |m0| < b/g
if (m0 < 0) m0 += b / s;
return {s, m0};
}
// Compile time primitive root
// @param m must be prime
// @return primitive root (and minimum in now)
constexpr int primitive_root_constexpr(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;
int divs[20] = {};
divs[0] = 2;
int cnt = 1;
int x = (m - 1) / 2;
while (x % 2 == 0) x /= 2;
for (int i = 3; (long long)(i)*i <= x; i += 2) {
if (x % i == 0) {
divs[cnt++] = i;
while (x % i == 0) {
x /= i;
}
}
}
if (x > 1) {
divs[cnt++] = x;
}
for (int g = 2;; g++) {
bool ok = true;
for (int i = 0; i < cnt; i++) {
if (pow_mod_constexpr(g, (m - 1) / divs[i], m) == 1) {
ok = false;
break;
}
}
if (ok) return g;
}
}
template <int m>
constexpr int primitive_root = primitive_root_constexpr(m);
// @param n `n < 2^32`
// @param m `1 <= m < 2^32`
// @return sum_{i=0}^{n-1} floor((ai + b) / m) (mod 2^64)
unsigned long long floor_sum_unsigned(unsigned long long n,
unsigned long long m,
unsigned long long a,
unsigned long long b) {
unsigned long long ans = 0;
while (true) {
if (a >= m) {
ans += n * (n - 1) / 2 * (a / m);
a %= m;
}
if (b >= m) {
ans += n * (b / m);
b %= m;
}
unsigned long long y_max = a * n + b;
if (y_max < m) break;
// y_max < m * (n + 1)
// floor(y_max / m) <= n
n = (unsigned long long)(y_max / m);
b = (unsigned long long)(y_max % m);
std::swap(m, a);
}
return ans;
}
} // namespace internal
} // namespace atcoder
#endif // ATCODER_INTERNAL_MATH_HPP
#ifndef ATCODER_INTERNAL_TYPE_TRAITS_HPP
#define ATCODER_INTERNAL_TYPE_TRAITS_HPP 1
#include <cassert>
#include <numeric>
#include <type_traits>
namespace atcoder {
namespace internal {
#ifndef _MSC_VER
template <class T>
using is_signed_int128 =
typename std::conditional<std::is_same<T, __int128_t>::value ||
std::is_same<T, __int128>::value,
std::true_type, std::false_type>::type;
template <class T>
using is_unsigned_int128 =
typename std::conditional<std::is_same<T, __uint128_t>::value ||
std::is_same<T, unsigned __int128>::value,
std::true_type, std::false_type>::type;
template <class T>
using make_unsigned_int128 =
typename std::conditional<std::is_same<T, __int128_t>::value, __uint128_t,
unsigned __int128>;
template <class T>
using is_integral =
typename std::conditional<std::is_integral<T>::value ||
is_signed_int128<T>::value ||
is_unsigned_int128<T>::value,
std::true_type, std::false_type>::type;
template <class T>
using is_signed_int =
typename std::conditional<(is_integral<T>::value &&
std::is_signed<T>::value) ||
is_signed_int128<T>::value,
std::true_type, std::false_type>::type;
template <class T>
using is_unsigned_int =
typename std::conditional<(is_integral<T>::value &&
std::is_unsigned<T>::value) ||
is_unsigned_int128<T>::value,
std::true_type, std::false_type>::type;
template <class T>
using to_unsigned = typename std::conditional<
is_signed_int128<T>::value, make_unsigned_int128<T>,
typename std::conditional<std::is_signed<T>::value, std::make_unsigned<T>,
std::common_type<T>>::type>::type;
#else
template <class T>
using is_integral = typename std::is_integral<T>;
template <class T>
using is_signed_int =
typename std::conditional<is_integral<T>::value && std::is_signed<T>::value,
std::true_type, std::false_type>::type;
template <class T>
using is_unsigned_int =
typename std::conditional<is_integral<T>::value &&
std::is_unsigned<T>::value,
std::true_type, std::false_type>::type;
template <class T>
using to_unsigned =
typename std::conditional<is_signed_int<T>::value, std::make_unsigned<T>,
std::common_type<T>>::type;
#endif
template <class T>
using is_signed_int_t = std::enable_if_t<is_signed_int<T>::value>;
template <class T>
using is_unsigned_int_t = std::enable_if_t<is_unsigned_int<T>::value>;
template <class T>
using to_unsigned_t = typename to_unsigned<T>::type;
} // namespace internal
} // namespace atcoder
#endif // ATCODER_INTERNAL_TYPE_TRAITS_HPP
#ifndef ATCODER_MODINT_HPP
#define ATCODER_MODINT_HPP 1
#include <cassert>
#include <numeric>
#include <type_traits>
#ifdef _MSC_VER
#include <intrin.h>
#endif
namespace atcoder {
namespace internal {
struct modint_base {};
struct static_modint_base : modint_base {};
template <class T>
using is_modint = std::is_base_of<modint_base, T>;
template <class T>
using is_modint_t = std::enable_if_t<is_modint<T>::value>;
} // namespace internal
template <int m, std::enable_if_t<(1 <= m)>* = nullptr>
struct static_modint : internal::static_modint_base {
using mint = static_modint;
public:
static constexpr int mod() { return m; }
static mint raw(int v) {
mint x;
x._v = v;
return x;
}
static_modint() : _v(0) {}
template <class T, internal::is_signed_int_t<T>* = nullptr>
static_modint(T v) {
long long x = (long long)(v % (long long)(umod()));
if (x < 0) x += umod();
_v = (unsigned int)(x);
}
template <class T, internal::is_unsigned_int_t<T>* = nullptr>
static_modint(T v) {
_v = (unsigned int)(v % umod());
}
unsigned int val() const { return _v; }
mint& operator++() {
_v++;
if (_v == umod()) _v = 0;
return *this;
}
mint& operator--() {
if (_v == 0) _v = umod();
_v--;
return *this;
}
mint operator++(int) {
mint result = *this;
++*this;
return result;
}
mint operator--(int) {
mint result = *this;
--*this;
return result;
}
mint& operator+=(const mint& rhs) {
_v += rhs._v;
if (_v >= umod()) _v -= umod();
return *this;
}
mint& operator-=(const mint& rhs) {
_v -= rhs._v;
if (_v >= umod()) _v += umod();
return *this;
}
mint& operator*=(const mint& rhs) {
unsigned long long z = _v;
z *= rhs._v;
_v = (unsigned int)(z % umod());
return *this;
}
mint& operator/=(const mint& rhs) { return *this = *this * rhs.inv(); }
mint operator+() const { return *this; }
mint operator-() const { return mint() - *this; }
mint pow(long long n) const {
assert(0 <= n);
mint x = *this, r = 1;
while (n) {
if (n & 1) r *= x;
x *= x;
n >>= 1;
}
return r;
}
mint inv() const {
if (prime) {
assert(_v);
return pow(umod() - 2);
} else {
auto eg = internal::inv_gcd(_v, m);
assert(eg.first == 1);
return eg.second;
}
}
friend mint operator+(const mint& lhs, const mint& rhs) {
return mint(lhs) += rhs;
}
friend mint operator-(const mint& lhs, const mint& rhs) {
return mint(lhs) -= rhs;
}
friend mint operator*(const mint& lhs, const mint& rhs) {
return mint(lhs) *= rhs;
}
friend mint operator/(const mint& lhs, const mint& rhs) {
return mint(lhs) /= rhs;
}
friend bool operator==(const mint& lhs, const mint& rhs) {
return lhs._v == rhs._v;
}
friend bool operator!=(const mint& lhs, const mint& rhs) {
return lhs._v != rhs._v;
}
private:
unsigned int _v;
static constexpr unsigned int umod() { return m; }
static constexpr bool prime = internal::is_prime<m>;
};
template <int id>
struct dynamic_modint : internal::modint_base {
using mint = dynamic_modint;
public:
static int mod() { return (int)(bt.umod()); }
static void set_mod(int m) {
assert(1 <= m);
bt = internal::barrett(m);
}
static mint raw(int v) {
mint x;
x._v = v;
return x;
}
dynamic_modint() : _v(0) {}
template <class T, internal::is_signed_int_t<T>* = nullptr>
dynamic_modint(T v) {
long long x = (long long)(v % (long long)(mod()));
if (x < 0) x += mod();
_v = (unsigned int)(x);
}
template <class T, internal::is_unsigned_int_t<T>* = nullptr>
dynamic_modint(T v) {
_v = (unsigned int)(v % mod());
}
unsigned int val() const { return _v; }
mint& operator++() {
_v++;
if (_v == umod()) _v = 0;
return *this;
}
mint& operator--() {
if (_v == 0) _v = umod();
_v--;
return *this;
}
mint operator++(int) {
mint result = *this;
++*this;
return result;
}
mint operator--(int) {
mint result = *this;
--*this;
return result;
}
mint& operator+=(const mint& rhs) {
_v += rhs._v;
if (_v >= umod()) _v -= umod();
return *this;
}
mint& operator-=(const mint& rhs) {
_v += mod() - rhs._v;
if (_v >= umod()) _v -= umod();
return *this;
}
mint& operator*=(const mint& rhs) {
_v = bt.mul(_v, rhs._v);
return *this;
}
mint& operator/=(const mint& rhs) { return *this = *this * rhs.inv(); }
mint operator+() const { return *this; }
mint operator-() const { return mint() - *this; }
mint pow(long long n) const {
assert(0 <= n);
mint x = *this, r = 1;
while (n) {
if (n & 1) r *= x;
x *= x;
n >>= 1;
}
return r;
}
mint inv() const {
auto eg = internal::inv_gcd(_v, mod());
assert(eg.first == 1);
return eg.second;
}
friend mint operator+(const mint& lhs, const mint& rhs) {
return mint(lhs) += rhs;
}
friend mint operator-(const mint& lhs, const mint& rhs) {
return mint(lhs) -= rhs;
}
friend mint operator*(const mint& lhs, const mint& rhs) {
return mint(lhs) *= rhs;
}
friend mint operator/(const mint& lhs, const mint& rhs) {
return mint(lhs) /= rhs;
}
friend bool operator==(const mint& lhs, const mint& rhs) {
return lhs._v == rhs._v;
}
friend bool operator!=(const mint& lhs, const mint& rhs) {
return lhs._v != rhs._v;
}
private:
unsigned int _v;
static internal::barrett bt;
static unsigned int umod() { return bt.umod(); }
};
template <int id>
internal::barrett dynamic_modint<id>::bt(998244353);
using modint998244353 = static_modint<998244353>;
using modint1000000007 = static_modint<1000000007>;
using modint = dynamic_modint<-1>;
namespace internal {
template <class T>
using is_static_modint = std::is_base_of<internal::static_modint_base, T>;
template <class T>
using is_static_modint_t = std::enable_if_t<is_static_modint<T>::value>;
template <class>
struct is_dynamic_modint : public std::false_type {};
template <int id>
struct is_dynamic_modint<dynamic_modint<id>> : public std::true_type {};
template <class T>
using is_dynamic_modint_t = std::enable_if_t<is_dynamic_modint<T>::value>;
} // namespace internal
} // namespace atcoder
#endif // ATCODER_MODINT_HPP
#ifndef IO_HPP
#define IO_HPP 1
#include <array>
#include <cstdint>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
namespace io {
void __read(char& c) { std::cin >> c; }
void __read(std::string& s) { std::cin >> s; }
template <typename T>
void __read_real(T& x) {
std::string s;
__read(s);
x = std::stod(s);
}
template <typename T>
void __read_integer(T& x) {
std::cin >> x;
}
void __read(int& x) { __read_integer(x); }
void __read(unsigned int& x) { __read_integer(x); }
void __read(long& x) { __read_integer(x); }
void __read(unsigned long& x) { __read_integer(x); }
void __read(long long& x) { __read_integer(x); }
void __read(unsigned long long& x) { __read_integer(x); }
void __read(double& x) { __read_real(x); }
void __read(long double& x) { __read_real(x); }
template <class U, class V>
void __read(std::pair<U, V>& p) {
__read(p.first);
__read(p.second);
}
template <size_t N = 0, typename T>
void __read_tuple(T& t) {
if constexpr (N < std::tuple_size<T>::value) {
auto& x = std::get<N>(t);
__read(x);
__read_tuple<N + 1>(t);
}
}
template <class... T>
void __read(std::tuple<T...>& t) {
__read_tuple(t);
}
template <size_t N = 0, typename T>
void __read(std::array<T, N>& a) {
for (auto& x : a) {
__read(x);
}
}
template <class T>
void __read(std::vector<T>& v) {
for (auto& x : v) {
__read(x);
}
}
void read() {}
template <class H, class... T>
void read(H& h, T&... t) {
__read(h), read(t...);
}
void __write(const char c) { std::cout << c; }
void __write(const std::string s) {
for (char c : s) {
__write(c);
}
}
void __write(const char* s) {
size_t len = strlen(s);
for (size_t i = 0; i < len; ++i) {
__write(s[i]);
}
}
template <typename T>
void __write_integer(T x) {
std::cout << x;
}
template <typename T>
void __write_real(T x) {
std::ostringstream oss;
oss << std::fixed << std::setprecision(15) << double(x);
std::string s = oss.str();
__write(s);
}
void __write(int x) { __write_integer(x); }
void __write(unsigned int x) { __write_integer(x); }
void __write(long x) { __write_integer(x); }
void __write(unsigned long x) { __write_integer(x); }
void __write(long long x) { __write_integer(x); }
void __write(unsigned long long x) { __write_integer(x); }
void __write(double x) { __write_real(x); }
void __write(long double x) { __write_real(x); }
template <class U, class V>
void __write(const std::pair<U, V> p) {
__write(p.first);
__write(' ');
__write(p.second);
}
template <size_t N = 0, typename T>
void __write_tuple(const T t) {
if constexpr (N < std::tuple_size<T>::value) {
if constexpr (N > 0) {
__write(' ');
}
const auto x = std::get<N>(t);
__write(x);
__write_tuple<N + 1>(t);
}
}
template <class... T>
void __write(std::tuple<T...> t) {
__write_tuple(t);
}
template <class T, size_t S>
void __write(const std::array<T, S> a) {
auto n = a.size();
for (size_t i = 0; i < n; i++) {
if (i) {
__write(' ');
}
__write(a[i]);
}
}
template <class T>
void __write(const std::vector<T> v) {
auto n = v.size();
for (size_t i = 0; i < n; i++) {
if (i) {
__write(' ');
}
__write(v[i]);
}
}
template <class T>
void __write(const std::set<T> s) {
__write(std::vector<T>{s.cbegin(), s.cend()});
}
template <class K, class V>
void __write(const std::map<K, V> m) {
__write(std::vector<std::pair<K, V>>{m.cbegin(), m.cend()});
}
void write() { __write('\n'); }
template <class Head, class... Tail>
void write(Head&& head, Tail&&... tail) {
__write(head);
if (sizeof...(Tail)) {
__write(' ');
}
write(std::forward<Tail>(tail)...);
}
} // namespace io
#endif // IO_HPP
#ifdef ONLINE_JUDGE
#include <bits/allocator.h>
#pragma GCC optimize("Ofast,unroll-loops,inline")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#endif
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
using namespace atcoder;
using namespace io;
using mint = modint1000000007;
template <typename T>
using ordered_set =
tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
constexpr auto k{8};
constexpr array<int, k> p{{2, 3, 5, 7, 11, 13, 17, 19}};
void solve() {
int n;
read(n);
vector<int> a(n);
read(a);
vector<mint> dp(1 << k);
dp[0] = 1;
mint total{};
for (int i{}; i < n; ++i) {
for (int j{}; j < k; ++j) {
int e{};
while (a[i] % p[j] == 0) {
a[i] /= p[j];
++e;
}
if (!e) {
continue;
}
for (int m{}; m < (1 << k); ++m) {
if ((m >> j) & 1) {
dp[m] += dp[m ^ (1 << j)] * e;
}
}
}
++dp[0];
for (int m{}; m < (1 << k); ++m) {
total += dp[m];
}
}
total -= n;
write(total.val());
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int t;
read(t);
while (t--) {
solve();
}
}
vietnamchess69
A
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
ll n;
cin >> n;
cout << n << "\n";
}
return 0;
}
B
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll NEG = (ll)-9e18;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
int n;
ll x;
cin >> n >> x;
vector<ll> c(n+1), a(n+1);
for (int i = 1; i <= n; i++) cin >> c[i];
for (int i = 1; i <= n; i++) cin >> a[i];
vector<ll> dp(n+1, NEG), ndp(n+1, NEG);
dp[0] = x;
for (int i = 1; i <= n; i++) {
for (int k = 0; k <= n; k++) ndp[k] = NEG;
for (int k = 0; k <= i; k++) {
if (k <= i - 1) {
ll prev = dp[k];
if (prev >= c[i]) {
ll val = prev - c[i] + a[i];
ndp[k] = max(ndp[k], val);
}
}
if (k >= 1) {
ll prev = dp[k - 1];
if (prev >= 0) {
ll val = prev + a[i];
ndp[k] = max(ndp[k], val);
}
}
}
dp.swap(ndp);
}
int ans = n;
for (int k = 0; k <= n; k++) {
if (dp[k] >= 0) {
ans = k;
break;
}
}
cout << ans << "\n";
}
return 0;
}
C
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
int tc;
cin >> tc;
const int MP = 31623;
vector<int> pr;
vector<bool> isp(MP+1, true);
isp[0] = isp[1] = false;
for (int i = 2; i * i <= MP; i++) {
if (isp[i]) {
for (int j = i * i; j <= MP; j += i)
isp[j] = false;
}
}
for (int i = 2; i <= MP; i++) {
if (isp[i]) pr.push_back(i);
}
while (tc--) {
ll n;
cin >> n;
ll m = n;
vector<pair<ll,int>> f;
for (int p : pr) {
if (1LL * p * p > m) break;
if (m % p == 0) {
int e = 0;
while (m % p == 0) {
m /= p;
e++;
}
f.emplace_back(p, e);
}
}
if (m > 1) f.emplace_back(m, 1);
ll s = 1, d = 1;
for (auto &pe : f) {
ll p = pe.first;
int e = pe.second;
ll pw = 1;
for (int i = 0; i <= e; i++) pw *= p;
ll sp = (pw - 1) / (p - 1);
s *= sp;
d *= (e + 1);
}
cout << (s - d) << '\n';
}
return 0;
}
D
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 998244353;
int add(ll a, ll b){ a+=b; if(a>=MOD) a-=MOD; return a; }
int mul(ll a, ll b){ return (int)( (a*b) % MOD ); }
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
vector<int> ns(t);
int mx = 0;
for(int i = 0; i < t; i++){
cin >> ns[i];
mx = max(mx, ns[i]);
}
vector<int> fac(mx+1), der(mx+1);
fac[0] = 1;
for(int i = 1; i <= mx; i++){
fac[i] = mul(fac[i-1], i);
}
der[0] = 1;
if(mx >= 1) der[1] = 0;
for(int i = 2; i <= mx; i++){
der[i] = mul(i-1, add(der[i-1], der[i-2]));
}
for(int n: ns){
if(n % 2 == 0){
cout << 1 << "\n";
} else {
cout << mul(fac[n], der[n]) << "\n";
}
}
return 0;
}
E
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int M = 1000000007;
ll pw(ll a, ll b) {
ll r = 1;
while (b) {
if (b & 1) r = r * a % M;
a = a * a % M;
b >>= 1;
}
return r;
}
int add(int a, int b) { a += b; if (a >= M) a -= M; return a; }
int mul(ll a, ll b) { return int(a * b % M); }
int eV[21][8];
int lsb[1<<8];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int p[8] = {2,3,5,7,11,13,17,19};
for (int x = 1; x <= 20; x++) {
for (int j = 0; j < 8; j++) {
int t = x;
eV[x][j] = 0;
while (t % p[j] == 0) {
eV[x][j]++;
t /= p[j];
}
}
}
for (int m = 1; m < (1<<8); m++) lsb[m] = __builtin_ctz(m);
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
static int C[1<<8];
C[0] = 1;
for (int m = 1; m < (1<<8); m++) C[m] = 0;
ll ans = 0;
ll E[8] = {0};
static int D[1<<8], P[1<<8];
for (int i = 0; i < n; i++) {
for (int j = 0; j < 8; j++) {
E[j] = (E[j] + eV[a[i]][j]) % M;
}
int A[8], iA[8];
for (int j = 0; j < 8; j++) {
A[j] = int((E[j] + 1) % M);
iA[j] = int(pw(A[j], M-2));
}
ll t0 = 1;
for (int j = 0; j < 8; j++) t0 = t0 * A[j] % M;
D[0] = int(t0);
for (int m = 1; m < (1<<8); m++) {
int b = lsb[m];
D[m] = mul(D[m ^ (1<<b)], iA[b]);
}
ll Sr = 0;
for (int m = 0; m < (1<<8); m++) {
int sgn = (__builtin_parity(m) ? M-1 : 1);
Sr = (Sr + (ll)sgn * D[m] % M * C[m]) % M;
}
ans = (ans + Sr) % M;
P[0] = 1;
for (int m = 1; m < (1<<8); m++) {
int b = lsb[m];
P[m] = mul(P[m ^ (1<<b)], E[b]);
}
for (int m = 0; m < (1<<8); m++) C[m] = add(C[m], P[m]);
}
cout << ans << '\n';
}
return 0;
}
9ovem
A
#include <bits/stdc++.h>
using namespace std;
#define fastio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int main(){
fastio
int t;
cin>>t;
while(t--){
long long n;
cin>>n;
cout<<n<<"\n";
}
return 0;
}
B
#include <bits/stdc++.h>
using namespace std;
#define fastio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int main() {
fastio;
int t;
cin >> t;
while (t--) {
int n, x;
cin >> n >> x;
vector<int> c(n), a(n);
for (int i = 0; i < n; i++) cin >> c[i];
for (int i = 0; i < n; i++) cin >> a[i];
const long long NEG = -1e18;
vector<long long> dp(n+1, NEG), ndp;
dp[0] = x;
for (int i = 0; i < n; i++) {
ndp.assign(n+1, NEG);
for (int used = 0; used <= i; used++) {
if (dp[used] < 0) continue;
if (dp[used] >= c[i]) {
ndp[used] = max(ndp[used], dp[used] - c[i] + a[i]);
}
ndp[used+1] = max(ndp[used+1], dp[used] + a[i]);
}
dp.swap(ndp);
}
int ans = n;
for (int used = 0; used <= n; used++) {
if (dp[used] >= 0) {
ans = used;
break;
}
}
cout << ans << '\n';
}
return 0;
}
C
#include <bits/stdc++.h>
using namespace std;
#define fastio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int main(){
fastio;
int t;
cin >> t;
while(t--){
long long n;
cin >> n;
long long ans = 0;
for(long long i = 1; i * i <= n; i++){
if(n % i == 0){
long long d = i, e = n / i;
if(d == e)
ans += (d - 1);
else
ans += (d - 1) + (e - 1);
}
}
cout << ans << "\n";
}
return 0;
}
D
#include <bits/stdc++.h>
using namespace std;
#define fastio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const int maxn = 1000000;
const int mod = 998244353;
long long f[maxn+1], d[maxn+1];
int main() {
fastio;
f[0] = 1;
for (int i = 1; i <= maxn; i++)
f[i] = f[i-1] * i % mod;
d[0] = 1;
d[1] = 0;
for (int i = 2; i <= maxn; i++)
d[i] = (i - 1LL) * (d[i-1] + d[i-2]) % mod;
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
if (n % 2 == 0)
cout << 1 << "\n";
else
cout << f[n] * d[n] % mod << "\n";
}
return 0;
}
E
#include <bits/stdc++.h>
using namespace std;
#define fastio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const int mod = 1e9 + 7;
int e[21][8], sg[256];
int main() {
fastio;
int p[8]= {2,3,5,7,11,13,17,19};
for(int v=1; v<=20; v++) {
int x=v;
for(int i=0; i<8; i++) {
e[v][i]=0;
while(x%p[i]==0) {
e[v][i]++;
x/=p[i];
}
}
}
for(int u=0; u<256; u++) sg[u]=(__builtin_parity(u)?mod-1:1);
int t;
cin>>t;
while(t--) {
int n;
cin>>n;
vector<int>a(n);
for(int i=0; i<n; i++) cin>>a[i];
long long ans=0;
int S[8]= {0}, c[256]= {0}, r[256], sr[256];
c[0]=1;
for(int i=0; i<n; i++) {
int v=a[i];
for(int k=0; k<8; k++) S[k]+=e[v][k];
r[0]=1;
for(int m=1; m<256; m++) {
int b=__builtin_ctz(m);
r[m]=(long long)r[m^(1<<b)]*S[b]%mod;
}
for(int m=0; m<256; m++) sr[m]=r[m];
for(int b=0; b<8; b++)
for(int m=0; m<256; m++)
if(m&(1<<b)) {
sr[m]+=sr[m^(1<<b)];
if(sr[m]>=mod) sr[m]-=mod;
}
long long sj=0;
for(int u=0; u<256; u++) {
sj = (sj + (long long)sg[u]*c[u]%mod*sr[255^u])%mod;
}
if(sj<0) sj+=mod;
ans=(ans+sj)%mod;
for(int m=0; m<256; m++) {
c[m]+=r[m];
if(c[m]>=mod) c[m]-=mod;
}
}
cout<<ans<<"\n";
}
return 0;
}
raneatharva
A
#include <bits/stdc++.h>
#define uint unsigned long long
#define int long long
#define double long double
#define KAMEHAMEHA freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
#define MADEINHEAVEN ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define DAWORLDZ cerr << "Time: " << duration.count() / 1000 << " ms" << endl;
using namespace std;
using namespace chrono;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#define M_PI 3.14159265358979323846
static const int MAXN=100000;
const int MOD = 998244353;
const int MAX_N = 10000000;
const int p = 3 * 1e4 + 5;
using cd = complex<double>;
const double PI = acos(-1);
static const int LIM = 1000000000LL;
const int MOD1 = 1000000007;
void solve(){
int n;
cin >> n;
cout << n << endl;
}
int32_t main(){
MADEINHEAVEN
auto start1 = high_resolution_clock::now();
#ifndef ONLINE_JUDGE
KAMEHAMEHA
#endif
int t = 1;
cin >> t;
while(t--)
solve();
auto stop1 = high_resolution_clock::now();
auto duration = duration_cast<microseconds>(stop1 - start1);
#ifndef ONLINE_JUDGE
DAWORLDZ
#endif
return 0;
}
B
#include <bits/stdc++.h>
#define uint unsigned long long
#define int long long
#define double long double
#define KAMEHAMEHA freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
#define MADEINHEAVEN ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define DAWORLDZ cerr << "Time: " << duration.count() / 1000 << " ms" << endl;
using namespace std;
using namespace chrono;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#define M_PI 3.14159265358979323846
static const int MAXN=100000;
const int MOD = 998244353;
const int MAX_N = 10000000;
const int p = 3 * 1e4 + 5;
using cd = complex<double>;
const double PI = acos(-1);
static const int LIM = 1000000000LL;
const int MOD1 = 1000000007;
void solve(){
int n, x;
cin >> n >> x;
vector<int> c(n), a(n);
for (int i = 0; i < n; i++){
cin >> c[i];
}
for (int i = 0; i < n; i++){
cin >> a[i];
}
int MAX_OP = n;
vector<vector<int>> dp(n+1, vector<int>(MAX_OP+1, -1));
dp[0][0] = x;
for (int i = 0; i < n; i++){
for (int op = 0; op <= MAX_OP; op++){
if(dp[i][op] < 0) continue;
if(dp[i][op] >= c[i]){
dp[i+1][op] = max(dp[i+1][op], dp[i][op] - c[i] + a[i]);
}
if(op + 1 <= MAX_OP){
dp[i+1][op+1] = max(dp[i+1][op+1], dp[i][op] + a[i]);
}
}
}
int ans = -1;
for (int op = 0; op <= MAX_OP; op++){
if(dp[n][op] >= 0){
ans = op;
break;
}
}
cout << ans << endl;
}
int32_t main(){
MADEINHEAVEN
auto start1 = high_resolution_clock::now();
#ifndef ONLINE_JUDGE
KAMEHAMEHA
#endif
int t = 1;
cin >> t;
while(t--)
solve();
auto stop1 = high_resolution_clock::now();
auto duration = duration_cast<microseconds>(stop1 - start1);
#ifndef ONLINE_JUDGE
DAWORLDZ
#endif
return 0;
}
C
#include <bits/stdc++.h>
#define uint unsigned long long
#define int long long
#define double long double
#define KAMEHAMEHA freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
#define MADEINHEAVEN ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define DAWORLDZ cerr << "Time: " << duration.count() / 1000 << " ms" << endl;
using namespace std;
using namespace chrono;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#define M_PI 3.14159265358979323846
static const int MAXN=100000;
const int MOD = 998244353;
const int MAX_N = 10000000;
const int p = 3 * 1e4 + 5;
using cd = complex<double>;
const double PI = acos(-1);
static const int LIM = 1000000000LL;
const int MOD1 = 1000000007;
void solve(){
int n;
cin >> n;
int sum = 0;
int count = 0;
for(int i = 1; i * i <= n; i++){
if(n % i == 0){
if(i * i == n){
sum += i;
count++;
}
else{
sum += i + n / i;
count += 2;
}
}
}
cout << sum - count << endl;
}
int32_t main(){
MADEINHEAVEN
auto start1 = high_resolution_clock::now();
#ifndef ONLINE_JUDGE
KAMEHAMEHA
#endif
int t = 1;
cin >> t;
while(t--)
solve();
auto stop1 = high_resolution_clock::now();
auto duration = duration_cast<microseconds>(stop1 - start1);
#ifndef ONLINE_JUDGE
DAWORLDZ
#endif
return 0;
}
D
#include <bits/stdc++.h>
#define uint unsigned long long
#define int long long
#define double long double
#define KAMEHAMEHA freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
#define MADEINHEAVEN ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define DAWORLDZ cerr << "Time: " << duration.count() / 1000 << " ms" << endl;
using namespace std;
using namespace chrono;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#define M_PI 3.14159265358979323846
static const int MAXN=100000;
const int MOD = 998244353;
const int MAX_N = 10000000;
const int p = 3 * 1e4 + 5;
using cd = complex<double>;
const double PI = acos(-1);
static const int LIM = 1000000000LL;
const int MOD1 = 1000000007;
int add(int a, int b) {
a += b;
if (a >= MOD) a -= MOD;
return a;
}
int mul(int a, int b) {
return ((a * b) % MOD);
}
void solve(){
int t;
cin >> t;
vector<int> ns(t);
int mx = 0;
for(int i = 0; i < t; i++){
cin >> ns[i];
mx = max(mx, ns[i]);
}
vector<int> fact(mx+1), der(mx+1);
fact[0] = 1;
for(int i = 1; i <= mx; i++){
fact[i] = mul(fact[i-1], i);
}
der[0] = 1;
if(mx >= 1) der[1] = 0;
for(int i = 2; i <= mx; i++){
der[i] = mul(i - 1, add(der[i-1], der[i-2]));
}
for(int n : ns){
if(n % 2 == 0){
cout << 1 << endl;
} else {
cout << mul(fact[n], der[n]) << endl;
}
}
}
int32_t main(){
MADEINHEAVEN
auto start1 = high_resolution_clock::now();
#ifndef ONLINE_JUDGE
KAMEHAMEHA
#endif
int t = 1;
// cin >> t;
while(t--)
solve();
auto stop1 = high_resolution_clock::now();
auto duration = duration_cast<microseconds>(stop1 - start1);
#ifndef ONLINE_JUDGE
DAWORLDZ
#endif
return 0;
}
E
#include <bits/stdc++.h>
#define uint unsigned long long
#define int long long
#define double long double
#define KAMEHAMEHA freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
#define MADEINHEAVEN ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define DAWORLDZ cerr << "Time: " << duration.count() / 1000 << " ms" << endl;
using namespace std;
using namespace chrono;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#define M_PI 3.14159265358979323846
static const int MAXN=100000;
const int MOD = 998244353;
const int MAX_N = 10000000;
const int p = 3 * 1e4 + 5;
using cd = complex<double>;
const double PI = acos(-1);
static const int LIM = 1000000000LL;
const int MOD1 = 1000000007;
vector<int> primes = {2, 3, 5, 7, 11, 13, 17, 19};
vector<array<int, 8>> factors(21);
void precomp(){
for (int x = 1; x <= 20; x++){
array<int, 8> exp = {0,0,0,0,0,0,0,0};
int temp = x;
for (int i = 0; i < 8; i++){
while(temp % primes[i] == 0){
exp[i]++;
temp /= primes[i];
}
}
factors[x] = exp;
}
}
void solve(){
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++){
cin >> a[i];
}
int cur[8] = {0,0,0,0,0,0,0,0};
vector<int> dp(256, 0);
dp[0] = 1;
int ans = 0;
for (int i = 0; i < n; i++){
int num = a[i];
for (int j = 0; j < 8; j++){
cur[j] += factors[num][j];
}
int mp[256], pn[256];
mp[0] = 1;
for (int i = 1; i < 256; i++){
int p = __builtin_ctz(i);
int x = i ^ (1 << p);
mp[i] = (mp[x] * (cur[p] % MOD1)) % MOD1;
}
int curr[8];
for (int j = 0; j < 8; j++){
curr[j] = (cur[j] + 1LL) % MOD1;
}
for (int i = 0; i < 256; i++){
int prod = 1;
for (int j = 0; j < 8; j++){
if (!(i & (1 << j))){
prod = (prod * curr[j]) % MOD1;
}
}
pn[i] = prod;
}
for (int i = 0; i < 256; i++){
int b = __builtin_popcount(i);
int t = pn[i];
t = (t * dp[i]) % MOD1;
if(b & 1) t = (MOD1 - t) % MOD1;
ans = (ans + t) % MOD1;
}
for (int i = 0; i < 256; i++){
dp[i] = (dp[i] + mp[i]) % MOD1;
}
}
cout << ans % MOD1 << endl;
}
int32_t main(){
MADEINHEAVEN
auto start1 = high_resolution_clock::now();
#ifndef ONLINE_JUDGE
KAMEHAMEHA
#endif
precomp();
int t = 1;
cin >> t;
while(t--)
solve();
auto stop1 = high_resolution_clock::now();
auto duration = duration_cast<microseconds>(stop1 - start1);
#ifndef ONLINE_JUDGE
DAWORLDZ
#endif
return 0;
}
K-423
A
/** Created by 5cm/s on 2025/04/17 22:38:12. **/
#include <bits/stdc++.h>
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#define endl '\n'
#endif
using namespace std;
void elysia() {
int64_t n;
cin >> n;
cout << n << endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1;
cin >> T;
cout << fixed << setprecision(12);
while (T--)
elysia();
return 0;
}
B
/** Created by 5cm/s on 2025/04/17 22:39:53. **/
#include <bits/stdc++.h>
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#define endl '\n'
#endif
using namespace std;
template <typename T>
bool chmax(T &a, T b) {
return a < b ? (a = b, true) : false;
}
template <typename T>
bool chmin(T &a, T b) {
return a > b ? (a = b, true) : false;
}
void elysia() {
int n, x, inf = 1e9;
cin >> n >> x;
vector<int> a(n), b(n);
for (int &v : a)
cin >> v;
for (int &v : b)
cin >> v;
vector<int> f(n + 1, -inf);
f[0] = x;
for (int i = 0; i < n; ++i) {
vector<int> nf(n + 1, -inf);
for (int j = 0; j <= n; ++j) {
if (f[j] >= a[i]) {
chmax(nf[j], f[j] - a[i] + b[i]);
}
if (j + 1 <= n) {
chmax(nf[j + 1], f[j] + b[i]);
}
}
f.swap(nf);
}
for (int i = 0; i <= n; ++i) {
if (f[i] >= 0) {
cout << i << '\n';
return;
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1;
cin >> T;
cout << fixed << setprecision(12);
while (T--)
elysia();
return 0;
}
C
/** Created by 5cm/s on 2025/04/17 22:50:21. **/
#include <bits/stdc++.h>
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#define endl '\n'
#endif
using namespace std;
void elysia() {
int n;
cin >> n;
int64_t ans = 0;
for (int i = 1; i * i <= n; ++i) {
if (n % i == 0) {
ans += i - 1;
if (i * i < n) {
ans += n / i - 1;
}
}
}
cout << ans << endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1;
cin >> T;
cout << fixed << setprecision(12);
while (T--)
elysia();
return 0;
}
D
/** Created by 5cm/s on 2025/04/17 22:55:05. **/
#include <bits/stdc++.h>
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#define endl '\n'
#endif
using namespace std;
// @formatter:off
template <typename T>
T inverse(T a, T m) {
T u = 0, v = 1;
while (a != 0) {
T t = m / a;
m -= t * a;
swap(a, m);
u -= t * v;
swap(u, v);
}
assert(m == 1);
return u;
}
template <typename T>
class Modular {
public:
using Type = typename decay<decltype(T::value)>::type;
constexpr Modular() : value() {}
template <typename U>
Modular(const U &x) {
value = normalize(x);
}
template <typename U>
static Type normalize(const U &x) {
Type v;
if (-mod() <= x && x < mod())
v = static_cast<Type>(x);
else
v = static_cast<Type>(x % mod());
if (v < 0)
v += mod();
return v;
}
const Type &operator()() const { return value; }
template <typename U>
explicit operator U() const {
return static_cast<U>(value);
}
constexpr static Type mod() { return T::value; }
Modular &operator+=(const Modular &other) {
if ((value += other.value) >= mod())
value -= mod();
return *this;
}
Modular &operator-=(const Modular &other) {
if ((value -= other.value) < 0)
value += mod();
return *this;
}
template <typename U>
Modular &operator+=(const U &other) {
return *this += Modular(other);
}
template <typename U>
Modular &operator-=(const U &other) {
return *this -= Modular(other);
}
Modular &operator++() { return *this += 1; }
Modular &operator--() { return *this -= 1; }
Modular operator++(int) {
Modular result(*this);
*this += 1;
return result;
}
Modular operator--(int) {
Modular result(*this);
*this -= 1;
return result;
}
Modular operator-() const { return Modular(-value); }
template <typename U = T>
typename enable_if<is_same<typename Modular<U>::Type, int>::value, Modular>::type &operator*=(const Modular &rhs) {
#ifdef _WIN32
uint64_t x = static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value);
uint32_t xh = static_cast<uint32_t>(x >> 32), xl = static_cast<uint32_t>(x), d, m;
asm("divl %4; \n\t" : "=a"(d), "=d"(m) : "d"(xh), "a"(xl), "r"(mod()));
value = m;
#else
value = normalize(static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value));
#endif
return *this;
}
template <typename U = T>
typename enable_if<is_same<typename Modular<U>::Type, long long>::value, Modular>::type &
operator*=(const Modular &rhs) {
long long q = static_cast<long long>(static_cast<long double>(value) * rhs.value / mod());
value = normalize(value * rhs.value - q * mod());
return *this;
}
template <typename U = T>
typename enable_if<!is_integral<typename Modular<U>::Type>::value, Modular>::type &operator*=(const Modular &rhs) {
value = normalize(value * rhs.value);
return *this;
}
Modular &operator/=(const Modular &other) { return *this *= Modular(inverse(other.value, mod())); }
friend const Type &abs(const Modular &x) { return x.value; }
template <typename U>
friend bool operator==(const Modular<U> &lhs, const Modular<U> &rhs);
template <typename U>
friend bool operator<(const Modular<U> &lhs, const Modular<U> &rhs);
template <typename V, typename U>
friend V &operator>>(V &stream, Modular<U> &number);
template <typename V>
operator V() {
return (V)value;
}
private:
Type value;
};
template <typename T>
bool operator==(const Modular<T> &lhs, const Modular<T> &rhs) {
return lhs.value == rhs.value;
}
template <typename T, typename U>
bool operator==(const Modular<T> &lhs, U rhs) {
return lhs == Modular<T>(rhs);
}
template <typename T, typename U>
bool operator==(U lhs, const Modular<T> &rhs) {
return Modular<T>(lhs) == rhs;
}
template <typename T>
bool operator!=(const Modular<T> &lhs, const Modular<T> &rhs) {
return !(lhs == rhs);
}
template <typename T, typename U>
bool operator!=(const Modular<T> &lhs, U rhs) {
return !(lhs == rhs);
}
template <typename T, typename U>
bool operator!=(U lhs, const Modular<T> &rhs) {
return !(lhs == rhs);
}
template <typename T>
bool operator<(const Modular<T> &lhs, const Modular<T> &rhs) {
return lhs.value < rhs.value;
}
template <typename T>
Modular<T> operator+(const Modular<T> &lhs, const Modular<T> &rhs) {
return Modular<T>(lhs) += rhs;
}
template <typename T, typename U>
Modular<T> operator+(const Modular<T> &lhs, U rhs) {
return Modular<T>(lhs) += rhs;
}
template <typename T, typename U>
Modular<T> operator+(U lhs, const Modular<T> &rhs) {
return Modular<T>(lhs) += rhs;
}
template <typename T>
Modular<T> operator-(const Modular<T> &lhs, const Modular<T> &rhs) {
return Modular<T>(lhs) -= rhs;
}
template <typename T, typename U>
Modular<T> operator-(const Modular<T> &lhs, U rhs) {
return Modular<T>(lhs) -= rhs;
}
template <typename T, typename U>
Modular<T> operator-(U lhs, const Modular<T> &rhs) {
return Modular<T>(lhs) -= rhs;
}
template <typename T>
Modular<T> operator*(const Modular<T> &lhs, const Modular<T> &rhs) {
return Modular<T>(lhs) *= rhs;
}
template <typename T, typename U>
Modular<T> operator*(const Modular<T> &lhs, U rhs) {
return Modular<T>(lhs) *= rhs;
}
template <typename T, typename U>
Modular<T> operator*(U lhs, const Modular<T> &rhs) {
return Modular<T>(lhs) *= rhs;
}
template <typename T>
Modular<T> operator/(const Modular<T> &lhs, const Modular<T> &rhs) {
return Modular<T>(lhs) /= rhs;
}
template <typename T, typename U>
Modular<T> operator/(const Modular<T> &lhs, U rhs) {
return Modular<T>(lhs) /= rhs;
}
template <typename T, typename U>
Modular<T> operator/(U lhs, const Modular<T> &rhs) {
return Modular<T>(lhs) /= rhs;
}
template <typename T, typename U>
Modular<T> power(const Modular<T> &a, const U &b) {
if (b < 0)
return 1 / power(a, -b);
Modular<T> x = a, res = 1;
U p = b;
while (p > 0) {
if (p & 1)
res *= x;
x *= x;
p >>= 1;
}
return res;
}
template <typename T>
bool IsZero(const Modular<T> &number) {
return number() == 0;
}
template <typename T>
string to_string(const Modular<T> &number) {
return to_string(number());
}
// U == std::ostream? but done this way because of fastoutput
template <typename U, typename T>
U &operator<<(U &stream, const Modular<T> &number) {
return stream << number();
}
// U == std::istream? but done this way because of fastinput
template <typename U, typename T>
U &operator>>(U &stream, Modular<T> &number) {
typename common_type<typename Modular<T>::Type, long long>::type x;
stream >> x;
number.value = Modular<T>::normalize(x);
return stream;
}
// using ModType = int;
//
// struct VarMod { static ModType value; };
// ModType VarMod::value;
// ModType &md = VarMod::value;
// using Mint = Modular<VarMod>;
constexpr int md = 998244353;
// constexpr int md = 1e9 + 7;
using Mint = Modular<std::integral_constant<decay<decltype(md)>::type, md>>;
// @formatter:on
vector<Mint> fact;
vector<Mint> inv_fact;
Mint C(int n, int k) {
if (k < 0 || k > n) {
return 0;
}
while ((int)fact.size() < n + 1) {
if (fact.empty()) {
fact = inv_fact = {1};
continue;
}
fact.push_back(fact.back() * (int)fact.size());
inv_fact.push_back(1 / fact.back());
}
return fact[n] * inv_fact[k] * inv_fact[n - k];
}
constexpr int N = 1e6;
vector<Mint> D(N + 1);
void elysia() {
int n;
cin >> n;
C(n, 0);
if (n == 1) {
cout << 0 << endl;
return;
}
if (n % 2 == 0) {
cout << 1 << endl;
} else {
cout << fact[n] * D[n] << endl;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
D[0] = D[2] = 1;
for (int i = 3; i <= N; ++i) {
D[i] = (D[i - 1] + D[i - 2]) * (i - 1);
}
int T = 1;
cin >> T;
cout << fixed << setprecision(12);
while (T--)
elysia();
return 0;
}
E
/** Created by 5cm/s on 2025/04/17 23:35:51. **/
#include <bits/stdc++.h>
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#define endl '\n'
#endif
using namespace std;
// @formatter:off
template <typename T>
T inverse(T a, T m) {
T u = 0, v = 1;
while (a != 0) {
T t = m / a;
m -= t * a;
swap(a, m);
u -= t * v;
swap(u, v);
}
assert(m == 1);
return u;
}
template <typename T>
class Modular {
public:
using Type = typename decay<decltype(T::value)>::type;
constexpr Modular() : value() {}
template <typename U>
Modular(const U &x) {
value = normalize(x);
}
template <typename U>
static Type normalize(const U &x) {
Type v;
if (-mod() <= x && x < mod())
v = static_cast<Type>(x);
else
v = static_cast<Type>(x % mod());
if (v < 0)
v += mod();
return v;
}
const Type &operator()() const { return value; }
template <typename U>
explicit operator U() const {
return static_cast<U>(value);
}
constexpr static Type mod() { return T::value; }
Modular &operator+=(const Modular &other) {
if ((value += other.value) >= mod())
value -= mod();
return *this;
}
Modular &operator-=(const Modular &other) {
if ((value -= other.value) < 0)
value += mod();
return *this;
}
template <typename U>
Modular &operator+=(const U &other) {
return *this += Modular(other);
}
template <typename U>
Modular &operator-=(const U &other) {
return *this -= Modular(other);
}
Modular &operator++() { return *this += 1; }
Modular &operator--() { return *this -= 1; }
Modular operator++(int) {
Modular result(*this);
*this += 1;
return result;
}
Modular operator--(int) {
Modular result(*this);
*this -= 1;
return result;
}
Modular operator-() const { return Modular(-value); }
template <typename U = T>
typename enable_if<is_same<typename Modular<U>::Type, int>::value, Modular>::type &operator*=(const Modular &rhs) {
#ifdef _WIN32
uint64_t x = static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value);
uint32_t xh = static_cast<uint32_t>(x >> 32), xl = static_cast<uint32_t>(x), d, m;
asm("divl %4; \n\t" : "=a"(d), "=d"(m) : "d"(xh), "a"(xl), "r"(mod()));
value = m;
#else
value = normalize(static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value));
#endif
return *this;
}
template <typename U = T>
typename enable_if<is_same<typename Modular<U>::Type, long long>::value, Modular>::type &
operator*=(const Modular &rhs) {
long long q = static_cast<long long>(static_cast<long double>(value) * rhs.value / mod());
value = normalize(value * rhs.value - q * mod());
return *this;
}
template <typename U = T>
typename enable_if<!is_integral<typename Modular<U>::Type>::value, Modular>::type &operator*=(const Modular &rhs) {
value = normalize(value * rhs.value);
return *this;
}
Modular &operator/=(const Modular &other) { return *this *= Modular(inverse(other.value, mod())); }
friend const Type &abs(const Modular &x) { return x.value; }
template <typename U>
friend bool operator==(const Modular<U> &lhs, const Modular<U> &rhs);
template <typename U>
friend bool operator<(const Modular<U> &lhs, const Modular<U> &rhs);
template <typename V, typename U>
friend V &operator>>(V &stream, Modular<U> &number);
template <typename V>
operator V() {
return (V)value;
}
private:
Type value;
};
template <typename T>
bool operator==(const Modular<T> &lhs, const Modular<T> &rhs) {
return lhs.value == rhs.value;
}
template <typename T, typename U>
bool operator==(const Modular<T> &lhs, U rhs) {
return lhs == Modular<T>(rhs);
}
template <typename T, typename U>
bool operator==(U lhs, const Modular<T> &rhs) {
return Modular<T>(lhs) == rhs;
}
template <typename T>
bool operator!=(const Modular<T> &lhs, const Modular<T> &rhs) {
return !(lhs == rhs);
}
template <typename T, typename U>
bool operator!=(const Modular<T> &lhs, U rhs) {
return !(lhs == rhs);
}
template <typename T, typename U>
bool operator!=(U lhs, const Modular<T> &rhs) {
return !(lhs == rhs);
}
template <typename T>
bool operator<(const Modular<T> &lhs, const Modular<T> &rhs) {
return lhs.value < rhs.value;
}
template <typename T>
Modular<T> operator+(const Modular<T> &lhs, const Modular<T> &rhs) {
return Modular<T>(lhs) += rhs;
}
template <typename T, typename U>
Modular<T> operator+(const Modular<T> &lhs, U rhs) {
return Modular<T>(lhs) += rhs;
}
template <typename T, typename U>
Modular<T> operator+(U lhs, const Modular<T> &rhs) {
return Modular<T>(lhs) += rhs;
}
template <typename T>
Modular<T> operator-(const Modular<T> &lhs, const Modular<T> &rhs) {
return Modular<T>(lhs) -= rhs;
}
template <typename T, typename U>
Modular<T> operator-(const Modular<T> &lhs, U rhs) {
return Modular<T>(lhs) -= rhs;
}
template <typename T, typename U>
Modular<T> operator-(U lhs, const Modular<T> &rhs) {
return Modular<T>(lhs) -= rhs;
}
template <typename T>
Modular<T> operator*(const Modular<T> &lhs, const Modular<T> &rhs) {
return Modular<T>(lhs) *= rhs;
}
template <typename T, typename U>
Modular<T> operator*(const Modular<T> &lhs, U rhs) {
return Modular<T>(lhs) *= rhs;
}
template <typename T, typename U>
Modular<T> operator*(U lhs, const Modular<T> &rhs) {
return Modular<T>(lhs) *= rhs;
}
template <typename T>
Modular<T> operator/(const Modular<T> &lhs, const Modular<T> &rhs) {
return Modular<T>(lhs) /= rhs;
}
template <typename T, typename U>
Modular<T> operator/(const Modular<T> &lhs, U rhs) {
return Modular<T>(lhs) /= rhs;
}
template <typename T, typename U>
Modular<T> operator/(U lhs, const Modular<T> &rhs) {
return Modular<T>(lhs) /= rhs;
}
template <typename T, typename U>
Modular<T> power(const Modular<T> &a, const U &b) {
if (b < 0)
return 1 / power(a, -b);
Modular<T> x = a, res = 1;
U p = b;
while (p > 0) {
if (p & 1)
res *= x;
x *= x;
p >>= 1;
}
return res;
}
template <typename T>
bool IsZero(const Modular<T> &number) {
return number() == 0;
}
template <typename T>
string to_string(const Modular<T> &number) {
return to_string(number());
}
// U == std::ostream? but done this way because of fastoutput
template <typename U, typename T>
U &operator<<(U &stream, const Modular<T> &number) {
return stream << number();
}
// U == std::istream? but done this way because of fastinput
template <typename U, typename T>
U &operator>>(U &stream, Modular<T> &number) {
typename common_type<typename Modular<T>::Type, long long>::type x;
stream >> x;
number.value = Modular<T>::normalize(x);
return stream;
}
// using ModType = int;
//
// struct VarMod { static ModType value; };
// ModType VarMod::value;
// ModType &md = VarMod::value;
// using Mint = Modular<VarMod>;
// constexpr int md = 998244353;
constexpr int md = 1e9 + 7;
using Mint = Modular<std::integral_constant<decay<decltype(md)>::type, md>>;
// @formatter:on
vector<Mint> fact;
vector<Mint> inv_fact;
Mint C(int n, int k) {
if (k < 0 || k > n) {
return 0;
}
while ((int)fact.size() < n + 1) {
if (fact.empty()) {
fact = inv_fact = {1};
continue;
}
fact.push_back(fact.back() * (int)fact.size());
inv_fact.push_back(1 / fact.back());
}
return fact[n] * inv_fact[k] * inv_fact[n - k];
}
void elysia() {
vector<int> h(21), ps = {2, 3, 5, 7, 11, 13, 17, 19};
for (int i = 0; i < ps.size(); ++i) {
h[ps[i]] = 1 << i;
}
int n, m = ps.size();
cin >> n;
Mint ans{};
vector<Mint> f(1 << m);
while (n--) {
int x;
cin >> x;
for (int i = 0; i < 1 << m; ++i) {
f[i]++;
}
for (int p : ps) {
if (x % p)
continue;
int y = 0;
while (x % p == 0)
x /= p, y++;
vector<Mint> nf(1 << m);
for (int i = 0; i < 1 << m; ++i) {
if (i & h[p]) {
nf[i] = f[i] + f[i ^ h[p]] * y;
} else {
nf[i] = f[i];
}
}
nf.swap(f);
}
ans += f.back();
}
cout << ans << endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1;
cin >> T;
cout << fixed << setprecision(12);
while (T--)
elysia();
return 0;
}
turkhuu622
A
#include <bits/stdc++.h>
#define FOR(i, a, b) for (auto i = (a); i <= (b); i++)
#define ROF(i, a, b) for (auto i = (a); i >= (b); i--)
using namespace std;
using ll = long long;
void solve() {
ll n;
cin >> n;
cout << n << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t; cin >> t; while (t--)
solve();
return 6/22;
}
B
#include <bits/stdc++.h>
#define FOR(i, a, b) for (auto i = (a); i <= (b); i++)
#define ROF(i, a, b) for (auto i = (a); i >= (b); i--)
using namespace std;
using ll = long long;
void solve() {
int n, x;
cin >> n >> x;
vector<int> c(n), a(n);
for (auto& i : c) cin >> i;
for (auto& i : a) cin >> i;
priority_queue<int> pq;
int ans = 0;
FOR(i, 0, n - 1) {
for (x -= c[i], pq.push(c[i]); x < 0; x += pq.top(), pq.pop(), ans++);
x += a[i];
}
cout << ans << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t; cin >> t; while (t--)
solve();
return 6/22;
}
C
#include <bits/stdc++.h>
#define FOR(i, a, b) for (auto i = (a); i <= (b); i++)
#define ROF(i, a, b) for (auto i = (a); i >= (b); i--)
using namespace std;
using ll = long long;
void bodooroi() {
int n;
cin >> n;
set<int> s;
FOR(i, 1, n / i) if ((n - i) % i == 0) s.insert((n - i) / i);
FOR(i, 1, n / i) {
if (1LL * i * n % (i + 1) == 0) {
ll k = 1LL * i * n / (i + 1);
if (k > 0 && k < n) {
s.insert(i);
}
}
}
ll ans = 0;
for (int i : s) ans += i;
cout << ans << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t; cin >> t; while (t--)
bodooroi();
return 6/22;
}
D
#include <bits/stdc++.h>
#define FOR(i, a, b) for (auto i = (a); i <= (b); i++)
#define ROF(i, a, b) for (auto i = (a); i >= (b); i--)
using namespace std;
using ll = long long;
template<int mod> struct modular {
using mint = modular;
int v;
modular() : v(0) {}
modular(long long x) {if ((v = x % mod) < 0) v += mod;}
mint operator+() const {return *this;}
mint operator-() const {return mint() - *this;}
mint inv() const {return pow(mod - 2);}
mint pow(long long a) const {
mint p = 1, u = *this;
for (; a; a >>= 1, u *= u) if (a & 1) p *= u;
return p;
}
mint& operator+=(const mint& a) {if ((v += a.v) >= mod) v -= mod; return *this;}
mint& operator-=(const mint& a) {if ((v -= a.v) < 0) v += mod; return *this;}
mint& operator*=(const mint& a) {v = (long long)v * a.v % mod; return *this;}
mint& operator/=(const mint& a) {return *this *= a.inv();}
friend bool operator==(const mint& a, const mint& b){return a.v == b.v;}
friend bool operator!=(const mint& a, const mint& b){return a.v != b.v;}
friend mint operator+(const mint& a, const mint& b) {return mint(a) += b;}
friend mint operator-(const mint& a, const mint& b) {return mint(a) -= b;}
friend mint operator*(const mint& a, const mint& b) {return mint(a) *= b;}
friend mint operator/(const mint& a, const mint& b) {return mint(a) /= b;}
friend istream& operator>>(istream& is, mint& a) {return is >> a.v;}
friend ostream& operator<<(ostream& os, const mint& a) {return os << a.v;}
};
const int mod = 998244353;
using mint = modular<mod>;
const int N = 1e6;
mint a[N + 1]{1, 0};
void init() {
FOR(i, 2, N) a[i] = mint(i) * (i - 1) * (a[i - 1] + a[i - 2] * (i - 1));
}
void bodooroi() {
int n;
cin >> n;
cout << (n % 2 == 0 ? 1 : a[n]) << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); init();
int t; cin >> t; while (t--)
bodooroi();
return 6/22;
}
E
#include <bits/stdc++.h>
#define FOR(i, a, b) for (auto i = (a); i <= (b); i++)
#define ROF(i, a, b) for (auto i = (a); i >= (b); i--)
using namespace std;
using ll = long long;
template<int mod> struct modular {
using mint = modular;
int v;
modular() : v(0) {}
modular(long long x) {if ((v = x % mod) < 0) v += mod;}
mint operator+() const {return *this;}
mint operator-() const {return mint() - *this;}
mint inv() const {return pow(mod - 2);}
mint pow(long long a) const {
mint p = 1, u = *this;
for (; a; a >>= 1, u *= u) if (a & 1) p *= u;
return p;
}
mint& operator+=(const mint& a) {if ((v += a.v) >= mod) v -= mod; return *this;}
mint& operator-=(const mint& a) {if ((v -= a.v) < 0) v += mod; return *this;}
mint& operator*=(const mint& a) {v = (long long)v * a.v % mod; return *this;}
mint& operator/=(const mint& a) {return *this *= a.inv();}
friend bool operator==(const mint& a, const mint& b){return a.v == b.v;}
friend bool operator!=(const mint& a, const mint& b){return a.v != b.v;}
friend mint operator+(const mint& a, const mint& b) {return mint(a) += b;}
friend mint operator-(const mint& a, const mint& b) {return mint(a) -= b;}
friend mint operator*(const mint& a, const mint& b) {return mint(a) *= b;}
friend mint operator/(const mint& a, const mint& b) {return mint(a) /= b;}
friend istream& operator>>(istream& is, mint& a) {return is >> a.v;}
friend ostream& operator<<(ostream& os, const mint& a) {return os << a.v;}
};
const int mod = 1000000007;
using mint = modular<mod>;
int p[]{2, 3, 5, 7, 11, 13, 17, 19};
void bodooroi() {
int n;
mint ans = 0, s[256]{1};
int c[8]{};
for (cin >> n; n; n--) {
int a;
cin >> a;
FOR(i, 0, 7) for (; a % p[i] == 0; a /= p[i], c[i]++);
FOR(i, 0, 255) {
mint p = 1;
FOR(j, 0, 7) if (i >> j & 1) p *= c[j] + 1;
ans += p * s[255 - i] * (__builtin_parity(i) ? -1 : 1);
}
FOR(i, 0, 255) {
mint p = 1;
FOR(j, 0, 7) if (i >> j & 1) p *= c[j];
s[i] += p;
}
}
cout << ans << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t; cin >> t; while (t--)
bodooroi();
return 6/22;
}
__baozii__
A
for _ in range(int(input())):
print(int(input()))
B
import os
import random
import sys
from typing import *
from collections import defaultdict, Counter, deque
from functools import cache, reduce
from itertools import pairwise, combinations, permutations, groupby, accumulate
from bisect import bisect_left, bisect_right, insort_left, insort_right
from heapq import *
from math import gcd, lcm, isqrt
from operator import add, sub, mul, floordiv, truediv, and_, or_, xor
from types import GeneratorType
def bootstrap(f, stack=[]):
def wrappedfunc(*args, **kwargs):
if stack:
return f(*args, **kwargs)
else:
to = f(*args, **kwargs)
while True:
if type(to) is GeneratorType:
stack.append(to)
to = next(to)
else:
stack.pop()
if not stack:
break
to = stack[-1].send(to)
return to
return wrappedfunc
input = sys.stdin.readline
output = lambda x: sys.stdout.write(str(x) + "\n")
outputL = lambda x: sys.stdout.write(" ".join(map(str, x)) + "\n")
printerr = lambda *args, **kwargs: print("\u001B[31m", *args, "\u001B[0m", file=sys.stderr, **kwargs)
I = lambda: input().rstrip("\n")
II = lambda: int(input())
MII = lambda: map(int, input().split())
LMII = lambda: list(MII())
TMII = lambda: tuple(MII())
LI = lambda: list(I())
LSI = lambda: list(map(int, I()))
class SortedList:
def __init__(self, iterable=None, _load=200):
if iterable is None:
iterable = []
values = sorted(iterable)
self._len = _len = len(values)
self._load = _load
self._lists = _lists = [values[i:i + _load]
for i in range(0, _len, _load)]
self._list_lens = [len(_list) for _list in _lists]
self._min_s = [_list[0] for _list in _lists]
self._fen_tree = []
self._rebuild = True
def _fen_build(self):
self._fen_tree[:] = self._list_lens
_fen_tree = self._fen_tree
for i in range(len(_fen_tree)):
if i | i + 1 < len(_fen_tree):
_fen_tree[i | i + 1] += _fen_tree[i]
self._rebuild = False
def _fen_update(self, index, value):
if not self._rebuild:
_fen_tree = self._fen_tree
while index < len(_fen_tree):
_fen_tree[index] += value
index |= index + 1
def _fen_query(self, end):
if self._rebuild:
self._fen_build()
_fen_tree = self._fen_tree
x = 0
while end:
x += _fen_tree[end - 1]
end &= end - 1
return x
def _fen_findkth(self, k):
_list_lens = self._list_lens
if k < _list_lens[0]:
return 0, k
if k >= self._len - _list_lens[-1]:
return len(_list_lens) - 1, k + _list_lens[-1] - self._len
if self._rebuild:
self._fen_build()
_fen_tree = self._fen_tree
idx = -1
for d in reversed(range(len(_fen_tree).bit_length())):
right_idx = idx + (1 << d)
if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
idx = right_idx
k -= _fen_tree[idx]
return idx + 1, k
def _delete(self, pos, idx):
_lists = self._lists
_mins = self._min_s
_list_lens = self._list_lens
self._len -= 1
self._fen_update(pos, -1)
del _lists[pos][idx]
_list_lens[pos] -= 1
if _list_lens[pos]:
_mins[pos] = _lists[pos][0]
else:
del _lists[pos]
del _list_lens[pos]
del _mins[pos]
self._rebuild = True
def _loc_left(self, value):
if not self._len:
return 0, 0
_lists = self._lists
_mins = self._min_s
lo, pos = -1, len(_lists) - 1
while lo + 1 < pos:
mi = (lo + pos) >> 1
if value <= _mins[mi]:
pos = mi
else:
lo = mi
if pos and value <= _lists[pos - 1][-1]:
pos -= 1
_list = _lists[pos]
lo, idx = -1, len(_list)
while lo + 1 < idx:
mi = (lo + idx) >> 1
if value <= _list[mi]:
idx = mi
else:
lo = mi
return pos, idx
def _loc_right(self, value):
if not self._len:
return 0, 0
_lists = self._lists
_mins = self._min_s
pos, hi = 0, len(_lists)
while pos + 1 < hi:
mi = (pos + hi) >> 1
if value < _mins[mi]:
hi = mi
else:
pos = mi
_list = _lists[pos]
lo, idx = -1, len(_list)
while lo + 1 < idx:
mi = (lo + idx) >> 1
if value < _list[mi]:
idx = mi
else:
lo = mi
return pos, idx
def add(self, value):
_load = self._load
_lists = self._lists
_mins = self._min_s
_list_lens = self._list_lens
self._len += 1
if _lists:
pos, idx = self._loc_right(value)
self._fen_update(pos, 1)
_list = _lists[pos]
_list.insert(idx, value)
_list_lens[pos] += 1
_mins[pos] = _list[0]
if _load + _load < len(_list):
_lists.insert(pos + 1, _list[_load:])
_list_lens.insert(pos + 1, len(_list) - _load)
_mins.insert(pos + 1, _list[_load])
_list_lens[pos] = _load
del _list[_load:]
self._rebuild = True
else:
_lists.append([value])
_mins.append(value)
_list_lens.append(1)
self._rebuild = True
def discard(self, value):
_lists = self._lists
if _lists:
pos, idx = self._loc_right(value)
if idx and _lists[pos][idx - 1] == value:
self._delete(pos, idx - 1)
def remove(self, value):
_len = self._len
self.discard(value)
if _len == self._len:
raise ValueError('{0!r} not in list'.format(value))
def pop(self, index=-1):
pos, idx = self._fen_findkth(self._len + index if index < 0 else index)
value = self._lists[pos][idx]
self._delete(pos, idx)
return value
def bisect_left(self, value):
pos, idx = self._loc_left(value)
return self._fen_query(pos) + idx
def bisect_right(self, value):
pos, idx = self._loc_right(value)
return self._fen_query(pos) + idx
def count(self, value):
return self.bisect_right(value) - self.bisect_left(value)
def __len__(self):
return self._len
def __getitem__(self, index):
pos, idx = self._fen_findkth(self._len + index if index < 0 else index)
return self._lists[pos][idx]
def __delitem__(self, index):
pos, idx = self._fen_findkth(self._len + index if index < 0 else index)
self._delete(pos, idx)
def __contains__(self, value):
_lists = self._lists
if _lists:
pos, idx = self._loc_left(value)
return idx < len(_lists[pos]) and _lists[pos][idx] == value
return False
def __iter__(self):
return (value for _list in self._lists for value in _list)
def __reversed__(self):
return (value for _list in reversed(self._lists)
for value in reversed(_list))
def __repr__(self):
return f'SortedList({list(self)})'
def solve():
n, x = MII()
c = LMII()
a = LMII()
s = SortedList()
cnt = 0
for co, ic in zip(c, a):
s.add(co)
x -= co
while x < 0:
x += s.pop()
cnt += 1
x += ic
print(cnt)
TC = II()
def main():
for _ in range(TC):
solve()
main()
C
using i64 = long long;
using i128 = __int128;
using u32 = unsigned;
using u64 = unsigned long long;
using f32 = double;
using f64 = long double;
#define uset unordered_set
#define umap unordered_map
#define vi vector<int>
#define vvi vector<vi>
#define vll vector<i64>
#define vvll vector<vll>
#define pii pair<int, int>
#define pll pair<i64, i64>
#define vpii vector<pii>
#define vpll vector<pll>
#define vvpii vector<vpii>
#define vvpll vector<vpll>
#define vz vector<Z>
#define vvz vector<vz>
#define pb push_back
#define pq priority_queue
#define ALL(x) (x).begin(), (x).end()
#define rep(i, x, y) for (int (i) = (x); (i) < (y); (i)++)
#define repr(i, x, y) for (int (i) = (x); (i) > (y); (i)--)
#define YES "YES\n"
#define NO "NO\n"
#define SZ(x) (static_cast<int>(x.size()))
#include <bits/stdc++.h>
using namespace std;
namespace atcoder {
namespace internal {
// @param m `1 <= m`
// @return x mod m
constexpr long long safe_mod(long long x, long long m) {
x %= m;
if (x < 0) x += m;
return x;
}
// Fast modular multiplication by barrett reduction
// Reference: https://en.wikipedia.org/wiki/Barrett_reduction
// NOTE: reconsider after Ice Lake
struct barrett {
unsigned int _m;
unsigned long long im;
// @param m `1 <= m`
explicit barrett(unsigned int m) : _m(m), im((unsigned long long)(-1) / m + 1) {}
// @return m
unsigned int umod() const { return _m; }
// @param a `0 <= a < m`
// @param b `0 <= b < m`
// @return `a * b % m`
unsigned int mul(unsigned int a, unsigned int b) const {
// [1] m = 1
// a = b = im = 0, so okay
// [2] m >= 2
// im = ceil(2^64 / m)
// -> im * m = 2^64 + r (0 <= r < m)
// let z = a*b = c*m + d (0 <= c, d < m)
// a*b * im = (c*m + d) * im = c*(im*m) + d*im = c*2^64 + c*r + d*im
// c*r + d*im < m * m + m * im < m * m + 2^64 + m <= 2^64 + m * (m + 1) < 2^64 * 2
// ((ab * im) >> 64) == c or c + 1
unsigned long long z = a;
z *= b;
#ifdef _MSC_VER
unsigned long long x;
_umul128(z, im, &x);
#else
unsigned long long x =
(unsigned long long)(((unsigned __int128)(z)*im) >> 64);
#endif
unsigned long long y = x * _m;
return (unsigned int)(z - y + (z < y ? _m : 0));
}
};
// @param n `0 <= n`
// @param m `1 <= m`
// @return `(x ** n) % m`
constexpr long long pow_mod_constexpr(long long x, long long n, int m) {
if (m == 1) return 0;
unsigned int _m = (unsigned int)(m);
unsigned long long r = 1;
unsigned long long y = safe_mod(x, m);
while (n) {
if (n & 1) r = (r * y) % _m;
y = (y * y) % _m;
n >>= 1;
}
return r;
}
// Reference:
// M. Forisek and J. Jancina,
// Fast Primality Testing for Integers That Fit into a Machine Word
// @param n `0 <= n`
constexpr bool is_prime_constexpr(int n) {
if (n <= 1) return false;
if (n == 2 || n == 7 || n == 61) return true;
if (n % 2 == 0) return false;
long long d = n - 1;
while (d % 2 == 0) d /= 2;
constexpr long long bases[3] = {2, 7, 61};
for (long long a : bases) {
long long t = d;
long long y = pow_mod_constexpr(a, t, n);
while (t != n - 1 && y != 1 && y != n - 1) {
y = y * y % n;
t <<= 1;
}
if (y != n - 1 && t % 2 == 0) {
return false;
}
}
return true;
}
template <int n> constexpr bool is_prime = is_prime_constexpr(n);
// @param b `1 <= b`
// @return pair(g, x) s.t. g = gcd(a, b), xa = g (mod b), 0 <= x < b/g
constexpr std::pair<long long, long long> inv_gcd(long long a, long long b) {
a = safe_mod(a, b);
if (a == 0) return {b, 0};
// Contracts:
// [1] s - m0 * a = 0 (mod b)
// [2] t - m1 * a = 0 (mod b)
// [3] s * |m1| + t * |m0| <= b
long long s = b, t = a;
long long m0 = 0, m1 = 1;
while (t) {
long long u = s / t;
s -= t * u;
m0 -= m1 * u; // |m1 * u| <= |m1| * s <= b
// [3]:
// (s - t * u) * |m1| + t * |m0 - m1 * u|
// <= s * |m1| - t * u * |m1| + t * (|m0| + |m1| * u)
// = s * |m1| + t * |m0| <= b
auto tmp = s;
s = t;
t = tmp;
tmp = m0;
m0 = m1;
m1 = tmp;
}
// by [3]: |m0| <= b/g
// by g != b: |m0| < b/g
if (m0 < 0) m0 += b / s;
return {s, m0};
}
// Compile time primitive root
// @param m must be prime
// @return primitive root (and minimum in now)
constexpr int primitive_root_constexpr(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;
int divs[20] = {};
divs[0] = 2;
int cnt = 1;
int x = (m - 1) / 2;
while (x % 2 == 0) x /= 2;
for (int i = 3; (long long)(i)*i <= x; i += 2) {
if (x % i == 0) {
divs[cnt++] = i;
while (x % i == 0) {
x /= i;
}
}
}
if (x > 1) {
divs[cnt++] = x;
}
for (int g = 2;; g++) {
bool ok = true;
for (int i = 0; i < cnt; i++) {
if (pow_mod_constexpr(g, (m - 1) / divs[i], m) == 1) {
ok = false;
break;
}
}
if (ok) return g;
}
}
template <int m> constexpr int primitive_root = primitive_root_constexpr(m);
// @param n `n < 2^32`
// @param m `1 <= m < 2^32`
// @return sum_{i=0}^{n-1} floor((ai + b) / m) (mod 2^64)
unsigned long long floor_sum_unsigned(unsigned long long n,
unsigned long long m,
unsigned long long a,
unsigned long long b) {
unsigned long long ans = 0;
while (true) {
if (a >= m) {
ans += n * (n - 1) / 2 * (a / m);
a %= m;
}
if (b >= m) {
ans += n * (b / m);
b %= m;
}
unsigned long long y_max = a * n + b;
if (y_max < m) break;
// y_max < m * (n + 1)
// floor(y_max / m) <= n
n = (unsigned long long)(y_max / m);
b = (unsigned long long)(y_max % m);
std::swap(m, a);
}
return ans;
}
} // namespace internal
} // namespace atcoder
#if __cplusplus >= 202002L
#include <bit>
#endif
namespace atcoder {
namespace internal {
#if __cplusplus >= 202002L
using std::bit_ceil;
#else
// @return same with std::bit::bit_ceil
unsigned int bit_ceil(unsigned int n) {
unsigned int x = 1;
while (x < (unsigned int)(n)) x *= 2;
return x;
}
#endif
// @param n `1 <= n`
// @return same with std::bit::countr_zero
int countr_zero(unsigned int n) {
#ifdef _MSC_VER
unsigned long index;
_BitScanForward(&index, n);
return index;
#else
return __builtin_ctz(n);
#endif
}
// @param n `1 <= n`
// @return same with std::bit::countr_zero
constexpr int countr_zero_constexpr(unsigned int n) {
int x = 0;
while (!(n & (1 << x))) x++;
return x;
}
} // namespace internal
} // namespace atcoder
namespace atcoder {
namespace internal {
template <class E> struct csr {
std::vector<int> start;
std::vector<E> elist;
explicit csr(int n, const std::vector<std::pair<int, E>>& edges)
: start(n + 1), elist(edges.size()) {
for (auto e : edges) {
start[e.first + 1]++;
}
for (int i = 1; i <= n; i++) {
start[i] += start[i - 1];
}
auto counter = start;
for (auto e : edges) {
elist[counter[e.first]++] = e.second;
}
}
};
} // namespace internal
} // namespace atcoder
namespace atcoder {
namespace internal {
template <class T> struct simple_queue {
std::vector<T> payload;
int pos = 0;
void reserve(int n) { payload.reserve(n); }
int size() const { return int(payload.size()) - pos; }
bool empty() const { return pos == int(payload.size()); }
void push(const T& t) { payload.push_back(t); }
T& front() { return payload[pos]; }
void clear() {
payload.clear();
pos = 0;
}
void pop() { pos++; }
};
} // namespace internal
} // namespace atcoder
namespace atcoder {
namespace internal {
#ifndef _MSC_VER
template <class T>
using is_signed_int128 =
typename std::conditional<std::is_same<T, __int128_t>::value ||
std::is_same<T, __int128>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_unsigned_int128 =
typename std::conditional<std::is_same<T, __uint128_t>::value ||
std::is_same<T, unsigned __int128>::value,
std::true_type,
std::false_type>::type;
template <class T>
using make_unsigned_int128 =
typename std::conditional<std::is_same<T, __int128_t>::value,
__uint128_t,
unsigned __int128>;
template <class T>
using is_integral = typename std::conditional<std::is_integral<T>::value ||
is_signed_int128<T>::value ||
is_unsigned_int128<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_signed_int = typename std::conditional<(is_integral<T>::value &&
std::is_signed<T>::value) ||
is_signed_int128<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_unsigned_int =
typename std::conditional<(is_integral<T>::value &&
std::is_unsigned<T>::value) ||
is_unsigned_int128<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using to_unsigned = typename std::conditional<
is_signed_int128<T>::value,
make_unsigned_int128<T>,
typename std::conditional<std::is_signed<T>::value,
std::make_unsigned<T>,
std::common_type<T>>::type>::type;
#else
template <class T> using is_integral = typename std::is_integral<T>;
template <class T>
using is_signed_int =
typename std::conditional<is_integral<T>::value && std::is_signed<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_unsigned_int =
typename std::conditional<is_integral<T>::value &&
std::is_unsigned<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using to_unsigned = typename std::conditional<is_signed_int<T>::value,
std::make_unsigned<T>,
std::common_type<T>>::type;
#endif
template <class T>
using is_signed_int_t = std::enable_if_t<is_signed_int<T>::value>;
template <class T>
using is_unsigned_int_t = std::enable_if_t<is_unsigned_int<T>::value>;
template <class T> using to_unsigned_t = typename to_unsigned<T>::type;
} // namespace internal
} // namespace atcoder
namespace atcoder {
namespace internal {
struct modint_base {};
struct static_modint_base : modint_base {};
template <class T> using is_modint = std::is_base_of<modint_base, T>;
template <class T> using is_modint_t = std::enable_if_t<is_modint<T>::value>;
} // namespace internal
template <int m, std::enable_if_t<(1 <= m)>* = nullptr>
struct static_modint : internal::static_modint_base {
using mint = static_modint;
public:
static constexpr int mod() { return m; }
static mint raw(int v) {
mint x;
x._v = v;
return x;
}
static_modint() : _v(0) {}
template <class T, internal::is_signed_int_t<T>* = nullptr>
static_modint(T v) {
long long x = (long long)(v % (long long)(umod()));
if (x < 0) x += umod();
_v = (unsigned int)(x);
}
template <class T, internal::is_unsigned_int_t<T>* = nullptr>
static_modint(T v) {
_v = (unsigned int)(v % umod());
}
unsigned int val() const { return _v; }
mint& operator++() {
_v++;
if (_v == umod()) _v = 0;
return *this;
}
mint& operator--() {
if (_v == 0) _v = umod();
_v--;
return *this;
}
mint operator++(int) {
mint result = *this;
++*this;
return result;
}
mint operator--(int) {
mint result = *this;
--*this;
return result;
}
mint& operator+=(const mint& rhs) {
_v += rhs._v;
if (_v >= umod()) _v -= umod();
return *this;
}
mint& operator-=(const mint& rhs) {
_v -= rhs._v;
if (_v >= umod()) _v += umod();
return *this;
}
mint& operator*=(const mint& rhs) {
unsigned long long z = _v;
z *= rhs._v;
_v = (unsigned int)(z % umod());
return *this;
}
mint& operator/=(const mint& rhs) { return *this = *this * rhs.inv(); }
mint operator+() const { return *this; }
mint operator-() const { return mint() - *this; }
mint pow(long long n) const {
assert(0 <= n);
mint x = *this, r = 1;
while (n) {
if (n & 1) r *= x;
x *= x;
n >>= 1;
}
return r;
}
mint inv() const {
if (prime) {
assert(_v);
return pow(umod() - 2);
} else {
auto eg = internal::inv_gcd(_v, m);
assert(eg.first == 1);
return eg.second;
}
}
friend mint operator+(const mint& lhs, const mint& rhs) {
return mint(lhs) += rhs;
}
friend mint operator-(const mint& lhs, const mint& rhs) {
return mint(lhs) -= rhs;
}
friend mint operator*(const mint& lhs, const mint& rhs) {
return mint(lhs) *= rhs;
}
friend mint operator/(const mint& lhs, const mint& rhs) {
return mint(lhs) /= rhs;
}
friend bool operator==(const mint& lhs, const mint& rhs) {
return lhs._v == rhs._v;
}
friend bool operator!=(const mint& lhs, const mint& rhs) {
return lhs._v != rhs._v;
}
private:
unsigned int _v;
static constexpr unsigned int umod() { return m; }
static constexpr bool prime = internal::is_prime<m>;
};
template <int id> struct dynamic_modint : internal::modint_base {
using mint = dynamic_modint;
public:
static int mod() { return (int)(bt.umod()); }
static void set_mod(int m) {
assert(1 <= m);
bt = internal::barrett(m);
}
static mint raw(int v) {
mint x;
x._v = v;
return x;
}
dynamic_modint() : _v(0) {}
template <class T, internal::is_signed_int_t<T>* = nullptr>
dynamic_modint(T v) {
long long x = (long long)(v % (long long)(mod()));
if (x < 0) x += mod();
_v = (unsigned int)(x);
}
template <class T, internal::is_unsigned_int_t<T>* = nullptr>
dynamic_modint(T v) {
_v = (unsigned int)(v % mod());
}
unsigned int val() const { return _v; }
mint& operator++() {
_v++;
if (_v == umod()) _v = 0;
return *this;
}
mint& operator--() {
if (_v == 0) _v = umod();
_v--;
return *this;
}
mint operator++(int) {
mint result = *this;
++*this;
return result;
}
mint operator--(int) {
mint result = *this;
--*this;
return result;
}
mint& operator+=(const mint& rhs) {
_v += rhs._v;
if (_v >= umod()) _v -= umod();
return *this;
}
mint& operator-=(const mint& rhs) {
_v += mod() - rhs._v;
if (_v >= umod()) _v -= umod();
return *this;
}
mint& operator*=(const mint& rhs) {
_v = bt.mul(_v, rhs._v);
return *this;
}
mint& operator/=(const mint& rhs) { return *this = *this * rhs.inv(); }
mint operator+() const { return *this; }
mint operator-() const { return mint() - *this; }
mint pow(long long n) const {
assert(0 <= n);
mint x = *this, r = 1;
while (n) {
if (n & 1) r *= x;
x *= x;
n >>= 1;
}
return r;
}
mint inv() const {
auto eg = internal::inv_gcd(_v, mod());
assert(eg.first == 1);
return eg.second;
}
friend mint operator+(const mint& lhs, const mint& rhs) {
return mint(lhs) += rhs;
}
friend mint operator-(const mint& lhs, const mint& rhs) {
return mint(lhs) -= rhs;
}
friend mint operator*(const mint& lhs, const mint& rhs) {
return mint(lhs) *= rhs;
}
friend mint operator/(const mint& lhs, const mint& rhs) {
return mint(lhs) /= rhs;
}
friend bool operator==(const mint& lhs, const mint& rhs) {
return lhs._v == rhs._v;
}
friend bool operator!=(const mint& lhs, const mint& rhs) {
return lhs._v != rhs._v;
}
private:
unsigned int _v;
static internal::barrett bt;
static unsigned int umod() { return bt.umod(); }
};
template <int id> internal::barrett dynamic_modint<id>::bt(998244353);
using modint998244353 = static_modint<998244353>;
using modint1000000007 = static_modint<1000000007>;
using modint = dynamic_modint<-1>;
namespace internal {
template <class T>
using is_static_modint = std::is_base_of<internal::static_modint_base, T>;
template <class T>
using is_static_modint_t = std::enable_if_t<is_static_modint<T>::value>;
template <class> struct is_dynamic_modint : public std::false_type {};
template <int id>
struct is_dynamic_modint<dynamic_modint<id>> : public std::true_type {};
template <class T>
using is_dynamic_modint_t = std::enable_if_t<is_dynamic_modint<T>::value>;
} // namespace internal
} // namespace atcoder
namespace atcoder {
namespace internal {
// Reference:
// R. Tarjan,
// Depth-First Search and Linear Graph Algorithms
struct scc_graph {
public:
explicit scc_graph(int n) : _n(n) {}
int num_vertices() { return _n; }
void add_edge(int from, int to) { edges.push_back({from, {to}}); }
// @return pair of (# of scc, scc id)
std::pair<int, std::vector<int>> scc_ids() {
auto g = csr<edge>(_n, edges);
int now_ord = 0, group_num = 0;
std::vector<int> visited, low(_n), ord(_n, -1), ids(_n);
visited.reserve(_n);
auto dfs = [&](auto self, int v) -> void {
low[v] = ord[v] = now_ord++;
visited.push_back(v);
for (int i = g.start[v]; i < g.start[v + 1]; i++) {
auto to = g.elist[i].to;
if (ord[to] == -1) {
self(self, to);
low[v] = std::min(low[v], low[to]);
} else {
low[v] = std::min(low[v], ord[to]);
}
}
if (low[v] == ord[v]) {
while (true) {
int u = visited.back();
visited.pop_back();
ord[u] = _n;
ids[u] = group_num;
if (u == v) break;
}
group_num++;
}
};
for (int i = 0; i < _n; i++) {
if (ord[i] == -1) dfs(dfs, i);
}
for (auto& x : ids) {
x = group_num - 1 - x;
}
return {group_num, ids};
}
std::vector<std::vector<int>> scc() {
auto ids = scc_ids();
int group_num = ids.first;
std::vector<int> counts(group_num);
for (auto x : ids.second) counts[x]++;
std::vector<std::vector<int>> groups(ids.first);
for (int i = 0; i < group_num; i++) {
groups[i].reserve(counts[i]);
}
for (int i = 0; i < _n; i++) {
groups[ids.second[i]].push_back(i);
}
return groups;
}
private:
int _n;
struct edge {
int to;
};
std::vector<std::pair<int, edge>> edges;
};
} // namespace internal
} // namespace atcoder
mt19937_64 rng((unsigned) chrono::high_resolution_clock::now().time_since_epoch().count());
void solve() {
i64 n;
cin >> n;
i64 m = n, cnt = 1, s = 1;
for (i64 p = 2; p * p <= n; p++) {
if (n % p == 0) {
i64 c = 0, tot = 1, cur = 1;
while (n % p == 0) {
n /= p;
c++;
cur *= p;
tot += cur;
}
cnt *= c + 1;
s *= tot;
}
}
if (n > 1) {
cnt <<= 1;
s *= n + 1;
}
cout << s - cnt << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while (t--) solve();
}
D
using i64 = long long;
using i128 = __int128;
using u32 = unsigned;
using u64 = unsigned long long;
using f32 = double;
using f64 = long double;
#define uset unordered_set
#define umap unordered_map
#define vi vector<int>
#define vvi vector<vi>
#define vll vector<i64>
#define vvll vector<vll>
#define pii pair<int, int>
#define pll pair<i64, i64>
#define vpii vector<pii>
#define vpll vector<pll>
#define vvpii vector<vpii>
#define vvpll vector<vpll>
#define vz vector<Z>
#define vvz vector<vz>
#define pb push_back
#define pq priority_queue
#define ALL(x) (x).begin(), (x).end()
#define rep(i, x, y) for (int (i) = (x); (i) < (y); (i)++)
#define repr(i, x, y) for (int (i) = (x); (i) > (y); (i)--)
#define YES "YES\n"
#define NO "NO\n"
#define SZ(x) (static_cast<int>(x.size()))
#include <bits/stdc++.h>
using namespace std;
namespace atcoder {
namespace internal {
// @param m `1 <= m`
// @return x mod m
constexpr long long safe_mod(long long x, long long m) {
x %= m;
if (x < 0) x += m;
return x;
}
// Fast modular multiplication by barrett reduction
// Reference: https://en.wikipedia.org/wiki/Barrett_reduction
// NOTE: reconsider after Ice Lake
struct barrett {
unsigned int _m;
unsigned long long im;
// @param m `1 <= m`
explicit barrett(unsigned int m) : _m(m), im((unsigned long long)(-1) / m + 1) {}
// @return m
unsigned int umod() const { return _m; }
// @param a `0 <= a < m`
// @param b `0 <= b < m`
// @return `a * b % m`
unsigned int mul(unsigned int a, unsigned int b) const {
// [1] m = 1
// a = b = im = 0, so okay
// [2] m >= 2
// im = ceil(2^64 / m)
// -> im * m = 2^64 + r (0 <= r < m)
// let z = a*b = c*m + d (0 <= c, d < m)
// a*b * im = (c*m + d) * im = c*(im*m) + d*im = c*2^64 + c*r + d*im
// c*r + d*im < m * m + m * im < m * m + 2^64 + m <= 2^64 + m * (m + 1) < 2^64 * 2
// ((ab * im) >> 64) == c or c + 1
unsigned long long z = a;
z *= b;
#ifdef _MSC_VER
unsigned long long x;
_umul128(z, im, &x);
#else
unsigned long long x =
(unsigned long long)(((unsigned __int128)(z)*im) >> 64);
#endif
unsigned long long y = x * _m;
return (unsigned int)(z - y + (z < y ? _m : 0));
}
};
// @param n `0 <= n`
// @param m `1 <= m`
// @return `(x ** n) % m`
constexpr long long pow_mod_constexpr(long long x, long long n, int m) {
if (m == 1) return 0;
unsigned int _m = (unsigned int)(m);
unsigned long long r = 1;
unsigned long long y = safe_mod(x, m);
while (n) {
if (n & 1) r = (r * y) % _m;
y = (y * y) % _m;
n >>= 1;
}
return r;
}
// Reference:
// M. Forisek and J. Jancina,
// Fast Primality Testing for Integers That Fit into a Machine Word
// @param n `0 <= n`
constexpr bool is_prime_constexpr(int n) {
if (n <= 1) return false;
if (n == 2 || n == 7 || n == 61) return true;
if (n % 2 == 0) return false;
long long d = n - 1;
while (d % 2 == 0) d /= 2;
constexpr long long bases[3] = {2, 7, 61};
for (long long a : bases) {
long long t = d;
long long y = pow_mod_constexpr(a, t, n);
while (t != n - 1 && y != 1 && y != n - 1) {
y = y * y % n;
t <<= 1;
}
if (y != n - 1 && t % 2 == 0) {
return false;
}
}
return true;
}
template <int n> constexpr bool is_prime = is_prime_constexpr(n);
// @param b `1 <= b`
// @return pair(g, x) s.t. g = gcd(a, b), xa = g (mod b), 0 <= x < b/g
constexpr std::pair<long long, long long> inv_gcd(long long a, long long b) {
a = safe_mod(a, b);
if (a == 0) return {b, 0};
// Contracts:
// [1] s - m0 * a = 0 (mod b)
// [2] t - m1 * a = 0 (mod b)
// [3] s * |m1| + t * |m0| <= b
long long s = b, t = a;
long long m0 = 0, m1 = 1;
while (t) {
long long u = s / t;
s -= t * u;
m0 -= m1 * u; // |m1 * u| <= |m1| * s <= b
// [3]:
// (s - t * u) * |m1| + t * |m0 - m1 * u|
// <= s * |m1| - t * u * |m1| + t * (|m0| + |m1| * u)
// = s * |m1| + t * |m0| <= b
auto tmp = s;
s = t;
t = tmp;
tmp = m0;
m0 = m1;
m1 = tmp;
}
// by [3]: |m0| <= b/g
// by g != b: |m0| < b/g
if (m0 < 0) m0 += b / s;
return {s, m0};
}
// Compile time primitive root
// @param m must be prime
// @return primitive root (and minimum in now)
constexpr int primitive_root_constexpr(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;
int divs[20] = {};
divs[0] = 2;
int cnt = 1;
int x = (m - 1) / 2;
while (x % 2 == 0) x /= 2;
for (int i = 3; (long long)(i)*i <= x; i += 2) {
if (x % i == 0) {
divs[cnt++] = i;
while (x % i == 0) {
x /= i;
}
}
}
if (x > 1) {
divs[cnt++] = x;
}
for (int g = 2;; g++) {
bool ok = true;
for (int i = 0; i < cnt; i++) {
if (pow_mod_constexpr(g, (m - 1) / divs[i], m) == 1) {
ok = false;
break;
}
}
if (ok) return g;
}
}
template <int m> constexpr int primitive_root = primitive_root_constexpr(m);
// @param n `n < 2^32`
// @param m `1 <= m < 2^32`
// @return sum_{i=0}^{n-1} floor((ai + b) / m) (mod 2^64)
unsigned long long floor_sum_unsigned(unsigned long long n,
unsigned long long m,
unsigned long long a,
unsigned long long b) {
unsigned long long ans = 0;
while (true) {
if (a >= m) {
ans += n * (n - 1) / 2 * (a / m);
a %= m;
}
if (b >= m) {
ans += n * (b / m);
b %= m;
}
unsigned long long y_max = a * n + b;
if (y_max < m) break;
// y_max < m * (n + 1)
// floor(y_max / m) <= n
n = (unsigned long long)(y_max / m);
b = (unsigned long long)(y_max % m);
std::swap(m, a);
}
return ans;
}
} // namespace internal
} // namespace atcoder
#if __cplusplus >= 202002L
#include <bit>
#endif
namespace atcoder {
namespace internal {
#if __cplusplus >= 202002L
using std::bit_ceil;
#else
// @return same with std::bit::bit_ceil
unsigned int bit_ceil(unsigned int n) {
unsigned int x = 1;
while (x < (unsigned int)(n)) x *= 2;
return x;
}
#endif
// @param n `1 <= n`
// @return same with std::bit::countr_zero
int countr_zero(unsigned int n) {
#ifdef _MSC_VER
unsigned long index;
_BitScanForward(&index, n);
return index;
#else
return __builtin_ctz(n);
#endif
}
// @param n `1 <= n`
// @return same with std::bit::countr_zero
constexpr int countr_zero_constexpr(unsigned int n) {
int x = 0;
while (!(n & (1 << x))) x++;
return x;
}
} // namespace internal
} // namespace atcoder
namespace atcoder {
namespace internal {
template <class E> struct csr {
std::vector<int> start;
std::vector<E> elist;
explicit csr(int n, const std::vector<std::pair<int, E>>& edges)
: start(n + 1), elist(edges.size()) {
for (auto e : edges) {
start[e.first + 1]++;
}
for (int i = 1; i <= n; i++) {
start[i] += start[i - 1];
}
auto counter = start;
for (auto e : edges) {
elist[counter[e.first]++] = e.second;
}
}
};
} // namespace internal
} // namespace atcoder
namespace atcoder {
namespace internal {
template <class T> struct simple_queue {
std::vector<T> payload;
int pos = 0;
void reserve(int n) { payload.reserve(n); }
int size() const { return int(payload.size()) - pos; }
bool empty() const { return pos == int(payload.size()); }
void push(const T& t) { payload.push_back(t); }
T& front() { return payload[pos]; }
void clear() {
payload.clear();
pos = 0;
}
void pop() { pos++; }
};
} // namespace internal
} // namespace atcoder
namespace atcoder {
namespace internal {
#ifndef _MSC_VER
template <class T>
using is_signed_int128 =
typename std::conditional<std::is_same<T, __int128_t>::value ||
std::is_same<T, __int128>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_unsigned_int128 =
typename std::conditional<std::is_same<T, __uint128_t>::value ||
std::is_same<T, unsigned __int128>::value,
std::true_type,
std::false_type>::type;
template <class T>
using make_unsigned_int128 =
typename std::conditional<std::is_same<T, __int128_t>::value,
__uint128_t,
unsigned __int128>;
template <class T>
using is_integral = typename std::conditional<std::is_integral<T>::value ||
is_signed_int128<T>::value ||
is_unsigned_int128<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_signed_int = typename std::conditional<(is_integral<T>::value &&
std::is_signed<T>::value) ||
is_signed_int128<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_unsigned_int =
typename std::conditional<(is_integral<T>::value &&
std::is_unsigned<T>::value) ||
is_unsigned_int128<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using to_unsigned = typename std::conditional<
is_signed_int128<T>::value,
make_unsigned_int128<T>,
typename std::conditional<std::is_signed<T>::value,
std::make_unsigned<T>,
std::common_type<T>>::type>::type;
#else
template <class T> using is_integral = typename std::is_integral<T>;
template <class T>
using is_signed_int =
typename std::conditional<is_integral<T>::value && std::is_signed<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_unsigned_int =
typename std::conditional<is_integral<T>::value &&
std::is_unsigned<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using to_unsigned = typename std::conditional<is_signed_int<T>::value,
std::make_unsigned<T>,
std::common_type<T>>::type;
#endif
template <class T>
using is_signed_int_t = std::enable_if_t<is_signed_int<T>::value>;
template <class T>
using is_unsigned_int_t = std::enable_if_t<is_unsigned_int<T>::value>;
template <class T> using to_unsigned_t = typename to_unsigned<T>::type;
} // namespace internal
} // namespace atcoder
namespace atcoder {
namespace internal {
struct modint_base {};
struct static_modint_base : modint_base {};
template <class T> using is_modint = std::is_base_of<modint_base, T>;
template <class T> using is_modint_t = std::enable_if_t<is_modint<T>::value>;
} // namespace internal
template <int m, std::enable_if_t<(1 <= m)>* = nullptr>
struct static_modint : internal::static_modint_base {
using mint = static_modint;
public:
static constexpr int mod() { return m; }
static mint raw(int v) {
mint x;
x._v = v;
return x;
}
static_modint() : _v(0) {}
template <class T, internal::is_signed_int_t<T>* = nullptr>
static_modint(T v) {
long long x = (long long)(v % (long long)(umod()));
if (x < 0) x += umod();
_v = (unsigned int)(x);
}
template <class T, internal::is_unsigned_int_t<T>* = nullptr>
static_modint(T v) {
_v = (unsigned int)(v % umod());
}
unsigned int val() const { return _v; }
mint& operator++() {
_v++;
if (_v == umod()) _v = 0;
return *this;
}
mint& operator--() {
if (_v == 0) _v = umod();
_v--;
return *this;
}
mint operator++(int) {
mint result = *this;
++*this;
return result;
}
mint operator--(int) {
mint result = *this;
--*this;
return result;
}
mint& operator+=(const mint& rhs) {
_v += rhs._v;
if (_v >= umod()) _v -= umod();
return *this;
}
mint& operator-=(const mint& rhs) {
_v -= rhs._v;
if (_v >= umod()) _v += umod();
return *this;
}
mint& operator*=(const mint& rhs) {
unsigned long long z = _v;
z *= rhs._v;
_v = (unsigned int)(z % umod());
return *this;
}
mint& operator/=(const mint& rhs) { return *this = *this * rhs.inv(); }
mint operator+() const { return *this; }
mint operator-() const { return mint() - *this; }
mint pow(long long n) const {
assert(0 <= n);
mint x = *this, r = 1;
while (n) {
if (n & 1) r *= x;
x *= x;
n >>= 1;
}
return r;
}
mint inv() const {
if (prime) {
assert(_v);
return pow(umod() - 2);
} else {
auto eg = internal::inv_gcd(_v, m);
assert(eg.first == 1);
return eg.second;
}
}
friend mint operator+(const mint& lhs, const mint& rhs) {
return mint(lhs) += rhs;
}
friend mint operator-(const mint& lhs, const mint& rhs) {
return mint(lhs) -= rhs;
}
friend mint operator*(const mint& lhs, const mint& rhs) {
return mint(lhs) *= rhs;
}
friend mint operator/(const mint& lhs, const mint& rhs) {
return mint(lhs) /= rhs;
}
friend bool operator==(const mint& lhs, const mint& rhs) {
return lhs._v == rhs._v;
}
friend bool operator!=(const mint& lhs, const mint& rhs) {
return lhs._v != rhs._v;
}
private:
unsigned int _v;
static constexpr unsigned int umod() { return m; }
static constexpr bool prime = internal::is_prime<m>;
};
template <int id> struct dynamic_modint : internal::modint_base {
using mint = dynamic_modint;
public:
static int mod() { return (int)(bt.umod()); }
static void set_mod(int m) {
assert(1 <= m);
bt = internal::barrett(m);
}
static mint raw(int v) {
mint x;
x._v = v;
return x;
}
dynamic_modint() : _v(0) {}
template <class T, internal::is_signed_int_t<T>* = nullptr>
dynamic_modint(T v) {
long long x = (long long)(v % (long long)(mod()));
if (x < 0) x += mod();
_v = (unsigned int)(x);
}
template <class T, internal::is_unsigned_int_t<T>* = nullptr>
dynamic_modint(T v) {
_v = (unsigned int)(v % mod());
}
unsigned int val() const { return _v; }
mint& operator++() {
_v++;
if (_v == umod()) _v = 0;
return *this;
}
mint& operator--() {
if (_v == 0) _v = umod();
_v--;
return *this;
}
mint operator++(int) {
mint result = *this;
++*this;
return result;
}
mint operator--(int) {
mint result = *this;
--*this;
return result;
}
mint& operator+=(const mint& rhs) {
_v += rhs._v;
if (_v >= umod()) _v -= umod();
return *this;
}
mint& operator-=(const mint& rhs) {
_v += mod() - rhs._v;
if (_v >= umod()) _v -= umod();
return *this;
}
mint& operator*=(const mint& rhs) {
_v = bt.mul(_v, rhs._v);
return *this;
}
mint& operator/=(const mint& rhs) { return *this = *this * rhs.inv(); }
mint operator+() const { return *this; }
mint operator-() const { return mint() - *this; }
mint pow(long long n) const {
assert(0 <= n);
mint x = *this, r = 1;
while (n) {
if (n & 1) r *= x;
x *= x;
n >>= 1;
}
return r;
}
mint inv() const {
auto eg = internal::inv_gcd(_v, mod());
assert(eg.first == 1);
return eg.second;
}
friend mint operator+(const mint& lhs, const mint& rhs) {
return mint(lhs) += rhs;
}
friend mint operator-(const mint& lhs, const mint& rhs) {
return mint(lhs) -= rhs;
}
friend mint operator*(const mint& lhs, const mint& rhs) {
return mint(lhs) *= rhs;
}
friend mint operator/(const mint& lhs, const mint& rhs) {
return mint(lhs) /= rhs;
}
friend bool operator==(const mint& lhs, const mint& rhs) {
return lhs._v == rhs._v;
}
friend bool operator!=(const mint& lhs, const mint& rhs) {
return lhs._v != rhs._v;
}
private:
unsigned int _v;
static internal::barrett bt;
static unsigned int umod() { return bt.umod(); }
};
template <int id> internal::barrett dynamic_modint<id>::bt(998244353);
using modint998244353 = static_modint<998244353>;
using modint1000000007 = static_modint<1000000007>;
using modint = dynamic_modint<-1>;
namespace internal {
template <class T>
using is_static_modint = std::is_base_of<internal::static_modint_base, T>;
template <class T>
using is_static_modint_t = std::enable_if_t<is_static_modint<T>::value>;
template <class> struct is_dynamic_modint : public std::false_type {};
template <int id>
struct is_dynamic_modint<dynamic_modint<id>> : public std::true_type {};
template <class T>
using is_dynamic_modint_t = std::enable_if_t<is_dynamic_modint<T>::value>;
} // namespace internal
} // namespace atcoder
namespace atcoder {
namespace internal {
// Reference:
// R. Tarjan,
// Depth-First Search and Linear Graph Algorithms
struct scc_graph {
public:
explicit scc_graph(int n) : _n(n) {}
int num_vertices() { return _n; }
void add_edge(int from, int to) { edges.push_back({from, {to}}); }
// @return pair of (# of scc, scc id)
std::pair<int, std::vector<int>> scc_ids() {
auto g = csr<edge>(_n, edges);
int now_ord = 0, group_num = 0;
std::vector<int> visited, low(_n), ord(_n, -1), ids(_n);
visited.reserve(_n);
auto dfs = [&](auto self, int v) -> void {
low[v] = ord[v] = now_ord++;
visited.push_back(v);
for (int i = g.start[v]; i < g.start[v + 1]; i++) {
auto to = g.elist[i].to;
if (ord[to] == -1) {
self(self, to);
low[v] = std::min(low[v], low[to]);
} else {
low[v] = std::min(low[v], ord[to]);
}
}
if (low[v] == ord[v]) {
while (true) {
int u = visited.back();
visited.pop_back();
ord[u] = _n;
ids[u] = group_num;
if (u == v) break;
}
group_num++;
}
};
for (int i = 0; i < _n; i++) {
if (ord[i] == -1) dfs(dfs, i);
}
for (auto& x : ids) {
x = group_num - 1 - x;
}
return {group_num, ids};
}
std::vector<std::vector<int>> scc() {
auto ids = scc_ids();
int group_num = ids.first;
std::vector<int> counts(group_num);
for (auto x : ids.second) counts[x]++;
std::vector<std::vector<int>> groups(ids.first);
for (int i = 0; i < group_num; i++) {
groups[i].reserve(counts[i]);
}
for (int i = 0; i < _n; i++) {
groups[ids.second[i]].push_back(i);
}
return groups;
}
private:
int _n;
struct edge {
int to;
};
std::vector<std::pair<int, edge>> edges;
};
} // namespace internal
} // namespace atcoder
mt19937_64 rng((unsigned) chrono::high_resolution_clock::now().time_since_epoch().count());
using Z = atcoder::modint998244353;
const int MAX = 1000001;
vz fac(MAX), f(MAX), ans(MAX);
void init() {
fac[0] = 1;
f[0] = 1;
rep(i, 1, MAX) {
fac[i] = fac[i - 1] * i;
if (i > 1) f[i] = (i - 1) * (f[i - 1] + f[i - 2]);
ans[i] = f[i] * fac[i];
}
}
void solve() {
int n;
cin >> n;
if (n % 2 == 0) cout << 1 << "\n";
else cout << ans[n].val() << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
init();
int t;
cin >> t;
while (t--) solve();
}
E
```
```
pandaforever
A
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <random>
#include <chrono>
using namespace std;
#define _int64 long long
#define mo 998244353
int main()
{
int i,j,k,l,t,m,x,y,o,b1;
_int64 n;
scanf("%d",&t);
for (l=0;l<t;l++)
{
scanf("%lld",&n);
printf("%lld\n",n);
}
}
B
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <random>
#include <chrono>
using namespace std;
#define _int64 long long
#define mo 998244353
int a[1000];
int c[1000];
int main()
{
int i,j,k,n,l,t,m,x,y,o,b1,now,ans;
priority_queue<int> pq;
scanf("%d",&t);
for (l=0;l<t;l++)
{
scanf("%d%d",&n,&x);
for (i=0;i<n;i++)
scanf("%d",&c[i]);
for (i=0;i<n;i++)
scanf("%d",&a[i]);
now=x;
while (!pq.empty()) pq.pop();
ans=0;
for (i=0;i<n;i++)
{
pq.push(c[i]);
while (now<c[i])
{
ans++;
now+=pq.top();
pq.pop();
}
now-=c[i];
now+=a[i];
}
printf("%d\n",ans);
}
}
C
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <random>
#include <chrono>
using namespace std;
#define _int64 long long
#define mo 998244353
int main()
{
int i,j,k,n,l,t,m,x,y,o,b1,v;
_int64 ans;
scanf("%d",&t);
for (l=0;l<t;l++)
{
scanf("%d",&n);
ans=0;
for (i=1;i*i<=n;i++)
{
if (n%i!=0) continue;
v=i;
ans+=(n-v)/v;
if (n/i!=i)
{
v=n/i;
ans+=(n-v)/v;
}
}
printf("%lld\n",ans);
}
}
D
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <random>
#include <chrono>
using namespace std;
#define _int64 long long
#define mo 998244353
#define faclim 1100000
_int64 fac[faclim];
_int64 invfac[faclim];
_int64 pow1(int x,int y)
{
int i;
_int64 ret;
ret=1;
for (i=30;i>=0;i--)
{
ret=ret*ret%mo;
if (((1<<i)&y)!=0) ret=ret*x%mo;
}
return ret;
}
_int64 inv(int x)
{
return pow1(x,mo-2);
}
_int64 c(int x,int y)
{
return fac[x]*invfac[y]%mo*invfac[x-y]%mo;
}
void init()
{
int i;
fac[0]=1;
for (i=1;i<faclim;i++)
fac[i]=fac[i-1]*i%mo;
invfac[faclim-1]=inv(fac[faclim-1]);
for (i=faclim-1;i>0;i--)
invfac[i-1]=invfac[i]*i%mo;
}
_int64 ans[1100000];
int main()
{
int i,j,k,n,l,t,m,x,y,o,b1;
_int64 tmp;
init();
ans[0]=1;
ans[1]=0;
for (i=2;i<=1000000;i++)
{
ans[i]=(ans[i-1]+(i-1)*ans[i-2]);
ans[i]%=mo;
ans[i]*=(i-1);
ans[i]%=mo;
ans[i]*=i;
ans[i]%=mo;
//if (i<10) cerr<<"ans:"<<ans[i]<<endl;
}
/*
for (i=1;i<=1000;i++)
{
ans[i]=0;
for (j=0;j<=i;j++)
{
tmp=fac[i]*fac[i-j];
tmp%=mo;
tmp*=c(i,j);
tmp%=mo;
if (j%2==0)
ans[i]+=tmp;
else ans[i]-=tmp;
}
ans[i]%=mo;
if (ans[i]<0) ans[i]+=mo;
if (i<10) cerr<<"ans:"<<ans[i]<<endl;
}
*/
scanf("%d",&t);
for (l=0;l<t;l++)
{
scanf("%d",&n);
if (n==1)
{
printf("0\n");
continue;
}
if (n%2==0)
{
printf("1\n");
continue;
}
printf("%lld\n",ans[n]);
}
}
E
```
```
Aging1986
A
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<vll> vvll;
typedef vector<vvll> vvvll;
typedef vector<pii> vpii;
typedef vector<vpii> vvpii;
typedef vector<pll> vpll;
typedef vector<vpll> vvpll;
typedef vector<pdd> vpdd;
typedef vector<vd> vvd;
#define yn(ans) printf("%s\n", (ans)?"Yes":"No");
#define YN(ans) printf("%s\n", (ans)?"YES":"NO");
template<class T> bool chmax(T &a, T b) {
if (a >= b) return false;
a = b; return true;
}
template<class T> bool chmin(T &a, T b) {
if (a <= b) return false;
a = b; return true;
}
#define FOR(i, s, e, t) for ((i) = (s); (i) < (e); (i) += (t))
#define REP(i, e) for (int i = 0; i < (e); ++i)
#define REP1(i, s, e) for (int i = (s); i < (e); ++i)
#define RREP(i, e) for (int i = (e); i >= 0; --i)
#define RREP1(i, e, s) for (int i = (e); i >= (s); --i)
#define all(v) v.begin(), v.end()
#define pb push_back
#define qb pop_back
#define pf push_front
#define qf pop_front
#define maxe max_element
#define mine min_element
ll inf = 1e18;
#define DEBUG printf("%d\n", __LINE__); fflush(stdout);
template<class T> void print(vector<T> &v, bool withSize = false) {
if (withSize) cout << v.size() << endl;
REP(i, v.size()) cout << v[i] << " ";
cout << endl;
}
mt19937_64 rng((unsigned int) chrono::steady_clock::now().time_since_epoch().count());
int __FAST_IO__ = []() {
std::ios::sync_with_stdio(0);
std::cin.tie(0);
std::cout.tie(0);
return 0;
}();
#define TESTS int t; cin >> t; while (t--)
#define TEST
int main() {
TESTS {
ll N;
cin >> N;
printf("%lld\n", N);
}
return 0;
}
B
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<vll> vvll;
typedef vector<vvll> vvvll;
typedef vector<pii> vpii;
typedef vector<vpii> vvpii;
typedef vector<pll> vpll;
typedef vector<vpll> vvpll;
typedef vector<pdd> vpdd;
typedef vector<vd> vvd;
#define yn(ans) printf("%s\n", (ans)?"Yes":"No");
#define YN(ans) printf("%s\n", (ans)?"YES":"NO");
template<class T> bool chmax(T &a, T b) {
if (a >= b) return false;
a = b; return true;
}
template<class T> bool chmin(T &a, T b) {
if (a <= b) return false;
a = b; return true;
}
#define FOR(i, s, e, t) for ((i) = (s); (i) < (e); (i) += (t))
#define REP(i, e) for (int i = 0; i < (e); ++i)
#define REP1(i, s, e) for (int i = (s); i < (e); ++i)
#define RREP(i, e) for (int i = (e); i >= 0; --i)
#define RREP1(i, e, s) for (int i = (e); i >= (s); --i)
#define all(v) v.begin(), v.end()
#define pb push_back
#define qb pop_back
#define pf push_front
#define qf pop_front
#define maxe max_element
#define mine min_element
ll inf = 1e18;
#define DEBUG printf("%d\n", __LINE__); fflush(stdout);
template<class T> void print(vector<T> &v, bool withSize = false) {
if (withSize) cout << v.size() << endl;
REP(i, v.size()) cout << v[i] << " ";
cout << endl;
}
mt19937_64 rng((unsigned int) chrono::steady_clock::now().time_since_epoch().count());
int __FAST_IO__ = []() {
std::ios::sync_with_stdio(0);
std::cin.tie(0);
std::cout.tie(0);
return 0;
}();
#define TESTS int t; cin >> t; while (t--)
#define TEST
int main() {
TESTS {
int N, X;
cin >> N >> X;
vi C(N), A(N);
REP(i, N) cin >> C[i];
REP(i, N) cin >> A[i];
int ans = 0, left = X;
priority_queue<int> q;
REP(i, N) {
q.push(C[i]);
left -= C[i];
while (left < 0) {
left += q.top();
ans++;
q.pop();
}
left += A[i];
}
printf("%d\n", ans);
}
return 0;
}
C
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<vll> vvll;
typedef vector<vvll> vvvll;
typedef vector<pii> vpii;
typedef vector<vpii> vvpii;
typedef vector<pll> vpll;
typedef vector<vpll> vvpll;
typedef vector<pdd> vpdd;
typedef vector<vd> vvd;
#define yn(ans) printf("%s\n", (ans)?"Yes":"No");
#define YN(ans) printf("%s\n", (ans)?"YES":"NO");
template<class T> bool chmax(T &a, T b) {
if (a >= b) return false;
a = b; return true;
}
template<class T> bool chmin(T &a, T b) {
if (a <= b) return false;
a = b; return true;
}
#define FOR(i, s, e, t) for ((i) = (s); (i) < (e); (i) += (t))
#define REP(i, e) for (int i = 0; i < (e); ++i)
#define REP1(i, s, e) for (int i = (s); i < (e); ++i)
#define RREP(i, e) for (int i = (e); i >= 0; --i)
#define RREP1(i, e, s) for (int i = (e); i >= (s); --i)
#define all(v) v.begin(), v.end()
#define pb push_back
#define qb pop_back
#define pf push_front
#define qf pop_front
#define maxe max_element
#define mine min_element
ll inf = 1e18;
#define DEBUG printf("%d\n", __LINE__); fflush(stdout);
template<class T> void print(vector<T> &v, bool withSize = false) {
if (withSize) cout << v.size() << endl;
REP(i, v.size()) cout << v[i] << " ";
cout << endl;
}
mt19937_64 rng((unsigned int) chrono::steady_clock::now().time_since_epoch().count());
int __FAST_IO__ = []() {
std::ios::sync_with_stdio(0);
std::cin.tie(0);
std::cout.tie(0);
return 0;
}();
#define TESTS int t; cin >> t; while (t--)
#define TEST
int main() {
TESTS {
int N;
cin >> N;
ll ans = 0;
for (int i = 1; 1ll * i * i <= N; ++i) {
if (N % i == 0) {
if (i > 1) ans += i - 1;
if (1ll * i * i != N) ans += N / i - 1;
}
}
printf("%lld\n", ans);
}
return 0;
}
D
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<vll> vvll;
typedef vector<vvll> vvvll;
typedef vector<pii> vpii;
typedef vector<vpii> vvpii;
typedef vector<pll> vpll;
typedef vector<vpll> vvpll;
typedef vector<pdd> vpdd;
typedef vector<vd> vvd;
#define yn(ans) printf("%s\n", (ans)?"Yes":"No");
#define YN(ans) printf("%s\n", (ans)?"YES":"NO");
template<class T> bool chmax(T &a, T b) {
if (a >= b) return false;
a = b; return true;
}
template<class T> bool chmin(T &a, T b) {
if (a <= b) return false;
a = b; return true;
}
#define FOR(i, s, e, t) for ((i) = (s); (i) < (e); (i) += (t))
#define REP(i, e) for (int i = 0; i < (e); ++i)
#define REP1(i, s, e) for (int i = (s); i < (e); ++i)
#define RREP(i, e) for (int i = (e); i >= 0; --i)
#define RREP1(i, e, s) for (int i = (e); i >= (s); --i)
#define all(v) v.begin(), v.end()
#define pb push_back
#define qb pop_back
#define pf push_front
#define qf pop_front
#define maxe max_element
#define mine min_element
ll inf = 1e18;
#define DEBUG printf("%d\n", __LINE__); fflush(stdout);
template<class T> void print(vector<T> &v, bool withSize = false) {
if (withSize) cout << v.size() << endl;
REP(i, v.size()) cout << v[i] << " ";
cout << endl;
}
mt19937_64 rng((unsigned int) chrono::steady_clock::now().time_since_epoch().count());
int __FAST_IO__ = []() {
std::ios::sync_with_stdio(0);
std::cin.tie(0);
std::cout.tie(0);
return 0;
}();
namespace atcoder {
namespace internal {
#ifndef _MSC_VER
template <class T>
using is_signed_int128 =
typename std::conditional<std::is_same<T, __int128_t>::value ||
std::is_same<T, __int128>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_unsigned_int128 =
typename std::conditional<std::is_same<T, __uint128_t>::value ||
std::is_same<T, unsigned __int128>::value,
std::true_type,
std::false_type>::type;
template <class T>
using make_unsigned_int128 =
typename std::conditional<std::is_same<T, __int128_t>::value,
__uint128_t,
unsigned __int128>;
template <class T>
using is_integral = typename std::conditional<std::is_integral<T>::value ||
is_signed_int128<T>::value ||
is_unsigned_int128<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_signed_int = typename std::conditional<(is_integral<T>::value &&
std::is_signed<T>::value) ||
is_signed_int128<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_unsigned_int =
typename std::conditional<(is_integral<T>::value &&
std::is_unsigned<T>::value) ||
is_unsigned_int128<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using to_unsigned = typename std::conditional<
is_signed_int128<T>::value,
make_unsigned_int128<T>,
typename std::conditional<std::is_signed<T>::value,
std::make_unsigned<T>,
std::common_type<T>>::type>::type;
#else
template <class T> using is_integral = typename std::is_integral<T>;
template <class T>
using is_signed_int =
typename std::conditional<is_integral<T>::value && std::is_signed<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_unsigned_int =
typename std::conditional<is_integral<T>::value &&
std::is_unsigned<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using to_unsigned = typename std::conditional<is_signed_int<T>::value,
std::make_unsigned<T>,
std::common_type<T>>::type;
#endif
template <class T>
using is_signed_int_t = std::enable_if_t<is_signed_int<T>::value>;
template <class T>
using is_unsigned_int_t = std::enable_if_t<is_unsigned_int<T>::value>;
template <class T> using to_unsigned_t = typename to_unsigned<T>::type;
} // namespace internal
} // namespace atcoder
namespace atcoder {
namespace internal {
// @param m `1 <= m`
// @return x mod m
constexpr long long safe_mod(long long x, long long m) {
x %= m;
if (x < 0) x += m;
return x;
}
// Fast modular multiplication by barrett reduction
// Reference: https://en.wikipedia.org/wiki/Barrett_reduction
// NOTE: reconsider after Ice Lake
struct barrett {
unsigned int _m;
unsigned long long im;
// @param m `1 <= m`
explicit barrett(unsigned int m) : _m(m), im((unsigned long long)(-1) / m + 1) {}
// @return m
unsigned int umod() const { return _m; }
// @param a `0 <= a < m`
// @param b `0 <= b < m`
// @return `a * b % m`
unsigned int mul(unsigned int a, unsigned int b) const {
// [1] m = 1
// a = b = im = 0, so okay
// [2] m >= 2
// im = ceil(2^64 / m)
// -> im * m = 2^64 + r (0 <= r < m)
// let z = a*b = c*m + d (0 <= c, d < m)
// a*b * im = (c*m + d) * im = c*(im*m) + d*im = c*2^64 + c*r + d*im
// c*r + d*im < m * m + m * im < m * m + 2^64 + m <= 2^64 + m * (m + 1) < 2^64 * 2
// ((ab * im) >> 64) == c or c + 1
unsigned long long z = a;
z *= b;
#ifdef _MSC_VER
unsigned long long x;
_umul128(z, im, &x);
#else
unsigned long long x =
(unsigned long long)(((unsigned __int128)(z)*im) >> 64);
#endif
unsigned long long y = x * _m;
return (unsigned int)(z - y + (z < y ? _m : 0));
}
};
// @param n `0 <= n`
// @param m `1 <= m`
// @return `(x ** n) % m`
constexpr long long pow_mod_constexpr(long long x, long long n, int m) {
if (m == 1) return 0;
unsigned int _m = (unsigned int)(m);
unsigned long long r = 1;
unsigned long long y = safe_mod(x, m);
while (n) {
if (n & 1) r = (r * y) % _m;
y = (y * y) % _m;
n >>= 1;
}
return r;
}
// Reference:
// M. Forisek and J. Jancina,
// Fast Primality Testing for Integers That Fit into a Machine Word
// @param n `0 <= n`
constexpr bool is_prime_constexpr(int n) {
if (n <= 1) return false;
if (n == 2 || n == 7 || n == 61) return true;
if (n % 2 == 0) return false;
long long d = n - 1;
while (d % 2 == 0) d /= 2;
constexpr long long bases[3] = {2, 7, 61};
for (long long a : bases) {
long long t = d;
long long y = pow_mod_constexpr(a, t, n);
while (t != n - 1 && y != 1 && y != n - 1) {
y = y * y % n;
t <<= 1;
}
if (y != n - 1 && t % 2 == 0) {
return false;
}
}
return true;
}
template <int n> constexpr bool is_prime = is_prime_constexpr(n);
// @param b `1 <= b`
// @return pair(g, x) s.t. g = gcd(a, b), xa = g (mod b), 0 <= x < b/g
constexpr std::pair<long long, long long> inv_gcd(long long a, long long b) {
a = safe_mod(a, b);
if (a == 0) return {b, 0};
// Contracts:
// [1] s - m0 * a = 0 (mod b)
// [2] t - m1 * a = 0 (mod b)
// [3] s * |m1| + t * |m0| <= b
long long s = b, t = a;
long long m0 = 0, m1 = 1;
while (t) {
long long u = s / t;
s -= t * u;
m0 -= m1 * u; // |m1 * u| <= |m1| * s <= b
// [3]:
// (s - t * u) * |m1| + t * |m0 - m1 * u|
// <= s * |m1| - t * u * |m1| + t * (|m0| + |m1| * u)
// = s * |m1| + t * |m0| <= b
auto tmp = s;
s = t;
t = tmp;
tmp = m0;
m0 = m1;
m1 = tmp;
}
// by [3]: |m0| <= b/g
// by g != b: |m0| < b/g
if (m0 < 0) m0 += b / s;
return {s, m0};
}
// Compile time primitive root
// @param m must be prime
// @return primitive root (and minimum in now)
constexpr int primitive_root_constexpr(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;
int divs[20] = {};
divs[0] = 2;
int cnt = 1;
int x = (m - 1) / 2;
while (x % 2 == 0) x /= 2;
for (int i = 3; (long long)(i)*i <= x; i += 2) {
if (x % i == 0) {
divs[cnt++] = i;
while (x % i == 0) {
x /= i;
}
}
}
if (x > 1) {
divs[cnt++] = x;
}
for (int g = 2;; g++) {
bool ok = true;
for (int i = 0; i < cnt; i++) {
if (pow_mod_constexpr(g, (m - 1) / divs[i], m) == 1) {
ok = false;
break;
}
}
if (ok) return g;
}
}
template <int m> constexpr int primitive_root = primitive_root_constexpr(m);
// @param n `n < 2^32`
// @param m `1 <= m < 2^32`
// @return sum_{i=0}^{n-1} floor((ai + b) / m) (mod 2^64)
unsigned long long floor_sum_unsigned(unsigned long long n,
unsigned long long m,
unsigned long long a,
unsigned long long b) {
unsigned long long ans = 0;
while (true) {
if (a >= m) {
ans += n * (n - 1) / 2 * (a / m);
a %= m;
}
if (b >= m) {
ans += n * (b / m);
b %= m;
}
unsigned long long y_max = a * n + b;
if (y_max < m) break;
// y_max < m * (n + 1)
// floor(y_max / m) <= n
n = (unsigned long long)(y_max / m);
b = (unsigned long long)(y_max % m);
std::swap(m, a);
}
return ans;
}
} // namespace internal
} // namespace atcoder
namespace atcoder {
namespace internal {
struct modint_base {};
struct static_modint_base : modint_base {};
template <class T> using is_modint = std::is_base_of<modint_base, T>;
template <class T> using is_modint_t = std::enable_if_t<is_modint<T>::value>;
} // namespace internal
template <int m, std::enable_if_t<(1 <= m)>* = nullptr>
struct static_modint : internal::static_modint_base {
using mint = static_modint;
public:
static constexpr int mod() { return m; }
static mint raw(int v) {
mint x;
x._v = v;
return x;
}
static_modint() : _v(0) {}
template <class T, internal::is_signed_int_t<T>* = nullptr>
static_modint(T v) {
long long x = (long long)(v % (long long)(umod()));
if (x < 0) x += umod();
_v = (unsigned int)(x);
}
template <class T, internal::is_unsigned_int_t<T>* = nullptr>
static_modint(T v) {
_v = (unsigned int)(v % umod());
}
unsigned int val() const { return _v; }
mint& operator++() {
_v++;
if (_v == umod()) _v = 0;
return *this;
}
mint& operator--() {
if (_v == 0) _v = umod();
_v--;
return *this;
}
mint operator++(int) {
mint result = *this;
++*this;
return result;
}
mint operator--(int) {
mint result = *this;
--*this;
return result;
}
mint& operator+=(const mint& rhs) {
_v += rhs._v;
if (_v >= umod()) _v -= umod();
return *this;
}
mint& operator-=(const mint& rhs) {
_v -= rhs._v;
if (_v >= umod()) _v += umod();
return *this;
}
mint& operator*=(const mint& rhs) {
unsigned long long z = _v;
z *= rhs._v;
_v = (unsigned int)(z % umod());
return *this;
}
mint& operator/=(const mint& rhs) { return *this = *this * rhs.inv(); }
mint operator+() const { return *this; }
mint operator-() const { return mint() - *this; }
mint pow(long long n) const {
assert(0 <= n);
mint x = *this, r = 1;
while (n) {
if (n & 1) r *= x;
x *= x;
n >>= 1;
}
return r;
}
mint inv() const {
if (prime) {
assert(_v);
return pow(umod() - 2);
} else {
auto eg = internal::inv_gcd(_v, m);
assert(eg.first == 1);
return eg.second;
}
}
friend mint operator+(const mint& lhs, const mint& rhs) {
return mint(lhs) += rhs;
}
friend mint operator-(const mint& lhs, const mint& rhs) {
return mint(lhs) -= rhs;
}
friend mint operator*(const mint& lhs, const mint& rhs) {
return mint(lhs) *= rhs;
}
friend mint operator/(const mint& lhs, const mint& rhs) {
return mint(lhs) /= rhs;
}
friend bool operator==(const mint& lhs, const mint& rhs) {
return lhs._v == rhs._v;
}
friend bool operator!=(const mint& lhs, const mint& rhs) {
return lhs._v != rhs._v;
}
friend ostream &operator<<(ostream &os, const mint& rhs) {
os << rhs.val(); return os;
}
private:
unsigned int _v;
static constexpr unsigned int umod() { return m; }
static constexpr bool prime = internal::is_prime<m>;
};
template <int id> struct dynamic_modint : internal::modint_base {
using mint = dynamic_modint;
public:
static int mod() { return (int)(bt.umod()); }
static void set_mod(int m) {
assert(1 <= m);
bt = internal::barrett(m);
}
static mint raw(int v) {
mint x;
x._v = v;
return x;
}
dynamic_modint() : _v(0) {}
template <class T, internal::is_signed_int_t<T>* = nullptr>
dynamic_modint(T v) {
long long x = (long long)(v % (long long)(mod()));
if (x < 0) x += mod();
_v = (unsigned int)(x);
}
template <class T, internal::is_unsigned_int_t<T>* = nullptr>
dynamic_modint(T v) {
_v = (unsigned int)(v % mod());
}
unsigned int val() const { return _v; }
mint& operator++() {
_v++;
if (_v == umod()) _v = 0;
return *this;
}
mint& operator--() {
if (_v == 0) _v = umod();
_v--;
return *this;
}
mint operator++(int) {
mint result = *this;
++*this;
return result;
}
mint operator--(int) {
mint result = *this;
--*this;
return result;
}
mint& operator+=(const mint& rhs) {
_v += rhs._v;
if (_v >= umod()) _v -= umod();
return *this;
}
mint& operator-=(const mint& rhs) {
_v += mod() - rhs._v;
if (_v >= umod()) _v -= umod();
return *this;
}
mint& operator*=(const mint& rhs) {
_v = bt.mul(_v, rhs._v);
return *this;
}
mint& operator/=(const mint& rhs) { return *this = *this * rhs.inv(); }
mint operator+() const { return *this; }
mint operator-() const { return mint() - *this; }
mint pow(long long n) const {
assert(0 <= n);
mint x = *this, r = 1;
while (n) {
if (n & 1) r *= x;
x *= x;
n >>= 1;
}
return r;
}
mint inv() const {
auto eg = internal::inv_gcd(_v, mod());
assert(eg.first == 1);
return eg.second;
}
friend mint operator+(const mint& lhs, const mint& rhs) {
return mint(lhs) += rhs;
}
friend mint operator-(const mint& lhs, const mint& rhs) {
return mint(lhs) -= rhs;
}
friend mint operator*(const mint& lhs, const mint& rhs) {
return mint(lhs) *= rhs;
}
friend mint operator/(const mint& lhs, const mint& rhs) {
return mint(lhs) /= rhs;
}
friend bool operator==(const mint& lhs, const mint& rhs) {
return lhs._v == rhs._v;
}
friend bool operator!=(const mint& lhs, const mint& rhs) {
return lhs._v != rhs._v;
}
friend ostream &operator<<(ostream &os, const mint& rhs) {
os << rhs.val(); return os;
}
private:
unsigned int _v;
static internal::barrett bt;
static unsigned int umod() { return bt.umod(); }
};
template <int id> internal::barrett dynamic_modint<id>::bt(998244353);
using modint998244353 = static_modint<998244353>;
using modint1000000007 = static_modint<1000000007>;
using modint = dynamic_modint<-1>;
namespace internal {
template <class T>
using is_static_modint = std::is_base_of<internal::static_modint_base, T>;
template <class T>
using is_static_modint_t = std::enable_if_t<is_static_modint<T>::value>;
template <class> struct is_dynamic_modint : public std::false_type {};
template <int id>
struct is_dynamic_modint<dynamic_modint<id>> : public std::true_type {};
template <class T>
using is_dynamic_modint_t = std::enable_if_t<is_dynamic_modint<T>::value>;
} // namespace internal
} // namespace atcoder
using Mint = atcoder::modint998244353;
using Mint2 = atcoder::modint1000000007;
typedef vector<Mint> vm;
typedef vector<vm> vvm;
typedef vector<vvm> vvvm;
vector<Mint> fac, ifac;
void initFac(int N) {
fac.resize(N + 1);
ifac.resize(N + 1);
fac[0] = ifac[0] = 1;
REP1(i, 1, N + 1) {
fac[i] = fac[i - 1] * i;
}
ifac[N] = 1 / fac[N];
RREP1(i, N - 1, 1) {
ifac[i] = (i + 1) * ifac[i + 1];
}
}
Mint C(int m, int n) {
if (m < n || n < 0) return 0;
return fac[m] * ifac[n] * ifac[m - n];
}
Mint P(int m, int n) {
if (m < n || n < 0) return 0;
return fac[m] * ifac[m - n];
}
vector<vector<Mint>> fastmulti(vector<vector<Mint>> &a, vector<vector<Mint>> &b) {
vector<vector<Mint>> ans(a.size(), vector<Mint>(b[0].size(), Mint(0)));
REP(i, a.size()) {
REP(j, a[0].size()) {
REP(k, b[0].size()) {
ans[i][k] += a[i][j] * b[j][k];
}
}
}
return ans;
}
vector<vector<Mint>> pow(vector<vector<Mint>> &a, ll k) {
vector<vector<Mint>> res(a.size(), vector<Mint>(a.size(), 0)), y = a;
REP(i, a.size()) res[i][i] = 1;
while (k) {
if (k & 1) res = fastmulti(y, res);
y = fastmulti(y, y);
k >>= 1;
}
return res;
}
template< typename Mint >
struct NumberTheoreticTransformFriendlyModInt {
vector< Mint > dw, idw;
int max_base;
Mint root;
NumberTheoreticTransformFriendlyModInt() {
const unsigned mod = Mint::mod();
assert(mod >= 3 && mod % 2 == 1);
auto tmp = mod - 1;
max_base = 0;
while(tmp % 2 == 0) tmp >>= 1, max_base++;
root = 2;
while(root.pow((mod - 1) >> 1) == 1) root += 1;
assert(root.pow(mod - 1) == 1);
dw.resize(max_base);
idw.resize(max_base);
for(int i = 0; i < max_base; i++) {
dw[i] = -root.pow((mod - 1) >> (i + 2));
idw[i] = Mint(1) / dw[i];
}
}
void ntt(vector< Mint > &a) {
const int n = (int) a.size();
assert((n & (n - 1)) == 0);
assert(__builtin_ctz(n) <= max_base);
for(int m = n; m >>= 1;) {
Mint w = 1;
for(int s = 0, k = 0; s < n; s += 2 * m) {
for(int i = s, j = s + m; i < s + m; ++i, ++j) {
auto x = a[i], y = a[j] * w;
a[i] = x + y, a[j] = x - y;
}
w *= dw[__builtin_ctz(++k)];
}
}
}
void intt(vector< Mint > &a, bool f = true) {
const int n = (int) a.size();
assert((n & (n - 1)) == 0);
assert(__builtin_ctz(n) <= max_base);
for(int m = 1; m < n; m *= 2) {
Mint w = 1;
for(int s = 0, k = 0; s < n; s += 2 * m) {
for(int i = s, j = s + m; i < s + m; ++i, ++j) {
auto x = a[i], y = a[j];
a[i] = x + y, a[j] = (x - y) * w;
}
w *= idw[__builtin_ctz(++k)];
}
}
if(f) {
Mint inv_sz = Mint(1) / n;
for(int i = 0; i < n; i++) a[i] *= inv_sz;
}
}
vector< Mint > multiply(vector< Mint > a, vector< Mint > b) {
int need = a.size() + b.size() - 1;
int nbase = 1;
while((1 << nbase) < need) nbase++;
int sz = 1 << nbase;
a.resize(sz, 0);
b.resize(sz, 0);
ntt(a);
ntt(b);
Mint inv_sz = Mint(1) / sz;
for(int i = 0; i < sz; i++) a[i] *= b[i] * inv_sz;
intt(a, false);
a.resize(need);
return a;
}
void sq(vector<Mint> &a, vector<Mint> &b, bool mult) {
int need = a.size() + b.size() - 1;
int nbase = 1;
while((1 << nbase) < need) nbase++;
int sz = 1 << nbase;
b.resize(sz, 0);
ntt(b);
Mint inv_sz = Mint(1) / sz;
if (mult) {
a.resize(sz, 0);
ntt(a);
for(int i = 0; i < sz; i++) a[i] *= b[i] * inv_sz;
intt(a, false);
a.resize(need);
}
for (int i = 0; i < sz; i++) b[i] *= b[i] * inv_sz;
intt(b, false);
b.resize(need);
}
void pow(vector<Mint> &a, vector<Mint> &b, int p) {
int len = a.size();
while (p) {
sq(a, b, p & 1);
a.resize(len);
b.resize(len);
p >>= 1;
}
}
};
NumberTheoreticTransformFriendlyModInt<Mint> ntt;
#define TESTS int t; cin >> t; while (t--)
#define TEST
int main() {
int mx = 1e6;
initFac(mx);
vm dp2(mx + 1, 0), pre2(mx + 1, 0);
dp2[0] = 1; dp2[1] = 0;
pre2[0] = dp2[0] * ifac[0] * ifac[0], pre2[1] = dp2[1] * ifac[1] * ifac[1] + pre2[0];
REP1(i, 2, mx + 1) {
dp2[i] = fac[i] * fac[i - 1] * pre2[i - 2];
pre2[i] = pre2[i - 1] + dp2[i] * ifac[i] * ifac[i];
}
TESTS {
int N;
cin >> N;
Mint ans = 0;
if (N % 2 == 0) ans = 1;
else if (N > 1) {
ans = dp2[N];
}
printf("%d\n", ans.val());
}
return 0;
}
E
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<vll> vvll;
typedef vector<vvll> vvvll;
typedef vector<pii> vpii;
typedef vector<vpii> vvpii;
typedef vector<pll> vpll;
typedef vector<vpll> vvpll;
typedef vector<pdd> vpdd;
typedef vector<vd> vvd;
#define yn(ans) printf("%s\n", (ans)?"Yes":"No");
#define YN(ans) printf("%s\n", (ans)?"YES":"NO");
template<class T> bool chmax(T &a, T b) {
if (a >= b) return false;
a = b; return true;
}
template<class T> bool chmin(T &a, T b) {
if (a <= b) return false;
a = b; return true;
}
#define FOR(i, s, e, t) for ((i) = (s); (i) < (e); (i) += (t))
#define REP(i, e) for (int i = 0; i < (e); ++i)
#define REP1(i, s, e) for (int i = (s); i < (e); ++i)
#define RREP(i, e) for (int i = (e); i >= 0; --i)
#define RREP1(i, e, s) for (int i = (e); i >= (s); --i)
#define all(v) v.begin(), v.end()
#define pb push_back
#define qb pop_back
#define pf push_front
#define qf pop_front
#define maxe max_element
#define mine min_element
ll inf = 1e18;
#define DEBUG printf("%d\n", __LINE__); fflush(stdout);
template<class T> void print(vector<T> &v, bool withSize = false) {
if (withSize) cout << v.size() << endl;
REP(i, v.size()) cout << v[i] << " ";
cout << endl;
}
mt19937_64 rng((unsigned int) chrono::steady_clock::now().time_since_epoch().count());
int __FAST_IO__ = []() {
std::ios::sync_with_stdio(0);
std::cin.tie(0);
std::cout.tie(0);
return 0;
}();
namespace atcoder {
namespace internal {
#ifndef _MSC_VER
template <class T>
using is_signed_int128 =
typename std::conditional<std::is_same<T, __int128_t>::value ||
std::is_same<T, __int128>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_unsigned_int128 =
typename std::conditional<std::is_same<T, __uint128_t>::value ||
std::is_same<T, unsigned __int128>::value,
std::true_type,
std::false_type>::type;
template <class T>
using make_unsigned_int128 =
typename std::conditional<std::is_same<T, __int128_t>::value,
__uint128_t,
unsigned __int128>;
template <class T>
using is_integral = typename std::conditional<std::is_integral<T>::value ||
is_signed_int128<T>::value ||
is_unsigned_int128<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_signed_int = typename std::conditional<(is_integral<T>::value &&
std::is_signed<T>::value) ||
is_signed_int128<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_unsigned_int =
typename std::conditional<(is_integral<T>::value &&
std::is_unsigned<T>::value) ||
is_unsigned_int128<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using to_unsigned = typename std::conditional<
is_signed_int128<T>::value,
make_unsigned_int128<T>,
typename std::conditional<std::is_signed<T>::value,
std::make_unsigned<T>,
std::common_type<T>>::type>::type;
#else
template <class T> using is_integral = typename std::is_integral<T>;
template <class T>
using is_signed_int =
typename std::conditional<is_integral<T>::value && std::is_signed<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_unsigned_int =
typename std::conditional<is_integral<T>::value &&
std::is_unsigned<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using to_unsigned = typename std::conditional<is_signed_int<T>::value,
std::make_unsigned<T>,
std::common_type<T>>::type;
#endif
template <class T>
using is_signed_int_t = std::enable_if_t<is_signed_int<T>::value>;
template <class T>
using is_unsigned_int_t = std::enable_if_t<is_unsigned_int<T>::value>;
template <class T> using to_unsigned_t = typename to_unsigned<T>::type;
} // namespace internal
} // namespace atcoder
namespace atcoder {
namespace internal {
// @param m `1 <= m`
// @return x mod m
constexpr long long safe_mod(long long x, long long m) {
x %= m;
if (x < 0) x += m;
return x;
}
// Fast modular multiplication by barrett reduction
// Reference: https://en.wikipedia.org/wiki/Barrett_reduction
// NOTE: reconsider after Ice Lake
struct barrett {
unsigned int _m;
unsigned long long im;
// @param m `1 <= m`
explicit barrett(unsigned int m) : _m(m), im((unsigned long long)(-1) / m + 1) {}
// @return m
unsigned int umod() const { return _m; }
// @param a `0 <= a < m`
// @param b `0 <= b < m`
// @return `a * b % m`
unsigned int mul(unsigned int a, unsigned int b) const {
// [1] m = 1
// a = b = im = 0, so okay
// [2] m >= 2
// im = ceil(2^64 / m)
// -> im * m = 2^64 + r (0 <= r < m)
// let z = a*b = c*m + d (0 <= c, d < m)
// a*b * im = (c*m + d) * im = c*(im*m) + d*im = c*2^64 + c*r + d*im
// c*r + d*im < m * m + m * im < m * m + 2^64 + m <= 2^64 + m * (m + 1) < 2^64 * 2
// ((ab * im) >> 64) == c or c + 1
unsigned long long z = a;
z *= b;
#ifdef _MSC_VER
unsigned long long x;
_umul128(z, im, &x);
#else
unsigned long long x =
(unsigned long long)(((unsigned __int128)(z)*im) >> 64);
#endif
unsigned long long y = x * _m;
return (unsigned int)(z - y + (z < y ? _m : 0));
}
};
// @param n `0 <= n`
// @param m `1 <= m`
// @return `(x ** n) % m`
constexpr long long pow_mod_constexpr(long long x, long long n, int m) {
if (m == 1) return 0;
unsigned int _m = (unsigned int)(m);
unsigned long long r = 1;
unsigned long long y = safe_mod(x, m);
while (n) {
if (n & 1) r = (r * y) % _m;
y = (y * y) % _m;
n >>= 1;
}
return r;
}
// Reference:
// M. Forisek and J. Jancina,
// Fast Primality Testing for Integers That Fit into a Machine Word
// @param n `0 <= n`
constexpr bool is_prime_constexpr(int n) {
if (n <= 1) return false;
if (n == 2 || n == 7 || n == 61) return true;
if (n % 2 == 0) return false;
long long d = n - 1;
while (d % 2 == 0) d /= 2;
constexpr long long bases[3] = {2, 7, 61};
for (long long a : bases) {
long long t = d;
long long y = pow_mod_constexpr(a, t, n);
while (t != n - 1 && y != 1 && y != n - 1) {
y = y * y % n;
t <<= 1;
}
if (y != n - 1 && t % 2 == 0) {
return false;
}
}
return true;
}
template <int n> constexpr bool is_prime = is_prime_constexpr(n);
// @param b `1 <= b`
// @return pair(g, x) s.t. g = gcd(a, b), xa = g (mod b), 0 <= x < b/g
constexpr std::pair<long long, long long> inv_gcd(long long a, long long b) {
a = safe_mod(a, b);
if (a == 0) return {b, 0};
// Contracts:
// [1] s - m0 * a = 0 (mod b)
// [2] t - m1 * a = 0 (mod b)
// [3] s * |m1| + t * |m0| <= b
long long s = b, t = a;
long long m0 = 0, m1 = 1;
while (t) {
long long u = s / t;
s -= t * u;
m0 -= m1 * u; // |m1 * u| <= |m1| * s <= b
// [3]:
// (s - t * u) * |m1| + t * |m0 - m1 * u|
// <= s * |m1| - t * u * |m1| + t * (|m0| + |m1| * u)
// = s * |m1| + t * |m0| <= b
auto tmp = s;
s = t;
t = tmp;
tmp = m0;
m0 = m1;
m1 = tmp;
}
// by [3]: |m0| <= b/g
// by g != b: |m0| < b/g
if (m0 < 0) m0 += b / s;
return {s, m0};
}
// Compile time primitive root
// @param m must be prime
// @return primitive root (and minimum in now)
constexpr int primitive_root_constexpr(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;
int divs[20] = {};
divs[0] = 2;
int cnt = 1;
int x = (m - 1) / 2;
while (x % 2 == 0) x /= 2;
for (int i = 3; (long long)(i)*i <= x; i += 2) {
if (x % i == 0) {
divs[cnt++] = i;
while (x % i == 0) {
x /= i;
}
}
}
if (x > 1) {
divs[cnt++] = x;
}
for (int g = 2;; g++) {
bool ok = true;
for (int i = 0; i < cnt; i++) {
if (pow_mod_constexpr(g, (m - 1) / divs[i], m) == 1) {
ok = false;
break;
}
}
if (ok) return g;
}
}
template <int m> constexpr int primitive_root = primitive_root_constexpr(m);
// @param n `n < 2^32`
// @param m `1 <= m < 2^32`
// @return sum_{i=0}^{n-1} floor((ai + b) / m) (mod 2^64)
unsigned long long floor_sum_unsigned(unsigned long long n,
unsigned long long m,
unsigned long long a,
unsigned long long b) {
unsigned long long ans = 0;
while (true) {
if (a >= m) {
ans += n * (n - 1) / 2 * (a / m);
a %= m;
}
if (b >= m) {
ans += n * (b / m);
b %= m;
}
unsigned long long y_max = a * n + b;
if (y_max < m) break;
// y_max < m * (n + 1)
// floor(y_max / m) <= n
n = (unsigned long long)(y_max / m);
b = (unsigned long long)(y_max % m);
std::swap(m, a);
}
return ans;
}
} // namespace internal
} // namespace atcoder
namespace atcoder {
namespace internal {
struct modint_base {};
struct static_modint_base : modint_base {};
template <class T> using is_modint = std::is_base_of<modint_base, T>;
template <class T> using is_modint_t = std::enable_if_t<is_modint<T>::value>;
} // namespace internal
template <int m, std::enable_if_t<(1 <= m)>* = nullptr>
struct static_modint : internal::static_modint_base {
using mint = static_modint;
public:
static constexpr int mod() { return m; }
static mint raw(int v) {
mint x;
x._v = v;
return x;
}
static_modint() : _v(0) {}
template <class T, internal::is_signed_int_t<T>* = nullptr>
static_modint(T v) {
long long x = (long long)(v % (long long)(umod()));
if (x < 0) x += umod();
_v = (unsigned int)(x);
}
template <class T, internal::is_unsigned_int_t<T>* = nullptr>
static_modint(T v) {
_v = (unsigned int)(v % umod());
}
unsigned int val() const { return _v; }
mint& operator++() {
_v++;
if (_v == umod()) _v = 0;
return *this;
}
mint& operator--() {
if (_v == 0) _v = umod();
_v--;
return *this;
}
mint operator++(int) {
mint result = *this;
++*this;
return result;
}
mint operator--(int) {
mint result = *this;
--*this;
return result;
}
mint& operator+=(const mint& rhs) {
_v += rhs._v;
if (_v >= umod()) _v -= umod();
return *this;
}
mint& operator-=(const mint& rhs) {
_v -= rhs._v;
if (_v >= umod()) _v += umod();
return *this;
}
mint& operator*=(const mint& rhs) {
unsigned long long z = _v;
z *= rhs._v;
_v = (unsigned int)(z % umod());
return *this;
}
mint& operator/=(const mint& rhs) { return *this = *this * rhs.inv(); }
mint operator+() const { return *this; }
mint operator-() const { return mint() - *this; }
mint pow(long long n) const {
assert(0 <= n);
mint x = *this, r = 1;
while (n) {
if (n & 1) r *= x;
x *= x;
n >>= 1;
}
return r;
}
mint inv() const {
if (prime) {
assert(_v);
return pow(umod() - 2);
} else {
auto eg = internal::inv_gcd(_v, m);
assert(eg.first == 1);
return eg.second;
}
}
friend mint operator+(const mint& lhs, const mint& rhs) {
return mint(lhs) += rhs;
}
friend mint operator-(const mint& lhs, const mint& rhs) {
return mint(lhs) -= rhs;
}
friend mint operator*(const mint& lhs, const mint& rhs) {
return mint(lhs) *= rhs;
}
friend mint operator/(const mint& lhs, const mint& rhs) {
return mint(lhs) /= rhs;
}
friend bool operator==(const mint& lhs, const mint& rhs) {
return lhs._v == rhs._v;
}
friend bool operator!=(const mint& lhs, const mint& rhs) {
return lhs._v != rhs._v;
}
friend ostream &operator<<(ostream &os, const mint& rhs) {
os << rhs.val(); return os;
}
private:
unsigned int _v;
static constexpr unsigned int umod() { return m; }
static constexpr bool prime = internal::is_prime<m>;
};
template <int id> struct dynamic_modint : internal::modint_base {
using mint = dynamic_modint;
public:
static int mod() { return (int)(bt.umod()); }
static void set_mod(int m) {
assert(1 <= m);
bt = internal::barrett(m);
}
static mint raw(int v) {
mint x;
x._v = v;
return x;
}
dynamic_modint() : _v(0) {}
template <class T, internal::is_signed_int_t<T>* = nullptr>
dynamic_modint(T v) {
long long x = (long long)(v % (long long)(mod()));
if (x < 0) x += mod();
_v = (unsigned int)(x);
}
template <class T, internal::is_unsigned_int_t<T>* = nullptr>
dynamic_modint(T v) {
_v = (unsigned int)(v % mod());
}
unsigned int val() const { return _v; }
mint& operator++() {
_v++;
if (_v == umod()) _v = 0;
return *this;
}
mint& operator--() {
if (_v == 0) _v = umod();
_v--;
return *this;
}
mint operator++(int) {
mint result = *this;
++*this;
return result;
}
mint operator--(int) {
mint result = *this;
--*this;
return result;
}
mint& operator+=(const mint& rhs) {
_v += rhs._v;
if (_v >= umod()) _v -= umod();
return *this;
}
mint& operator-=(const mint& rhs) {
_v += mod() - rhs._v;
if (_v >= umod()) _v -= umod();
return *this;
}
mint& operator*=(const mint& rhs) {
_v = bt.mul(_v, rhs._v);
return *this;
}
mint& operator/=(const mint& rhs) { return *this = *this * rhs.inv(); }
mint operator+() const { return *this; }
mint operator-() const { return mint() - *this; }
mint pow(long long n) const {
assert(0 <= n);
mint x = *this, r = 1;
while (n) {
if (n & 1) r *= x;
x *= x;
n >>= 1;
}
return r;
}
mint inv() const {
auto eg = internal::inv_gcd(_v, mod());
assert(eg.first == 1);
return eg.second;
}
friend mint operator+(const mint& lhs, const mint& rhs) {
return mint(lhs) += rhs;
}
friend mint operator-(const mint& lhs, const mint& rhs) {
return mint(lhs) -= rhs;
}
friend mint operator*(const mint& lhs, const mint& rhs) {
return mint(lhs) *= rhs;
}
friend mint operator/(const mint& lhs, const mint& rhs) {
return mint(lhs) /= rhs;
}
friend bool operator==(const mint& lhs, const mint& rhs) {
return lhs._v == rhs._v;
}
friend bool operator!=(const mint& lhs, const mint& rhs) {
return lhs._v != rhs._v;
}
friend ostream &operator<<(ostream &os, const mint& rhs) {
os << rhs.val(); return os;
}
private:
unsigned int _v;
static internal::barrett bt;
static unsigned int umod() { return bt.umod(); }
};
template <int id> internal::barrett dynamic_modint<id>::bt(998244353);
using modint998244353 = static_modint<998244353>;
using modint1000000007 = static_modint<1000000007>;
using modint = dynamic_modint<-1>;
namespace internal {
template <class T>
using is_static_modint = std::is_base_of<internal::static_modint_base, T>;
template <class T>
using is_static_modint_t = std::enable_if_t<is_static_modint<T>::value>;
template <class> struct is_dynamic_modint : public std::false_type {};
template <int id>
struct is_dynamic_modint<dynamic_modint<id>> : public std::true_type {};
template <class T>
using is_dynamic_modint_t = std::enable_if_t<is_dynamic_modint<T>::value>;
} // namespace internal
} // namespace atcoder
using Mint2 = atcoder::modint998244353;
using Mint = atcoder::modint1000000007;
typedef vector<Mint> vm;
typedef vector<vm> vvm;
typedef vector<vvm> vvvm;
vector<Mint> fac, ifac;
void initFac(int N) {
fac.resize(N + 1);
ifac.resize(N + 1);
fac[0] = ifac[0] = 1;
REP1(i, 1, N + 1) {
fac[i] = fac[i - 1] * i;
}
ifac[N] = 1 / fac[N];
RREP1(i, N - 1, 1) {
ifac[i] = (i + 1) * ifac[i + 1];
}
}
Mint C(int m, int n) {
if (m < n || n < 0) return 0;
return fac[m] * ifac[n] * ifac[m - n];
}
Mint P(int m, int n) {
if (m < n || n < 0) return 0;
return fac[m] * ifac[m - n];
}
vector<vector<Mint>> fastmulti(vector<vector<Mint>> &a, vector<vector<Mint>> &b) {
vector<vector<Mint>> ans(a.size(), vector<Mint>(b[0].size(), Mint(0)));
REP(i, a.size()) {
REP(j, a[0].size()) {
REP(k, b[0].size()) {
ans[i][k] += a[i][j] * b[j][k];
}
}
}
return ans;
}
vector<vector<Mint>> pow(vector<vector<Mint>> &a, ll k) {
vector<vector<Mint>> res(a.size(), vector<Mint>(a.size(), 0)), y = a;
REP(i, a.size()) res[i][i] = 1;
while (k) {
if (k & 1) res = fastmulti(y, res);
y = fastmulti(y, y);
k >>= 1;
}
return res;
}
template< typename Mint >
struct NumberTheoreticTransformFriendlyModInt {
vector< Mint > dw, idw;
int max_base;
Mint root;
NumberTheoreticTransformFriendlyModInt() {
const unsigned mod = Mint::mod();
assert(mod >= 3 && mod % 2 == 1);
auto tmp = mod - 1;
max_base = 0;
while(tmp % 2 == 0) tmp >>= 1, max_base++;
root = 2;
while(root.pow((mod - 1) >> 1) == 1) root += 1;
assert(root.pow(mod - 1) == 1);
dw.resize(max_base);
idw.resize(max_base);
for(int i = 0; i < max_base; i++) {
dw[i] = -root.pow((mod - 1) >> (i + 2));
idw[i] = Mint(1) / dw[i];
}
}
void ntt(vector< Mint > &a) {
const int n = (int) a.size();
assert((n & (n - 1)) == 0);
assert(__builtin_ctz(n) <= max_base);
for(int m = n; m >>= 1;) {
Mint w = 1;
for(int s = 0, k = 0; s < n; s += 2 * m) {
for(int i = s, j = s + m; i < s + m; ++i, ++j) {
auto x = a[i], y = a[j] * w;
a[i] = x + y, a[j] = x - y;
}
w *= dw[__builtin_ctz(++k)];
}
}
}
void intt(vector< Mint > &a, bool f = true) {
const int n = (int) a.size();
assert((n & (n - 1)) == 0);
assert(__builtin_ctz(n) <= max_base);
for(int m = 1; m < n; m *= 2) {
Mint w = 1;
for(int s = 0, k = 0; s < n; s += 2 * m) {
for(int i = s, j = s + m; i < s + m; ++i, ++j) {
auto x = a[i], y = a[j];
a[i] = x + y, a[j] = (x - y) * w;
}
w *= idw[__builtin_ctz(++k)];
}
}
if(f) {
Mint inv_sz = Mint(1) / n;
for(int i = 0; i < n; i++) a[i] *= inv_sz;
}
}
vector< Mint > multiply(vector< Mint > a, vector< Mint > b) {
int need = a.size() + b.size() - 1;
int nbase = 1;
while((1 << nbase) < need) nbase++;
int sz = 1 << nbase;
a.resize(sz, 0);
b.resize(sz, 0);
ntt(a);
ntt(b);
Mint inv_sz = Mint(1) / sz;
for(int i = 0; i < sz; i++) a[i] *= b[i] * inv_sz;
intt(a, false);
a.resize(need);
return a;
}
void sq(vector<Mint> &a, vector<Mint> &b, bool mult) {
int need = a.size() + b.size() - 1;
int nbase = 1;
while((1 << nbase) < need) nbase++;
int sz = 1 << nbase;
b.resize(sz, 0);
ntt(b);
Mint inv_sz = Mint(1) / sz;
if (mult) {
a.resize(sz, 0);
ntt(a);
for(int i = 0; i < sz; i++) a[i] *= b[i] * inv_sz;
intt(a, false);
a.resize(need);
}
for (int i = 0; i < sz; i++) b[i] *= b[i] * inv_sz;
intt(b, false);
b.resize(need);
}
void pow(vector<Mint> &a, vector<Mint> &b, int p) {
int len = a.size();
while (p) {
sq(a, b, p & 1);
a.resize(len);
b.resize(len);
p >>= 1;
}
}
};
NumberTheoreticTransformFriendlyModInt<Mint> ntt;
#define TESTS int t; cin >> t; while (t--)
#define TEST
int main() {
vvi p(21, vi(8, 0));
vi pr = {2,3,5,7,11,13,17,19};
REP1(i, 1, 21) {
REP(j, 8) {
int k = i;
while (k % pr[j] == 0) k /= pr[j], p[i][j]++;
}
}
TESTS {
int N;
cin >> N;
vi A(N);
REP(i, N) cin >> A[i];
vi cnt(8, 0);
vm pre(1 << 8, 0);
pre[0] = 1;
Mint ans = 0;
REP(i, N) {
REP(j, 8) cnt[j] += p[A[i]][j];
REP(j, 1 << 8) {
int x = __builtin_popcount(j);
Mint prod = 1;
REP(k, 8) {
if (!(j >> k & 1)) prod *= cnt[k] + 1;
}
prod *= pre[j];
ans += (x % 2 == 0 ? 1 : -1) * prod;
}
REP(j, 1 << 8) {
Mint prod = 1;
REP(k, 8) {
if (j >> k & 1) prod *= cnt[k];
}
pre[j] += prod;
}
}
printf("%d\n", ans.val());
}
return 0;
}
serialcomder
A
#include <bits/stdc++.h>
using namespace std;
#define int int64_t
void solve() {
int n; cin >> n;
cout << n << '\n';
}
int32_t main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1;
cin >> T;
while (T--) solve();
return 0;
}
B
#include <bits/stdc++.h>
using namespace std;
#define int int64_t
void solve() {
int n, x; cin >> n >> x;
int val = x, ans = 0;
priority_queue<int> pq;
vector<int> c(n), a(n);
for (auto &i : c) cin >> i;
for (auto &i : a) cin >> i;
for (int i = 0; i < n; i++) {
val -= c[i];
pq.push(c[i]);
while (val < 0) {
ans++;
val += pq.top();
pq.pop();
}
val += a[i];
}
cout << ans << '\n';
}
int32_t main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1;
cin >> T;
while (T--) solve();
return 0;
}
C
#include <bits/stdc++.h>
using namespace std;
#define int int64_t
void solve() {
int n, ans = 0; cin >> n;
for (int i = 1; i * i <= n; i++) {
if (n % i == 0) {
ans += (i - 1);
if (i != n / i) ans += (n / i - 1);
}
}
cout << ans << '\n';
}
int32_t main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1;
cin >> T;
while (T--) solve();
return 0;
}
D
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<vll> vvll;
typedef vector<vvll> vvvll;
typedef vector<pii> vpii;
typedef vector<vpii> vvpii;
typedef vector<pll> vpll;
typedef vector<vpll> vvpll;
typedef vector<pdd> vpdd;
typedef vector<vd> vvd;
#define yn(ans) printf("%s\n", (ans)?"Yes":"No");
#define YN(ans) printf("%s\n", (ans)?"YES":"NO");
template<class T> bool chmax(T &a, T b) {
if (a >= b) return false;
a = b; return true;
}
template<class T> bool chmin(T &a, T b) {
if (a <= b) return false;
a = b; return true;
}
#define FOR(i, s, e, t) for ((i) = (s); (i) < (e); (i) += (t))
#define REP(i, e) for (int i = 0; i < (e); ++i)
#define REP1(i, s, e) for (int i = (s); i < (e); ++i)
#define RREP(i, e) for (int i = (e); i >= 0; --i)
#define RREP1(i, e, s) for (int i = (e); i >= (s); --i)
#define all(v) v.begin(), v.end()
#define pb push_back
#define qb pop_back
#define pf push_front
#define qf pop_front
#define maxe max_element
#define mine min_element
ll inf = 1e18;
#define DEBUG printf("%d\n", __LINE__); fflush(stdout);
template<class T> void print(vector<T> &v, bool withSize = false) {
if (withSize) cout << v.size() << endl;
REP(i, v.size()) cout << v[i] << " ";
cout << endl;
}
mt19937_64 rng((unsigned int) chrono::steady_clock::now().time_since_epoch().count());
int __FAST_IO__ = []() {
std::ios::sync_with_stdio(0);
std::cin.tie(0);
std::cout.tie(0);
return 0;
}();
namespace atcoder {
namespace internal {
#ifndef _MSC_VER
template <class T>
using is_signed_int128 =
typename std::conditional<std::is_same<T, __int128_t>::value ||
std::is_same<T, __int128>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_unsigned_int128 =
typename std::conditional<std::is_same<T, __uint128_t>::value ||
std::is_same<T, unsigned __int128>::value,
std::true_type,
std::false_type>::type;
template <class T>
using make_unsigned_int128 =
typename std::conditional<std::is_same<T, __int128_t>::value,
__uint128_t,
unsigned __int128>;
template <class T>
using is_integral = typename std::conditional<std::is_integral<T>::value ||
is_signed_int128<T>::value ||
is_unsigned_int128<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_signed_int = typename std::conditional<(is_integral<T>::value &&
std::is_signed<T>::value) ||
is_signed_int128<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_unsigned_int =
typename std::conditional<(is_integral<T>::value &&
std::is_unsigned<T>::value) ||
is_unsigned_int128<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using to_unsigned = typename std::conditional<
is_signed_int128<T>::value,
make_unsigned_int128<T>,
typename std::conditional<std::is_signed<T>::value,
std::make_unsigned<T>,
std::common_type<T>>::type>::type;
#else
template <class T> using is_integral = typename std::is_integral<T>;
template <class T>
using is_signed_int =
typename std::conditional<is_integral<T>::value && std::is_signed<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_unsigned_int =
typename std::conditional<is_integral<T>::value &&
std::is_unsigned<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using to_unsigned = typename std::conditional<is_signed_int<T>::value,
std::make_unsigned<T>,
std::common_type<T>>::type;
#endif
template <class T>
using is_signed_int_t = std::enable_if_t<is_signed_int<T>::value>;
template <class T>
using is_unsigned_int_t = std::enable_if_t<is_unsigned_int<T>::value>;
template <class T> using to_unsigned_t = typename to_unsigned<T>::type;
} // namespace internal
} // namespace atcoder
namespace atcoder {
namespace internal {
// @param m `1 <= m`
// @return x mod m
constexpr long long safe_mod(long long x, long long m) {
x %= m;
if (x < 0) x += m;
return x;
}
// Fast modular multiplication by barrett reduction
// Reference: https://en.wikipedia.org/wiki/Barrett_reduction
// NOTE: reconsider after Ice Lake
struct barrett {
unsigned int _m;
unsigned long long im;
// @param m `1 <= m`
explicit barrett(unsigned int m) : _m(m), im((unsigned long long)(-1) / m + 1) {}
// @return m
unsigned int umod() const { return _m; }
// @param a `0 <= a < m`
// @param b `0 <= b < m`
// @return `a * b % m`
unsigned int mul(unsigned int a, unsigned int b) const {
// [1] m = 1
// a = b = im = 0, so okay
// [2] m >= 2
// im = ceil(2^64 / m)
// -> im * m = 2^64 + r (0 <= r < m)
// let z = a*b = c*m + d (0 <= c, d < m)
// a*b * im = (c*m + d) * im = c*(im*m) + d*im = c*2^64 + c*r + d*im
// c*r + d*im < m * m + m * im < m * m + 2^64 + m <= 2^64 + m * (m + 1) < 2^64 * 2
// ((ab * im) >> 64) == c or c + 1
unsigned long long z = a;
z *= b;
#ifdef _MSC_VER
unsigned long long x;
_umul128(z, im, &x);
#else
unsigned long long x =
(unsigned long long)(((unsigned __int128)(z)*im) >> 64);
#endif
unsigned long long y = x * _m;
return (unsigned int)(z - y + (z < y ? _m : 0));
}
};
// @param n `0 <= n`
// @param m `1 <= m`
// @return `(x ** n) % m`
constexpr long long pow_mod_constexpr(long long x, long long n, int m) {
if (m == 1) return 0;
unsigned int _m = (unsigned int)(m);
unsigned long long r = 1;
unsigned long long y = safe_mod(x, m);
while (n) {
if (n & 1) r = (r * y) % _m;
y = (y * y) % _m;
n >>= 1;
}
return r;
}
// Reference:
// M. Forisek and J. Jancina,
// Fast Primality Testing for Integers That Fit into a Machine Word
// @param n `0 <= n`
constexpr bool is_prime_constexpr(int n) {
if (n <= 1) return false;
if (n == 2 || n == 7 || n == 61) return true;
if (n % 2 == 0) return false;
long long d = n - 1;
while (d % 2 == 0) d /= 2;
constexpr long long bases[3] = {2, 7, 61};
for (long long a : bases) {
long long t = d;
long long y = pow_mod_constexpr(a, t, n);
while (t != n - 1 && y != 1 && y != n - 1) {
y = y * y % n;
t <<= 1;
}
if (y != n - 1 && t % 2 == 0) {
return false;
}
}
return true;
}
template <int n> constexpr bool is_prime = is_prime_constexpr(n);
// @param b `1 <= b`
// @return pair(g, x) s.t. g = gcd(a, b), xa = g (mod b), 0 <= x < b/g
constexpr std::pair<long long, long long> inv_gcd(long long a, long long b) {
a = safe_mod(a, b);
if (a == 0) return {b, 0};
// Contracts:
// [1] s - m0 * a = 0 (mod b)
// [2] t - m1 * a = 0 (mod b)
// [3] s * |m1| + t * |m0| <= b
long long s = b, t = a;
long long m0 = 0, m1 = 1;
while (t) {
long long u = s / t;
s -= t * u;
m0 -= m1 * u; // |m1 * u| <= |m1| * s <= b
// [3]:
// (s - t * u) * |m1| + t * |m0 - m1 * u|
// <= s * |m1| - t * u * |m1| + t * (|m0| + |m1| * u)
// = s * |m1| + t * |m0| <= b
auto tmp = s;
s = t;
t = tmp;
tmp = m0;
m0 = m1;
m1 = tmp;
}
// by [3]: |m0| <= b/g
// by g != b: |m0| < b/g
if (m0 < 0) m0 += b / s;
return {s, m0};
}
// Compile time primitive root
// @param m must be prime
// @return primitive root (and minimum in now)
constexpr int primitive_root_constexpr(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;
int divs[20] = {};
divs[0] = 2;
int cnt = 1;
int x = (m - 1) / 2;
while (x % 2 == 0) x /= 2;
for (int i = 3; (long long)(i)*i <= x; i += 2) {
if (x % i == 0) {
divs[cnt++] = i;
while (x % i == 0) {
x /= i;
}
}
}
if (x > 1) {
divs[cnt++] = x;
}
for (int g = 2;; g++) {
bool ok = true;
for (int i = 0; i < cnt; i++) {
if (pow_mod_constexpr(g, (m - 1) / divs[i], m) == 1) {
ok = false;
break;
}
}
if (ok) return g;
}
}
template <int m> constexpr int primitive_root = primitive_root_constexpr(m);
// @param n `n < 2^32`
// @param m `1 <= m < 2^32`
// @return sum_{i=0}^{n-1} floor((ai + b) / m) (mod 2^64)
unsigned long long floor_sum_unsigned(unsigned long long n,
unsigned long long m,
unsigned long long a,
unsigned long long b) {
unsigned long long ans = 0;
while (true) {
if (a >= m) {
ans += n * (n - 1) / 2 * (a / m);
a %= m;
}
if (b >= m) {
ans += n * (b / m);
b %= m;
}
unsigned long long y_max = a * n + b;
if (y_max < m) break;
// y_max < m * (n + 1)
// floor(y_max / m) <= n
n = (unsigned long long)(y_max / m);
b = (unsigned long long)(y_max % m);
std::swap(m, a);
}
return ans;
}
} // namespace internal
} // namespace atcoder
namespace atcoder {
namespace internal {
struct modint_base {};
struct static_modint_base : modint_base {};
template <class T> using is_modint = std::is_base_of<modint_base, T>;
template <class T> using is_modint_t = std::enable_if_t<is_modint<T>::value>;
} // namespace internal
template <int m, std::enable_if_t<(1 <= m)>* = nullptr>
struct static_modint : internal::static_modint_base {
using mint = static_modint;
public:
static constexpr int mod() { return m; }
static mint raw(int v) {
mint x;
x._v = v;
return x;
}
static_modint() : _v(0) {}
template <class T, internal::is_signed_int_t<T>* = nullptr>
static_modint(T v) {
long long x = (long long)(v % (long long)(umod()));
if (x < 0) x += umod();
_v = (unsigned int)(x);
}
template <class T, internal::is_unsigned_int_t<T>* = nullptr>
static_modint(T v) {
_v = (unsigned int)(v % umod());
}
unsigned int val() const { return _v; }
mint& operator++() {
_v++;
if (_v == umod()) _v = 0;
return *this;
}
mint& operator--() {
if (_v == 0) _v = umod();
_v--;
return *this;
}
mint operator++(int) {
mint result = *this;
++*this;
return result;
}
mint operator--(int) {
mint result = *this;
--*this;
return result;
}
mint& operator+=(const mint& rhs) {
_v += rhs._v;
if (_v >= umod()) _v -= umod();
return *this;
}
mint& operator-=(const mint& rhs) {
_v -= rhs._v;
if (_v >= umod()) _v += umod();
return *this;
}
mint& operator*=(const mint& rhs) {
unsigned long long z = _v;
z *= rhs._v;
_v = (unsigned int)(z % umod());
return *this;
}
mint& operator/=(const mint& rhs) { return *this = *this * rhs.inv(); }
mint operator+() const { return *this; }
mint operator-() const { return mint() - *this; }
mint pow(long long n) const {
assert(0 <= n);
mint x = *this, r = 1;
while (n) {
if (n & 1) r *= x;
x *= x;
n >>= 1;
}
return r;
}
mint inv() const {
if (prime) {
assert(_v);
return pow(umod() - 2);
} else {
auto eg = internal::inv_gcd(_v, m);
assert(eg.first == 1);
return eg.second;
}
}
friend mint operator+(const mint& lhs, const mint& rhs) {
return mint(lhs) += rhs;
}
friend mint operator-(const mint& lhs, const mint& rhs) {
return mint(lhs) -= rhs;
}
friend mint operator*(const mint& lhs, const mint& rhs) {
return mint(lhs) *= rhs;
}
friend mint operator/(const mint& lhs, const mint& rhs) {
return mint(lhs) /= rhs;
}
friend bool operator==(const mint& lhs, const mint& rhs) {
return lhs._v == rhs._v;
}
friend bool operator!=(const mint& lhs, const mint& rhs) {
return lhs._v != rhs._v;
}
friend ostream &operator<<(ostream &os, const mint& rhs) {
os << rhs.val(); return os;
}
private:
unsigned int _v;
static constexpr unsigned int umod() { return m; }
static constexpr bool prime = internal::is_prime<m>;
};
template <int id> struct dynamic_modint : internal::modint_base {
using mint = dynamic_modint;
public:
static int mod() { return (int)(bt.umod()); }
static void set_mod(int m) {
assert(1 <= m);
bt = internal::barrett(m);
}
static mint raw(int v) {
mint x;
x._v = v;
return x;
}
dynamic_modint() : _v(0) {}
template <class T, internal::is_signed_int_t<T>* = nullptr>
dynamic_modint(T v) {
long long x = (long long)(v % (long long)(mod()));
if (x < 0) x += mod();
_v = (unsigned int)(x);
}
template <class T, internal::is_unsigned_int_t<T>* = nullptr>
dynamic_modint(T v) {
_v = (unsigned int)(v % mod());
}
unsigned int val() const { return _v; }
mint& operator++() {
_v++;
if (_v == umod()) _v = 0;
return *this;
}
mint& operator--() {
if (_v == 0) _v = umod();
_v--;
return *this;
}
mint operator++(int) {
mint result = *this;
++*this;
return result;
}
mint operator--(int) {
mint result = *this;
--*this;
return result;
}
mint& operator+=(const mint& rhs) {
_v += rhs._v;
if (_v >= umod()) _v -= umod();
return *this;
}
mint& operator-=(const mint& rhs) {
_v += mod() - rhs._v;
if (_v >= umod()) _v -= umod();
return *this;
}
mint& operator*=(const mint& rhs) {
_v = bt.mul(_v, rhs._v);
return *this;
}
mint& operator/=(const mint& rhs) { return *this = *this * rhs.inv(); }
mint operator+() const { return *this; }
mint operator-() const { return mint() - *this; }
mint pow(long long n) const {
assert(0 <= n);
mint x = *this, r = 1;
while (n) {
if (n & 1) r *= x;
x *= x;
n >>= 1;
}
return r;
}
mint inv() const {
auto eg = internal::inv_gcd(_v, mod());
assert(eg.first == 1);
return eg.second;
}
friend mint operator+(const mint& lhs, const mint& rhs) {
return mint(lhs) += rhs;
}
friend mint operator-(const mint& lhs, const mint& rhs) {
return mint(lhs) -= rhs;
}
friend mint operator*(const mint& lhs, const mint& rhs) {
return mint(lhs) *= rhs;
}
friend mint operator/(const mint& lhs, const mint& rhs) {
return mint(lhs) /= rhs;
}
friend bool operator==(const mint& lhs, const mint& rhs) {
return lhs._v == rhs._v;
}
friend bool operator!=(const mint& lhs, const mint& rhs) {
return lhs._v != rhs._v;
}
friend ostream &operator<<(ostream &os, const mint& rhs) {
os << rhs.val(); return os;
}
private:
unsigned int _v;
static internal::barrett bt;
static unsigned int umod() { return bt.umod(); }
};
template <int id> internal::barrett dynamic_modint<id>::bt(998244353);
using modint998244353 = static_modint<998244353>;
using modint1000000007 = static_modint<1000000007>;
using modint = dynamic_modint<-1>;
namespace internal {
template <class T>
using is_static_modint = std::is_base_of<internal::static_modint_base, T>;
template <class T>
using is_static_modint_t = std::enable_if_t<is_static_modint<T>::value>;
template <class> struct is_dynamic_modint : public std::false_type {};
template <int id>
struct is_dynamic_modint<dynamic_modint<id>> : public std::true_type {};
template <class T>
using is_dynamic_modint_t = std::enable_if_t<is_dynamic_modint<T>::value>;
} // namespace internal
} // namespace atcoder
using Mint = atcoder::modint998244353;
using Mint2 = atcoder::modint1000000007;
typedef vector<Mint> vm;
typedef vector<vm> vvm;
typedef vector<vvm> vvvm;
vector<Mint> fac, ifac;
void initFac(int N) {
fac.resize(N + 1);
ifac.resize(N + 1);
fac[0] = ifac[0] = 1;
REP1(i, 1, N + 1) {
fac[i] = fac[i - 1] * i;
}
ifac[N] = 1 / fac[N];
RREP1(i, N - 1, 1) {
ifac[i] = (i + 1) * ifac[i + 1];
}
}
Mint C(int m, int n) {
if (m < n || n < 0) return 0;
return fac[m] * ifac[n] * ifac[m - n];
}
Mint P(int m, int n) {
if (m < n || n < 0) return 0;
return fac[m] * ifac[m - n];
}
vector<vector<Mint>> fastmulti(vector<vector<Mint>> &a, vector<vector<Mint>> &b) {
vector<vector<Mint>> ans(a.size(), vector<Mint>(b[0].size(), Mint(0)));
REP(i, a.size()) {
REP(j, a[0].size()) {
REP(k, b[0].size()) {
ans[i][k] += a[i][j] * b[j][k];
}
}
}
return ans;
}
vector<vector<Mint>> pow(vector<vector<Mint>> &a, ll k) {
vector<vector<Mint>> res(a.size(), vector<Mint>(a.size(), 0)), y = a;
REP(i, a.size()) res[i][i] = 1;
while (k) {
if (k & 1) res = fastmulti(y, res);
y = fastmulti(y, y);
k >>= 1;
}
return res;
}
template< typename Mint >
struct NumberTheoreticTransformFriendlyModInt {
vector< Mint > dw, idw;
int max_base;
Mint root;
NumberTheoreticTransformFriendlyModInt() {
const unsigned mod = Mint::mod();
assert(mod >= 3 && mod % 2 == 1);
auto tmp = mod - 1;
max_base = 0;
while(tmp % 2 == 0) tmp >>= 1, max_base++;
root = 2;
while(root.pow((mod - 1) >> 1) == 1) root += 1;
assert(root.pow(mod - 1) == 1);
dw.resize(max_base);
idw.resize(max_base);
for(int i = 0; i < max_base; i++) {
dw[i] = -root.pow((mod - 1) >> (i + 2));
idw[i] = Mint(1) / dw[i];
}
}
void ntt(vector< Mint > &a) {
const int n = (int) a.size();
assert((n & (n - 1)) == 0);
assert(__builtin_ctz(n) <= max_base);
for(int m = n; m >>= 1;) {
Mint w = 1;
for(int s = 0, k = 0; s < n; s += 2 * m) {
for(int i = s, j = s + m; i < s + m; ++i, ++j) {
auto x = a[i], y = a[j] * w;
a[i] = x + y, a[j] = x - y;
}
w *= dw[__builtin_ctz(++k)];
}
}
}
void intt(vector< Mint > &a, bool f = true) {
const int n = (int) a.size();
assert((n & (n - 1)) == 0);
assert(__builtin_ctz(n) <= max_base);
for(int m = 1; m < n; m *= 2) {
Mint w = 1;
for(int s = 0, k = 0; s < n; s += 2 * m) {
for(int i = s, j = s + m; i < s + m; ++i, ++j) {
auto x = a[i], y = a[j];
a[i] = x + y, a[j] = (x - y) * w;
}
w *= idw[__builtin_ctz(++k)];
}
}
if(f) {
Mint inv_sz = Mint(1) / n;
for(int i = 0; i < n; i++) a[i] *= inv_sz;
}
}
vector< Mint > multiply(vector< Mint > a, vector< Mint > b) {
int need = a.size() + b.size() - 1;
int nbase = 1;
while((1 << nbase) < need) nbase++;
int sz = 1 << nbase;
a.resize(sz, 0);
b.resize(sz, 0);
ntt(a);
ntt(b);
Mint inv_sz = Mint(1) / sz;
for(int i = 0; i < sz; i++) a[i] *= b[i] * inv_sz;
intt(a, false);
a.resize(need);
return a;
}
void sq(vector<Mint> &a, vector<Mint> &b, bool mult) {
int need = a.size() + b.size() - 1;
int nbase = 1;
while((1 << nbase) < need) nbase++;
int sz = 1 << nbase;
b.resize(sz, 0);
ntt(b);
Mint inv_sz = Mint(1) / sz;
if (mult) {
a.resize(sz, 0);
ntt(a);
for(int i = 0; i < sz; i++) a[i] *= b[i] * inv_sz;
intt(a, false);
a.resize(need);
}
for (int i = 0; i < sz; i++) b[i] *= b[i] * inv_sz;
intt(b, false);
b.resize(need);
}
void pow(vector<Mint> &a, vector<Mint> &b, int p) {
int len = a.size();
while (p) {
sq(a, b, p & 1);
a.resize(len);
b.resize(len);
p >>= 1;
}
}
};
NumberTheoreticTransformFriendlyModInt<Mint> ntt;
#define TESTS int t; cin >> t; while (t--)
#define TEST
int main() {
int mx = 1e6;
initFac(mx);
vm dp2(mx + 1, 0), pre2(mx + 1, 0);
dp2[0] = 1; dp2[1] = 0;
pre2[0] = dp2[0] * ifac[0] * ifac[0], pre2[1] = dp2[1] * ifac[1] * ifac[1] + pre2[0];
REP1(i, 2, mx + 1) {
dp2[i] = fac[i] * fac[i - 1] * pre2[i - 2];
pre2[i] = pre2[i - 1] + dp2[i] * ifac[i] * ifac[i];
}
TESTS {
int N;
cin >> N;
Mint ans = 0;
if (N % 2 == 0) ans = 1;
else if (N > 1) {
ans = dp2[N];
}
printf("%d\n", ans.val());
}
return 0;
}
E
#include <bits/stdc++.h>
using namespace std;
#ifndef ONLINE_JUDGE
#include "db/debug.h"
#else
#define debug(...)
#endif
/*https://github.com/nealwu/competitive-programming/blob/master/mod/mod_int.cc*/
template<const int64_t &MOD>
struct _m_int {
int val;
_m_int(int64_t v = 0) {
if (v < 0) v = v % MOD + MOD;
if (v >= MOD) v %= MOD;
val = int(v);
}
_m_int(uint64_t v) {
if (v >= MOD) v %= MOD;
val = int(v);
}
_m_int(int v) : _m_int(int64_t(v)) {}
_m_int(unsigned v) : _m_int(uint64_t(v)) {}
explicit operator int() const { return val; }
explicit operator unsigned() const { return val; }
explicit operator int64_t() const { return val; }
explicit operator uint64_t() const { return val; }
explicit operator double() const { return val; }
explicit operator long double() const { return val; }
_m_int& operator+=(const _m_int &other) {
val -= MOD - other.val;
if (val < 0) val += MOD;
return *this;
}
_m_int& operator-=(const _m_int &other) {
val -= other.val;
if (val < 0) val += MOD;
return *this;
}
static unsigned fast_mod(uint64_t x, unsigned m = MOD) {
#if !defined(_WIN32) || defined(_WIN64)
return unsigned(x % m);
#endif
// Optimized mod for Codeforces 32-bit machines.
// x must be less than 2^32 * m for this to work, so that x / m fits in an unsigned 32-bit int.
unsigned x_high = unsigned(x >> 32), x_low = unsigned(x);
unsigned quot, rem;
asm("divl %4\n"
: "=a" (quot), "=d" (rem)
: "d" (x_high), "a" (x_low), "r" (m));
return rem;
}
_m_int& operator*=(const _m_int &other) {
val = fast_mod(uint64_t(val) * other.val);
return *this;
}
_m_int& operator/=(const _m_int &other) {
return *this *= other.inv();
}
friend _m_int operator+(const _m_int &a, const _m_int &b) { return _m_int(a) += b; }
friend _m_int operator-(const _m_int &a, const _m_int &b) { return _m_int(a) -= b; }
friend _m_int operator*(const _m_int &a, const _m_int &b) { return _m_int(a) *= b; }
friend _m_int operator/(const _m_int &a, const _m_int &b) { return _m_int(a) /= b; }
_m_int& operator++() {
val = val == MOD - 1 ? 0 : val + 1;
return *this;
}
_m_int& operator--() {
val = val == 0 ? MOD - 1 : val - 1;
return *this;
}
_m_int operator++(int) { _m_int before = *this; ++*this; return before; }
_m_int operator--(int) { _m_int before = *this; --*this; return before; }
_m_int operator-() const {
return val == 0 ? 0 : MOD - val;
}
friend bool operator==(const _m_int &a, const _m_int &b) { return a.val == b.val; }
friend bool operator!=(const _m_int &a, const _m_int &b) { return a.val != b.val; }
friend bool operator<(const _m_int &a, const _m_int &b) { return a.val < b.val; }
friend bool operator>(const _m_int &a, const _m_int &b) { return a.val > b.val; }
friend bool operator<=(const _m_int &a, const _m_int &b) { return a.val <= b.val; }
friend bool operator>=(const _m_int &a, const _m_int &b) { return a.val >= b.val; }
static const int SAVE_INV = int(1e6) + 5;
static _m_int save_inv[SAVE_INV];
static void prepare_inv() {
// Ensures that MOD is prime, which is necessary for the inverse algorithm below.
for (int64_t p = 2; p * p <= MOD; p += p % 2 + 1)
assert(MOD % p != 0);
save_inv[0] = 0;
save_inv[1] = 1;
for (int i = 2; i < SAVE_INV; i++)
save_inv[i] = save_inv[MOD % i] * (MOD - MOD / i);
}
_m_int inv() const {
if (save_inv[1] == 0)
prepare_inv();
if (val < SAVE_INV)
return save_inv[val];
_m_int product = 1;
int v = val;
do {
product *= MOD - MOD / v;
v = MOD % v;
} while (v >= SAVE_INV);
return product * save_inv[v];
}
_m_int pow(int64_t p) const {
if (p < 0)
return inv().pow(-p);
_m_int a = *this, result = 1;
while (p > 0) {
if (p & 1)
result *= a;
p >>= 1;
if (p > 0)
a *= a;
}
return result;
}
friend ostream& operator<<(ostream &os, const _m_int &m) {
return os << m.val;
}
};
template<const int64_t &MOD> _m_int<MOD> _m_int<MOD>::save_inv[_m_int<MOD>::SAVE_INV];
// const int64_t mod = 998244353;
const int64_t mod = int(1e9) + 7;
//const int64_t mod = 29996224275833;
using mod_int = _m_int<mod>;
vector<mod_int> _factorial = {1}, _inv_factorial = {1};
void prepare_factorials(int64_t maximum) {
static int64_t prepared_maximum = 0;
if (maximum <= prepared_maximum)
return;
// Prevent increasing maximum by only 1 each time.
maximum += maximum / 100;
_factorial.resize(maximum + 1);
_inv_factorial.resize(maximum + 1);
for (int64_t i = prepared_maximum + 1; i <= maximum; i++)
_factorial[i] = i * _factorial[i - 1];
_inv_factorial[maximum] = _factorial[maximum].inv();
for (int64_t i = maximum - 1; i > prepared_maximum; i--)
_inv_factorial[i] = (i + 1) * _inv_factorial[i + 1];
prepared_maximum = maximum;
}
mod_int factorial(int64_t n) {
if (n < 0) return 0;
prepare_factorials(n);
return _factorial[n];
}
mod_int inv_factorial(int64_t n) {
if (n < 0) return 0;
prepare_factorials(n);
return _inv_factorial[n];
}
mod_int choose(int64_t n, int64_t r) {
if (r < 0 || r > n) return 0;
prepare_factorials(n);
return _factorial[n] * _inv_factorial[r] * _inv_factorial[n - r];
}
mod_int permute(int64_t n, int64_t r) {
if (r < 0 || r > n) return 0;
prepare_factorials(n);
return _factorial[n] * _inv_factorial[n - r];
}
mod_int inv_choose(int64_t n, int64_t r) {
assert(0 <= r && r <= n);
prepare_factorials(n);
return _inv_factorial[n] * _factorial[r] * _factorial[n - r];
}
mod_int inv_permute(int64_t n, int64_t r) {
assert(0 <= r && r <= n);
prepare_factorials(n);
return _inv_factorial[n] * _factorial[n - r];
}
void __print(mod_int x) {cerr << x;}
const int N = 8;
vector<int> A = {2, 3, 5, 7, 11, 13, 17, 19};
void solve() {
int n; cin >> n;
vector<int> a(n + 1);
vector<mod_int> p(1 << N, 1); vector<int> count(N);
mod_int ans = 0;
for (int i = 1; i <= n; i++) {
cin >> a[i];
for (int j = 0; j < N; j++) {
while (a[i] % A[j] == 0) a[i] /= A[j], count[j]++;
}
for (int mask = 0; mask < (1 << N); mask++) {
mod_int val = p[mask];
int c = 0;
for (int j = 0; j < N; j++) {
if (mask >> j & 1) {
c = 1;
} else {
val *= count[j];
}
}
if (c) ans += val;
else ans += val;
}
for (int mask = 0; mask < (1 << N); mask++) {
mod_int val = 1;
for (int j = 0; j < N; j++) {
if (mask >> j & 1) {
val *= (-count[j] + 1);
}
}
p[mask] += val;
}
}
cout << ans << '\n';
}
int32_t main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1;
cin >> T;
while (T--) solve();
return 0;
}
/*
INPUT
1
9
10 17 19 2 11 2 7 13 12
SOLUTION OUTPUT
2770
CORRECT OUTPUT
2410
*/
ayush_295 have 4 skipped contests most probably because of cheating
arnabmanna submissions were skipped in Codeforces Round 994 (Div. 2) and he got caught already check this blog
raneatharva have 3 skipped contests
nika-skybytska is the true winner of this round, congratulations.
Uh, where is me?
Updated (the old version was based on standing at 1:30, that's why).
Chatgpt is CRAZY now