A 串
题目描述
长度不超过 ，且包含子序列“us”的、只由小写字母构成的字符串有多少个？ 答案对
取模。
所谓子序列，指一个字符串删除部分字符（也可以不删）得到的字符串。
例如，"unoacscc"包含子序列"us"，但"scscucu"则不包含子序列"us"
输入描述:
一个正整数 （
）
输出描述:
一个正整数，为满足条件的字符串数量对 取模的值
分析：
设 表示长度为
且不包含 'u','s' 这两个字符的字符串个数.
表示长度为
且不包含 'u' 这个字符的字符串个数.
表示长度为
且不包含 's' 这个字符的字符串个数.
表示长度为
且不包含子序列 "us" 且包含子序列 "us"的字符串个数.
有状态转移方程
f[i][0] = f[i - 1][0] * 24; f[i][1] = f[i - 1][0] + f[i - 1][1] * 25; f[i][2] = f[i - 1][0] + f[i - 1][2] * 25; f[i][3] = f[i - 1][3] * 25 + f[i - 1][2];
因此包含子序列 "us" 的字符串个数为 .
代码实现：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
const int M = (int)1e6;
const int N = (int)2e4;
const int inf = 0x3f3f3f3f;
const double eps = 1e-6;
const ll mod = (ll)1e9 + 7;
ll f[M + 5][4];
ll quick(ll a, ll b, ll p = mod)
{
a %= p;
ll s = 1;
while(b)
{
if(b & 1) s = s * a % p;
a = a * a % p;
b >>= 1;
}
return s % p;
}
ll inv(ll n, ll p = mod)
{
return quick(n, p - 2, p);
}
void work()
{
int n; scanf("%d", &n);
f[0][0] = 1;
for(int i = 1; i <= n; ++i)
{
f[i][0] = f[i - 1][0] * 24 % mod;
f[i][1] = (f[i - 1][0] + f[i - 1][1] * 25) % mod;
f[i][2] = (f[i - 1][0] + f[i - 1][2] * 25) % mod;
f[i][3] = (f[i - 1][3] * 25 + f[i - 1][2]) % mod;
}
ll s = 0;
for(int i = 2; i <= n; ++i)
s = (s + f[i][0] + f[i][1] + f[i][2] + f[i][3]) % mod;
s = 26 * 26 % mod * (quick(26, n - 1) - 1) % mod * inv(25) % mod - s;
s = (s % mod + mod) % mod;
printf("%lld\n", s);
}
int main()
{
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
// int T; scanf("%d", &T);
// while(T--) work();
work();
// cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
return 0;
} B 括号
题目描述
请你构造一个非空的括号字符串，包含正好 个不同合法括号对。
所谓括号字符串，是指由'('和')'这两种字符构成的字符串。
要求构造的字符串长度不超过。
输入描述:
一个整数 。
输出描述:
一个仅包含左右括号字符串，其中有 个合法的括号对。如果有多种构造方法，输出任意一种合法方案即可。
分析：
比赛时没找到好康的构造策略，于是开始瞎搞...
代码实现：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
const int M = (int)1e8;
const int N = (int)2e4;
const int inf = 0x3f3f3f3f;
const double eps = 1e-6;
const ll mod = (ll)1e9 + 7;
stack<char> st;
void work()
{
int k; scanf("%d", &k);
if(k == 0) {printf(")\n"); return;}
int n = 1; while(1ll * n * n <= k) ++n;
--n;
int s = n * n;
for(int i = 1; i <= n; ++i) st.emplace(')');
for(int i = n; i >= 1; --i)
{
if(s + i <= k) st.push(')'), s += i;
st.push('(');
}
st.pop();
while(s < k)
{
st.push(')');
++s;
}
st.push('(');
while(!st.empty())
{
printf("%c", st.top());
st.pop();
}
printf("\n");
}
int main()
{
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
// int T; scanf("%d", &T);
// while(T--) work();
work();
// cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
return 0;
} C 红和蓝
题目描述
你拿到了一棵树，请你给每个顶点染成红色或蓝色。
要求：每个红点周围有且仅有一个红点，每个蓝点周围有且仅有一个蓝点。
“周围”的定义：某点周围的点指通过邻边直接连接的点。
所谓树，即没有自环、重边和回路的无向连通图。
输入描述:
第一行一个正整数 ，代表树的顶点个数。
接下来的 行，每行两个正整数
和
，代表点
和点
有一条边连接。
保证输入的一定是一棵合法的树。
输出描述:
如果可以达成染色的要求，请输出一个长度为 的字符串，第
个字符代表第
个顶点的染色情况，'B' 代表蓝色，'R' 代表红色。（若有多种合法染色的方法，输出任意一种即可）
否则直接输出-1。
分析：
设 表示在以
为根的子树中，
号点的颜色为
是否能构造出合法方案.
然后胡乱写写就过了
Q：小姐姐你的代码好长啊？！
A：没错，我的就是很长！（？
代码实现：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
const int M = (int)1e5;
const int N = (int)2e4;
const int inf = 0x3f3f3f3f;
const double eps = 1e-6;
const ll mod = (ll)1e9 + 7;
int n, cnt;
int head[M + 5];
struct enode
{
int v, nx;
}Edge[M * 2 + 5];
void init()
{
cnt = 0;
for(int i = 1; i <= n; ++i)
{
head[i] = -1;
}
}
void add(int u, int v)
{
Edge[cnt].v = v;
Edge[cnt].nx = head[u];
head[u] = cnt++;
}
int f[M + 5][2];
int sz[M + 5];
void dfs(int u, int fa)
{
sz[u] = 1;
f[u][0] = 0, f[u][1] = 0;
for(int i = head[u]; ~i; i = Edge[i].nx)
{
int v = Edge[i].v;
if(v == fa) continue;
dfs(v, u);
sz[u] += sz[v];
}
if(sz[u] & 1)
{
int son = -1;
for(int i = head[u]; ~i; i = Edge[i].nx)
{
int v = Edge[i].v;
if(v == fa) continue;
if(sz[v] & 1) son = v;
}
if(son == -1)
{
bool flag = 1;
for(int i = head[u]; ~i; i = Edge[i].nx)
{
int v = Edge[i].v;
if(v == fa) continue;
if(f[v][0] == 0) flag = 0;
}
if(flag) f[u][1] = 1;
flag = 1;
for(int i = head[u]; ~i; i = Edge[i].nx)
{
int v = Edge[i].v;
if(v == fa) continue;
if(f[v][1] == 0) flag = 0;
}
if(flag) f[u][0] = 1;
}
}
else
{
int son = -1;
for(int i = head[u]; ~i; i = Edge[i].nx)
{
int v = Edge[i].v;
if(v == fa) continue;
if(sz[v] & 1)
{
if(son == -1) son = v;
else {son = -1; break;}
}
}
if(son != -1)
{
bool flag = 1;
for(int i = head[u]; ~i; i = Edge[i].nx)
{
int v = Edge[i].v;
if(v == fa) continue;
if(v == son) continue;
if(f[v][1] == 0) flag = 0;
}
if(flag) f[u][0] = f[son][0];
flag = 1;
for(int i = head[u]; ~i; i = Edge[i].nx)
{
int v = Edge[i].v;
if(v == fa) continue;
if(v == son) continue;
if(f[v][0] == 0) flag = 0;
}
if(flag) f[u][1] = f[son][1];
}
}
// printf("f[%d][0] = %d\n", u, f[u][0]);
// printf("f[%d][1] = %d\n", u, f[u][1]);
}
char s[M + 5];
void dfs2(int u, int fa)
{
for(int i = head[u]; ~i; i = Edge[i].nx)
{
int v = Edge[i].v;
if(v == fa) continue;
if(sz[v] & 1)
{
s[v] = s[u];
}
else
{
if(s[u] == 'R') s[v] = 'B';
else if(s[u] == 'B') s[v] = 'R';
}
dfs2(v, u);
}
}
void work()
{
scanf("%d", &n); init();
for(int i = 1, a, b; i <= n - 1; ++i)
{
scanf("%d %d", &a, &b);
add(a, b), add(b, a);
}
dfs(1, 0);
if(sz[1] & 1) {printf("-1\n"); return;}
if(f[1][0])
{
s[1] = 'R';
dfs2(1, 0);
s[n + 1] = '\0';
printf("%s\n", s + 1);
}
else if(f[1][1])
{
s[1] = 'B';
dfs2(1, 0);
s[n + 1] = '\0';
printf("%s\n", s + 1);
}
else printf("-1\n");
}
int main()
{
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
// int T; scanf("%d", &T);
// while(T--) work();
work();
// cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
return 0;
} D 点一成零
题目描述
牛牛拿到了一个n*n的方阵，每个格子上面有一个数字：0或1
行和列的编号都是从0到n-1
现在牛牛每次操作可以点击一个写着1的格子，将这个格子所在的1连通块全部变成0。
牛牛想知道，自己有多少种不同的方案，可以把全部格子的1都变成0？
所谓连通块，是指方阵中的两个正方形共用一条边，即(x,y)和以下4个坐标的数是连通的：(x-1,y)、(x+1,y)、(x,y-1)、(x,y+1)
这个问题对于牛牛来说可能太简单了。于是他将这个问题变得更加复杂：
他会选择一个格子，将这个格子上的数字修改成1（如果本来就是1，那么不进行任何改变），再去考虑“点一成零”的方案数。
牛牛想知道，每次“将某个格子修改成1”之后，“把全部格子的1都变成0”的方案数量。
ps：请注意，每次“将某个格子修改成1”之后，状态会保留到接下来的询问。具体请参考样例描述。
由于方案数可能过大，请对 取模
输入描述:
第一行输入一个 n（）
随后 行每行有一个 长度为
的字符串，字符串只可能包含 '0' 或 '1' 字符 ，表示整个方阵
接下来输入一个数 ，表示询问的次数。（
）
随后 行每行有 2 个整数
和
表示将
行
列的数字变为 1 的一次修改操作
输出描述:
针对每一次变更数字的操作，输出当前的方案数
分析：
并查集维护，操作的时候顺便更新答案就行了.
代码实现：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
const int M = (int)5e2;
const int N = (int)2e4;
const int inf = 0x3f3f3f3f;
const double eps = 1e-6;
const ll mod = (ll)1e9 + 7;
int n, k;
char s[M + 5][M + 5];
int sz[M * M + 5];
int fa[M * M + 5];
ll fac[M * M + 5];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int tofind(int x)
{
if(x == fa[x]) return x;
return fa[x] = tofind(fa[x]);
}
inline int id(int i, int j)
{
return i * n + j;
}
ll quick(ll a, ll b, ll p = mod)
{
a %= p;
ll s = 1;
while(b)
{
if(b & 1) s = s * a % p;
a = a * a % p;
b >>= 1;
}
return s % p;
}
ll inv(ll n, ll p = mod)
{
return quick(n, p - 2, p);
}
/**
5
00110
00111
00000
01001
10100
3
1 3
1 2
4 3
**/
void work()
{
scanf("%d", &n);
for(int i = 0; i < n; ++i) scanf("%s", s[i]);
for(int i = 0; i < n; ++i) for(int j = 0; j < n; ++j) fa[id(i, j)] = id(i, j), sz[id(i, j)] = 1;
for(int i = 0; i < n; ++i)
{
for(int j = 0; j < n; ++j)
{
if(s[i][j] == '0') continue;
for(int k = 0; k < 4; ++k)
{
int x = i + dx[k], y = j + dy[k];
if(x < 0 || x >= n || y < 0 || y >= n || s[x][y] == '0') continue;
int a = id(i, j), b = id(x, y);
a = tofind(a), b = tofind(b);
if(a != b)
{
fa[a] = b;
sz[b] += sz[a];
}
}
}
}
ll ans = 1; int p = 0;
for(int i = 0; i < n; ++i)
{
for(int j = 0; j < n; ++j)
{
if(s[i][j] == '0') continue;
int a = id(i, j);
if(a != fa[a]) continue;
ans = ans * sz[a] % mod * inv(fac[p]) % mod * fac[p + 1] % mod;
++p;
}
}
int i, j, x, y;
scanf("%d", &k);
while(k--)
{
scanf("%d %d", &i, &j);
if(s[i][j] == '0')
{
s[i][j] = '1';
ans = ans * inv(fac[p]) % mod * fac[p + 1] % mod;
++p;
for(int k = 0; k < 4; ++k)
{
int x = i + dx[k], y = j + dy[k];
if(x < 0 || x >= n || y < 0 || y >= n || s[x][y] == '0') continue;
int a = id(i, j), b = id(x, y);
a = tofind(a), b = tofind(b);
if(a != b)
{
fa[a] = b;
ans = ans * inv(sz[a]) % mod
* inv(sz[b]) % mod
* (sz[a] + sz[b]) % mod
* inv(fac[p]) % mod
* fac[p - 1] % mod;
--p;
sz[b] += sz[a];
}
}
}
printf("%lld\n", ans);
}
}
int main()
{
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
// int T; scanf("%d", &T);
// while(T--) work();
fac[0] = 1;
for(int i = 1; i <= M * M; ++i) fac[i] = fac[i - 1] * i % mod;
work();
// cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
return 0;
} E 三棱锥之刻
题目描述
牛牛站在一个棱长为的正三棱锥内部的中心。（牛牛是不可移动的）
（所谓正三棱锥，指六条棱都相等的三棱锥。正三棱锥的中心指到 4 个顶点距离都相等的那个点）
如上图，，牛牛站在P点，
他拿着一个染色喷雾，可以用来给正三棱锥的内表面染色。
已知喷雾能喷洒的距离为。也就是说，三棱锥内表面距离牛牛不超过的点才有可能被染色。牛牛想知道，正三棱锥内表面能被他染色的最大面积是多少？
ps：牛牛可看成一个无大小的点。重力对于喷雾的影响忽略不计。
输入描述:
两个正整数和
输出描述:
染色的最大面积。若你的答案和正确答案误差不超过 ，则认为你的答案正确。
分析：
分四种情况讨论再鸡个分就行了.
吐槽：
前天刚被卡了精度，今天又被卡了...
例如这段代码是 WA 的double s = 0, lim = sqrt(r * r - 3.0 / 36.0 * a * a); double th = acos(1.0 - 3.0 / 36.0 * a * a / r / r);改成这个样子就 AC 了？？？
double s = 0, lim = sqrt(r * r - 3.0 / 36.0 * a * a); double th = acos(lim / r);原因就在于 WA 掉的代码中出现了大数减小数导致精度严重丢失的问题.
代码实现：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
const int M = (int)1e6;
const int N = (int)2e4;
const int inf = 0x3f3f3f3f;
const double eps = 1e-6;
const ll mod = (ll)1e9 + 7;
const double PI = acos(-1.0);
void work(double a, double r)
{
if(36 * r * r <= 3 * a * a) {printf("%.12f\n", 4 * PI * r * r); return;}
if(9 * r * r >= 3 * a * a) {printf("%.12f\n", sqrt(3) * a * a); return;}
double s = 0, lim = sqrt(r * r - 3.0 / 36.0 * a * a);
double th = acos(lim / r);
s += -sqrt(3.0) / 6 * a * lim;
s += r * r / 2.0 * ((PI / 2.0) - (th - 0.5 * sin(2 * th)));
double ans = 4 * (PI * r * r - 6.0 * s);
printf("%.12f\n", ans);
}
void work()
{
int a, r; scanf("%d %d", &a, &r);
if(144 * r * r <= 6 * a * a) {printf("0\n"); return;}
work(1.0 * a, sqrt(r * r - 6.0 / 144.0 * a * a));
}
int main()
{
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
// int T; scanf("%d", &T);
// while(T--) work();
work();
// cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
return 0;
} F 对答案一时爽
题目描述
考试结束了，牛牛和牛妹开始对答案。
每道题有 ABCD 四个选项，一共有道题，全部是单选题，每道题正确得 1 分，错误不得分。
牛牛和牛妹互相知道了他们每道题选择的选项。他们想知道，两个人得分之和有可能达到的最大值和最小值是多少？
输入描述:
第一行输入一个正整数（）
第二行输入一行个字符（'A'、'B'、'C'、'D'中的一种），用空格隔开。第个字符代表牛牛第题的选项。
第三行输入一行个字符（'A'、'B'、'C'、'D'中的一种），用空格隔开。第个字符代表牛妹第题的选项。
输出描述:
牛牛和牛妹得分之和的能达到的最大值和最小值。用空格隔开。
分析：
签到题.
代码实现：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
const int M = (int)1e5;
const int N = (int)2e4;
const int inf = 0x3f3f3f3f;
const double eps = 1e-6;
const ll mod = (ll)1e9 + 7;
int n;
char s[M + 5];
char t[M + 5];
int getMax()
{
int ans = 0;
for(int i = 1; i <= n; ++i)
{
if(s[i] == t[i]) ans += 2;
if(s[i] != t[i]) ans += 1;
}
return ans;
}
int getMin()
{
return 0;
}
void work()
{
scanf("%d", &n);
for(int i = 1; i <= n; ++i)
{
getchar();
scanf("%c", &s[i]);
}
for(int i = 1; i <= n; ++i)
{
getchar();
scanf("%c", &t[i]);
}
printf("%d %d\n", getMax(), getMin());
}
int main()
{
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
// int T; scanf("%d", &T);
// while(T--) work();
work();
// cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
return 0;
} G 好玩的数字游戏
好像是个恶心模拟题，以后在做吧（咕咕咕）
H 幂塔个位数的计算
求底数为，层数为的幂塔的个位数是多少？
定义为底，层的幂塔为
例如
用数学语言表示，
求 的个位数。
输入描述:
第一行输入一个正整数。
第二行输入一个正整数。
输出描述:
一个数字，代表幂塔的个位数
分析：
欧拉降幂经典题了.
代码实现：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
const int M = (int)1e5;
const int N = (int)2e4;
const int inf = 0x3f3f3f3f;
const double eps = 1e-6;
const ll mod = (ll)1e9 + 7;
int a, n;
string sa, sn;
ll SMod(string sa, ll m)
{
int n = sa.size(), rem = 0;
for(int i = 0; i < n; ++i) rem = (rem * 10 + sa[i] - '0') % m;
return rem;
}
ll Mod(ll n, ll p)
{
return n < p ? n : n % p + p;
}
ll Mod(string sa, ll p)
{
int lensa = sa.size();
int rem = 0;
if(lensa > 1) return SMod(sa, p) + p;
else return Mod(SMod(sa, 100), p);
}
ll quick(string sa, ll b, ll p = mod)
{
int a = Mod(sa, p);
ll s = 1;
while(b)
{
if(b & 1) s = Mod(s * a, p);
a = Mod(a * a, p);
b >>= 1;
}
return s;
}
int phi[] = {0, 1, 2, 3, 2, 4, 2, 6, 4, 6, 4};
ll cal(int u, int m)
{
if(u == n || m == 1) return Mod(sa, m);
return quick(sa, cal(u + 1, phi[m]), m);
}
void work()
{
cin >> sa >> sn;
int lensn = sn.size();
if(lensn > 2) n = 100;
else
{
n = 0;
for(int i = 0; i < lensn; ++i) n = n * 10 + sn[i] - '0';
}
printf("%lld\n", cal(1, 10) % 10);
}
int main()
{
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
// int T; scanf("%d", &T);
// while(T--) work();
work();
// cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
return 0;
} I 限制不互素对的排列
题目描述
输入一个数 ，请构造一个长度为
的排列，使得其中正好有
对相邻的数gcd（最大公约数）大于
。
排列是指 到
一共 个数，每个数都出现过且仅出现过
次。例如，
输入描述:
两个整数 和
，用空格隔开。
输出描述:
如果不存在可行的构造方案，输出-1。
否则输出一行 个数，用空格隔开。如果有多组可行的构造方案，输出任意一组即可。
分析：
显然，当 时，直接把前
个偶数提到最前面，其他数按从小到大排列.
当 时，直接把前
个偶数(除
以外)提到最前面，接着再放 6，然后再放 3，其他数按从小到大排列.
代码实现：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
const int M = (int)1e6;
const int N = (int)2e4;
const int inf = 0x3f3f3f3f;
const double eps = 1e-6;
const ll mod = (ll)1e9 + 7;
int n, k;
bool vis[M + 5];
void work()
{
scanf("%d %d", &n, &k);
if(n < 6 && k == n / 2) {printf("-1\n"); return;}
if(k <= n / 2 - 1)
{
for(int i = 2; i <= 2 * (k + 1); i += 2)
{
printf("%d ", i);
vis[i] = 1;
}
for(int i = 1; i <= n; ++i)
{
if(!vis[i]) printf("%d ", i);
}
printf("\n");
}
else
{
for(int i = 2; i <= 2 * k; i += 2)
{
vis[i] = 1;
if(i == 6) continue;
printf("%d ", i);
}
if(vis[6])
{
printf("%d %d ", 6, 3);
vis[3] = 1;
}
for(int i = 1; i <= n; ++i)
{
if(!vis[i]) printf("%d ", i);
}
printf("\n");
}
}
int main()
{
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
// int T; scanf("%d", &T);
// while(T--) work();
work();
// cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
return 0;
} J 一群小青蛙呱蹦呱蹦呱
题目描述
有n个格子，每个格子里有一个数，1,2,3,4...n
牛牛放出无穷只青蛙。
第一只青蛙的路线是：1->2->4->8->16->....
第二只青蛙的路线是：1->3->9->27->81->....
第三只青蛙的路线是：1->5->25->125....
第四只青蛙的路线是：1->7->49........
。。。。。。
用数学语言描述，第 只青蛙的路线是首项为1，公比为
个素数。
当青蛙跳到一个格子上，如果这个格子上面有一个数，青蛙就会把这个数吃掉。
牛牛想知道，所有没有被吃掉的数的lcm（最小公倍数 ，Least common multiple）是多少？
由于这个lcm可能非常大，请输出它对
输入描述:
一个正整数 
输出描述:
如果所有数都被吃掉了，请输出一个字符串"empty"
否则输出所有没有被吃掉的数的lcm，对
分析：
显然，没被吃掉的数就是含有至少两个质因子的数.
在统计 lcm 的时候，就让当前质因子的指数尽量大.
代码实现：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
const int M = (int)1e8;
const int N = (int)2e4;
const int inf = 0x3f3f3f3f;
const double eps = 1e-6;
const ll mod = (ll)1e9 + 7;
bool is_prime[M + 5];
int prime[M + 5], cnt;
void init()
{
memset(is_prime, 1, sizeof(is_prime));
is_prime[0] = is_prime[1] = 0;
for(int i = 2; i <= M; ++i)
{
if(is_prime[i])
{
prime[++cnt] = i;
}
for(int j = 1; j <= cnt && i * prime[j] <= M; ++j)
{
is_prime[i * prime[j]] = 0;
if(i % prime[j] == 0)
{
break;
}
}
}
}
ll quick(ll a, ll b, ll p = mod)
{
// printf("%lld^%lld\n", a, b);
ll s = 1;
while(b)
{
if(b & 1) s = s * a % p;
a = a * a % p;
b >>= 1;
}
return s;
}
void work()
{
int n; scanf("%d", &n);
if(n <= 5) {printf("empty\n"); return;}
ll c = 0, t = 3;
while(t <= n) ++c, t *= 2;
ll ans = quick(2, c - 1);
for(int i = 2; i <= cnt && 2 * prime[i] <= n; ++i)
{
c = 0, t = 2;
while(t <= n) ++c, t *= prime[i];
ans = ans * quick(prime[i], c - 1) % mod;
}
printf("%lld\n", ans);
}
int main()
{
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
// int T; scanf("%d", &T);
// while(T--) work();
init();
work();
// cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
return 0;
} 
京公网安备 11010502036488号