2017山东一轮集训 Day1
Sum
题目描述：
求有多少(n)位十进制数时(p)的倍数且每位之和小于等于$m_i (m_i = 0,1,2, dots , m - 1) $，允许前导零，答案对998244353取模。
数据范围：
$1 leqslant n leqslant 10^9 , 1 leqslant p leqslant 50 , 1 leqslant m leqslant 1000 $
题解：
位数和？前导零？(p)的倍数？数位dp裸题？？？不好意思(n)是十亿。。。怎么办？怎么办？由于可以忽略掉前导零，那么考虑倍增一下：
对于一个长度(len)我们先把(lfloor frac{len}{2} floor)的答案即(dp[lfloor frac{len}{2} floor])求出来，这个直接递归算，然后先解决长度为偶数的情况。
容易发现第一个和式是一个卷积的形式，那么我们将(dp)数组做一次(DFT)，然后就可以愉快的直接暴力转移了。
然后考虑长度为奇数的情况，其实就是少了一位（算出了(len - 1)的答案），那么只需要暴力枚举最高位即可。
时间复杂度(O((p^2m+mlogm)log n))
代码：
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int MOD = 998244353;
const int G = 3;
const int maxn = 3010;
inline int inc(int a, int b) { return (a + b >= MOD) ? (a + b - MOD) : (a + b); }
inline int dec(int a, int b) { return (a > b) ? (a - b) : (a + MOD - b); }
inline int mul(int a, int b) { return 1LL * a * b % MOD; }
inline int power(int x, int k) {
int tmp = 1;
while(k) {
if(k & 1) tmp = mul(tmp,x);
x = mul(x,x);
k >>= 1;
}
return tmp;
}
namespace NTT{
int len, invlen;
inline void init(int n) {
len = 1;
while(len <= n) len <<= 1; len <<= 1;
invlen = power(len,MOD - 2);
}
inline void rader(int *a, int n) {
for(int i = 0, j = 0;i < n - 1;i ++) {
if(i < j) swap(a[i],a[j]);
int k = n >> 1;
while(j >= k) {
j -= k;
k >>= 1;
}
if(j < k) j += k;
}
}
inline void ntt(int *a, int kd) {
int n = len;
rader(a,n);
for(int i = 2;i <= n;i <<= 1) {
int pn = power(G,(MOD - 1) / i);
for(int j = 0;j < n;j += i) {
int p = 1;
for(int k = 0;k < (i >> 1);k ++) {
int x = a[k + j], y = mul(a[k + j + (i >> 1)],p);
a[k + j] = inc(x,y);
a[k + j + (i >> 1)] = dec(x,y);
p = mul(p,pn);
}
}
}
if(kd == -1) {
for(int i = 1;i < (n >> 1);i ++) swap(a[i],a[n - i]);
for(int i = 0;i < n;i ++) a[i] = mul(a[i],invlen);
}
}
}
int n, p, m;
int g[maxn][maxn], f[maxn][maxn];
inline int work(int n) {
if(!n) return 1;
int mi = work(n >> 1);
for(int i = 0;i < p;i ++) NTT::ntt(g[i],1);
for(int i = 0;i < p;i ++) {
for(int j = 0;j < p;j ++) {
int now = (i + 1LL * j * mi % p) % p;
for(int k = 0;k < NTT::len;k ++) f[now][k] = inc(f[now][k],mul(g[i][k],g[j][k]));
}
}
for(int i = 0;i < p;i ++) NTT::ntt(f[i],-1);
for(int i = 0;i < p;i ++) {
for(int j = 0;j < NTT::len;j ++) g[i][j] = 0;
for(int j = 0;j <= m;j ++) g[i][j] = f[i][j];
for(int j = 0;j < NTT::len;j ++) f[i][j] = 0;
}
mi = 1LL * mi * mi % p;
if(n & 1) {
for(int i = 0;i < p;i ++) {
for(int x = 0;x <= 9;x ++) {
for(int j = 0;j + x <= m;j ++) {
int now = (i + 1LL * x * mi % p) % p;
f[now][j + x] = inc(f[now][j + x],g[i][j]);
}
}
}
for(int i = 0;i < p;i ++) {
for(int j = 0;j <= m;j ++) g[i][j] = f[i][j];
for(int j = 0;j < NTT::len;j ++) f[i][j] = 0;
}
mi = 1LL * mi * 10 % p;
}
return mi;
}
int main() {
scanf("%d%d%d", &n, &p, &m);
g[0][0] = 1; m ++;
NTT::init(m);
m --;
work(n);
int ans = 0;
for(int i = 0;i <= m;i ++) {
ans = inc(ans,g[0][i]);
printf("%d ", ans);
}
puts("");
return 0;
}
Set
题目描述：
给出(n)个非负整数，将数划分成两个集合，记为一号集合和二号集合。(x_1)为一号集合中所有数的异或和，(x_2)为二号集合中所有数的异或和。在最大化(x_1+x_2)的前提下，最小化(x_1)。
数据范围：
$1 leqslant n leqslant 10^5 $
题解：
异或！选数的子集！线性基！！！
设(Sum)为所有数的异或和，那么题目变成最大化Sum^x1+x1，且最小化x1。按套路，从大到小贪心的决策，假设当前在第k位：
如果Sum的第k位为1：那么x1的第k位最好为1，这样就有(2^{k - 1})的贡献
如果Sum的第k位为0：那么x1的第k位最好为1，这样就有(2^k)的贡献
考虑用线性基来维护这个贪心，容易发现按Sum的二进制建出两个线性基：Sum为1的位，Sum为0的位。这样优先级也就很容易确定了：Sum为0的优先于Sum为1的，高位优先于低位，直接贪心即可。
时间复杂度：(O(n log N))
代码：
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
typedef long long ll;
const int maxn = 100000 + 10;
int n, vis[maxn];
ll a[maxn], sum, s[70];
inline void ins(ll x) {
for(ll i = 62;i >= 0;i --) {
if(!(sum & (1LL << i)) && (x & (1LL << i))) {
if(!s[i]) {
s[i] = x;
return;
}
else x ^= s[i];
}
}
for(ll i = 62;i >= 0;i --) {
if((sum & (1LL << i)) && (x & (1LL << i))) {
if(!s[i]) {
s[i] = x;
return;
}
else x ^= s[i];
}
}
}
int main() {
scanf("%d", &n); sum = 0;
for(int i = 1;i <= n;i ++) scanf("%lld", &a[i]), sum ^= a[i];
for(int i = 1;i <= n;i ++) ins(a[i]);
ll ans = 0;
for(ll i = 62;i >= 0;i --) {
if(!(sum & (1LL << i))) {
ll tmp = (ans ^ s[i]) + (ans ^ s[i] ^ sum);
ll now = ans + (ans ^ sum);
if(tmp > now || (tmp == now && ans < (ans ^ s[i])))
ans ^= s[i];
}
}
for(ll i = 62;i >= 0;i --) {
if(sum & (1LL << i)) {
ll tmp = (ans ^ s[i]) + (ans ^ s[i] ^ sum);
ll now = ans + (ans ^ sum);
if(tmp > now || (tmp == now && ans < (ans ^ s[i]))) ans ^= s[i];
}
}
printf("%lld
", sum ^ ans);
return 0;
}