Bigger系列题解
Bigger Python
坑点在于要高精度以及表达式求值，用java写可以很容易避免高精度问题
然后这道题就可以AC了
代码
import java.io.*;
import java.util.*;
import java.math.*;
import java.text.*;
public class Main
{
static Map<String,BigInteger> map= new HashMap<String,BigInteger>();
static BigInteger cal(String s)
{
BigInteger ans=BigInteger.ZERO,mu=BigInteger.ONE,tk,val;
int tem,len=s.length(),la=1;
for(int pos=0;pos<len;pos++)
{
if(s.charAt(pos)=='(')
{
int k=1;
tk=BigInteger.ZERO;
for(int d=pos+1;d<len;d++)
if(s.charAt(d)=='(')
k++;
else if(s.charAt(d)==')')
{
k--;
if(k==0)
{
tk=cal(s.substring(pos+1,d));
pos=d+1;
break;
}
}
}
else if(s.charAt(pos)=='-'||(s.charAt(pos)>='0'&&s.charAt(pos)<='9'))
{
int flag=1;
if(s.charAt(pos)=='-'){flag=-1;pos++;}
tem=0;
while(pos<len&&s.charAt(pos)>='0'&&s.charAt(pos)<='9')
{
tem=tem*10+(s.charAt(pos)-'0');
pos++;
}
tk=BigInteger.valueOf(tem*flag);
}
else
{
int fla=pos;
while(pos<len&&((s.charAt(pos)>='a'&&s.charAt(pos)<='z')||(s.charAt(pos)>='A'&&s.charAt(pos)<='Z')))pos++;
tk=map.get(s.substring(fla,pos));
}
if(pos==len)
{
mu=mu.multiply(tk);
if(la==1)
ans=ans.add(mu);
else
ans=ans.subtract(mu);
return ans;
}
if(s.charAt(pos)=='+'||s.charAt(pos)=='-')
{
mu=mu.multiply(tk);
if(la==1)
ans=ans.add(mu);
else
ans=ans.subtract(mu);
mu=BigInteger.ONE;
if(s.charAt(pos)=='+')
la=1;
else
la=0;
}
else if(s.charAt(pos)=='*')
mu=mu.multiply(tk);
}
return ans;
}
static void pr(String s)
{
int pos,la=0,len=s.length();
for(pos=0;pos<len;pos++)
{
if(s.charAt(pos)==',')
{
System.out.print(map.get(s.substring(la,pos)).toString()+" ");
la=pos+1;
}
}
System.out.println(map.get(s.substring(la,pos)).toString());
}
public static void main(String args[]) throws Exception
{
//Scanner in = new Scanner(new File("in.txt"));
//PrintWriter out = new PrintWriter(new FileWriter("out.txt",true));
Scanner in = new Scanner(System.in);
String s,tem;
char c;
int len;
int pos;
map.clear();
while(in.hasNext())
{
s=in.nextLine();
tem="";
len=s.length();
if(s.charAt(0)=='p')
pr(s.substring(6, len-1));
else
{
for(pos=0;pos<len;pos++)
if(s.charAt(pos)=='=')
{
map.put(s.substring(0,pos),cal(s.substring(pos+1, len)));
}
}
}
//System.out.println(h[n][m].mod(e));
System.out.close();
}
};
Bigger place
题源：ZOJ Monthly, December 2013 Problem H. Tragedy Organ
代码：
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <iostream>
using namespace std;
int main() {
double x, e ,y;
int t;
scanf("%d",&t);
while(t--)
{
cin>>x>>y;
x = x / y * 25.0;
x = sqrt(x * 0.04);
e = 1 + 8.0 / sqrt(7.0) * sqrt(x) * sin(sqrt(7.0) / 2 * log(x));
printf("%.12f\n", e);
}
return 0;
}
Bigger world
题目转化为{1,1,2,2,3,3,4,4,n,n}这个序列中，两个相同的数不挨在一起的方案数
用容斥什么的很容易就可以推出来公式了，然后显然不可以过，因为这道题的模数是一个非素数，所以得智障改一改公式，优化一下才行。
结果貌似大家都是on 递推的…
a(n) = n*(2*n-1)*a(n-1) + (n-1)*n*a(n-2)
代码
#include<bits/stdc++.h>
using namespace std;
long long dp[100100];
int main(){
int n,p;
while(scanf("%d%d",&n,&p)!=EOF){
n--;
dp[2]=2%p;
for(int i=3;i<=n;i++){
dp[i]=1LL*i*(2*i-1)%p*dp[i-1]%p+1LL*(i-1)*i%p*dp[i-2]%p;
dp[i]%=p;
}
printf("%lld\n",dp[n]);
}
return 0;
}
Bigger bet
随便推一推，发现这道题就是求行列式值，因为题目其实就是把行列式的定义说了一遍
然后这个怎么做呢？
定义消元后的f(i)=A[i][i]
很轻松就可以发现：f(n) = n^k - sigma(d|n)f(d),d<n,移项后 n^k = sigma(d|n)f(d)
f(i)显然是一个积性函数,f(p^a) = (p(a-1)(p^k-1),p是素数
然后线性筛就可以把f莽出来，这道题就结束了。
当然，这道题你得预处理+记忆化一些东西去优化常数。
代码
#include <cstdio>
#include <cstring>
const int MAXN = 1000000 + 10;
const int MOD = 1e9+7;
int vis[MAXN], A[MAXN];
int f[MAXN], p[MAXN], T, N, M, K, cas;
int pow_mod(int a, int n) {
int ret = 1;
for (; n; n >>= 1) {
if (n & 1) ret = (long long)ret * a % MOD;
a = (long long)a * a % MOD;
}
return ret;
}
void sieve() {
M = 0;
for (int i = 2; i < MAXN; ++ i) {
if (!vis[i]) p[M ++] = i;
for (int j = 0; j < M && i * p[j] < MAXN; ++ j) {
vis[i * p[j]] = true;
if (i % p[j] == 0) break;
}
}
}
int main() {
sieve();
scanf("%d", &T);
for (cas = 1; cas <= T; ++ cas) {
scanf("%d%d", &N, &K);
K %= (MOD - 1);
memset(f, 0, sizeof(int) * (N + 1)); f[1] = 1;
for (int i = 2; i <= N; ++ i) {
if (!f[i]) {
A[i] = pow_mod(i, K), f[i] = A[i] - 1;
if (f[i] < 0) f[i] += MOD;
}
for (int j = 0, t; j < M && (t = i * p[j]) <= N; ++ j) {
if (i % p[j] == 0) {
f[t] = (long long)f[i] * A[p[j]] % MOD;
break;
}
else {
f[t] = (long long)f[i] * (A[p[j]] - 1 + MOD) % MOD;
}
}
}
int ret = 1;
for (int i = 1; i <= N; ++ i) ret = (long long)ret * f[i] % MOD;
printf("%d\n", ret);
}
return 0;
}