B Signed Derangements
定义一个大小为n的Signed Derangements为n一个全排列随机加上正负号
求大小为n的Signed Derangements中，$$p_i \neq i$$的排列数
利用容斥原理即可，显然，$$f_1 = 1$$
接着，$$\forall m > 1 , f_m = 2\^m m! - \Sigma_{1\le j<m} C_m\^jf_(m-j)$$
于是可以计算出结果。注意需要使用高精度。
import java.io.*;
import java.math.*;
import java.util.*;
import java.text.*;
import java.lang.*;
public class Main{
final static int maxn = 200 + 5;
public static BigInteger bigPow(BigInteger a, int b) {
BigInteger ret = new BigInteger("1");
BigInteger x = a;
while (b > 0) {
if ((b & 1) == 1) {
ret = ret.multiply(x);
}
x = x.multiply(x);
b = b >> 1;
}
return ret;
}
public static void main(String[] args) {
try{
InputStream fin = new FileInputStream(new File("derangements.in"));
Scanner cin = new Scanner(new BufferedInputStream(fin));
BigInteger c[][] = new BigInteger[maxn][maxn];
BigInteger frac[] = new BigInteger[maxn];
BigInteger f[] = new BigInteger[maxn];
c[0][0] = new BigInteger("1");
frac[0] = new BigInteger("1");
for (int i = 1; i < maxn; i++)
c[0][i] = new BigInteger("0");
for (int i = 1; i < maxn; i++) {
frac[i] = frac[i - 1].multiply(new BigInteger("" + i));
c[i][0] = new BigInteger("1");
for (int j = 1; j < maxn; j++)
c[i][j] = c[i - 1][j - 1].add(c[i - 1][j]);
}
f[1] = new BigInteger("1");
for (int i = 2; i < maxn; i++) {
f[i] = bigPow(new BigInteger("2"), i).multiply(frac[i]);
for (int j = 1; j < i; j++) {
f[i] = f[i].subtract(c[i][j].multiply(f[i - j]));
}
f[i] = f[i].subtract(new BigInteger("1"));
}
int n = cin.nextInt();
PrintWriter pw = new PrintWriter(new OutputStreamWriter(new FileOutputStream("derangements.out")));
pw.println(f[n].toString());
fin.close();
pw.close();
/*
for (int i = 1; i < maxn; i++) {
System.out.printf("\"%s\" ,\n", f[i].toString());
}*/
}catch(Exception e)
{}
}
}
D Currency Exchange
求$$[L,R]$$区间内，能用00112233445566778899组成的数字种数
显然是数位DP，首先，我们用三进制数$$(a_9a_8a_7a_6a_5a_4a_3a_2a_1a_0)_3$$表示每种数字出现了几次，则转移方程为
$$F_{len + 1,k,w + (1 << k)_3} = \Sigma F_{len,k’,w}$$
其中len表示当前数字位数，k表示最高位，w表示每个数字出现了几次。
之后就是传统数位DP
#include <bits/stdc++.h>
using namespace std;
const int maxn = 59049 + 5, maxbit = 21;
const int pow3[]={1,3,9,27,81,243,729,2187,6561,19683,59049};
long long f[maxbit][10][maxn];
int eachbit[maxbit];
int eachbit2[maxbit];
int ato3(int b[])
{
int ret = 0;
for (int i = 0; i < 10; i++)
ret = ret + b[i] * pow3[i];
return ret;
}
void ttoa(int b[], int num)
{
for (int i = 0; i < 10; i++)
b[i] = (num / pow3[i]) % 3;
}
long long getans(long long q)
{
long long ret = 0;
int totbit = 1;
memset(eachbit2, 0, sizeof(eachbit2));
while (q)
{
eachbit2[totbit++] = q % 10;
q /= 10;
}
int eachbit3[maxbit];
bool flg;
for (int i = 0; i <= 9; i++) eachbit3[i] = 2;
totbit--;
for (int i = 1; i < totbit; i++)
for (int j = 1; j < 10; j++)
for (int l = 0; l < 59049; l++)
ret += f[i][j][l];
// cerr << ret << endl;
for (int i = 1; i < eachbit2[totbit]; i++)
for (int l = 0; l < 59049; l++)
ret += f[totbit][i][l];
// cerr << ret << endl;
// eachbit3[eachbit2[totbit]]--;
for (int i = totbit - 1; i > 0; i--)
{
eachbit3[eachbit2[i + 1]]--;
for (int j = 0; j < eachbit2[i]; j++)
{
for (int l = 0; l < 59049; l++)
{
flg = true;
ttoa(eachbit, l);
for (int m = 0; m < 10; m++)
if (eachbit[m] > eachbit3[m])
{
flg = false;
break;
}
if (flg)
{
/*
if (f[i][j][l])
{
cerr << i << " " << j << " " << l;
cerr << " " << f[i][j][l] << endl;
}*/
ret += f[i][j][l];
}
}
}
}
return ret;
}
int main()
{
#ifdef ONLINE_JUDGE
freopen("exchange.in", "r", stdin);
freopen("exchange.out", "w", stdout);
#endif
long long l , r;
f[0][0][0] = 1;
for (int i = 0; i < 20; i++)
for (int j = 0; j < 59049; j++)
{
ttoa(eachbit, j);
long long lsum = 0;
for (int k = 0; k <= 9; k++)
lsum += f[i][k][j];
/*
if (lsum)
{
for (int k = 0; k <= 9; k++) cerr << eachbit[k];
cerr << endl;
cerr << i << " " << j << " " << lsum << endl;
cin >> l;
}*/
for (int k = 0; k <= 9; k++)
if (eachbit[k] < 2)
{
eachbit[k]++;
f[i + 1][k][ato3(eachbit)] += lsum;
eachbit[k]--;
}
}
cin >> l >> r;
cout << getans(r + 1) - getans(l) << endl;
return 0;
}
F $$\sqrt{Nim}$$
Nim游戏，每次可以取$$[1,\lfloor k\rfloor]$$个石子，问先手是否必胜。
可以枚举$$\lfloor k\rfloor$$的值，注意到数据只有$$10\^{12}$$，则$$\lfloor k\rfloor$$不会超过$$10\^6$$，必败态也不会超过$$10\^6$$，预处理之后回答即可。
#include <bits/stdc++.h>
using namespace std;
set<long long> s;
int main()
{
#ifdef ONLINE_JUDGE
freopen("nim.in", "r", stdin);
freopen("nim.out", "w", stdout);
#endif
long long curr = 2;
s.insert(1e16);
s.insert(2);
for (long long sq = 1; sq <= 1000000 + 5; sq++)
{
long long curr2 = curr + sq + 1;
while (curr2 < (sq + 1) * (sq + 1))
{
s.insert(curr2);
curr = curr2;
curr2 = curr + sq + 1;
}
}
long long n;
cin >> n;
if ((*s.lower_bound(n)) == n)
printf("LOSE\n");
else
printf("WIN\n");
return 0;
}