CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~
Magic Mirror
#include <cstdio>
#include <cstring>
int T;
char s[20], a[20] = "JESSIE", b[20] = "jessie";
bool o;
int main()
{
scanf("%d", &T);
while (T--)
{
scanf("%s", s);
if (strlen(s) != 6)
{
printf("Dare you say that again?\n");
continue;
}
o = true;
for (int i = 0; i < 6; i++)
if ((s[i] != a[i]) && (s[i] != b[i]))
{
o = false;
break;
}
if (o)
printf("Good guy!\n");
else
printf("Dare you say that again?\n");
}
}
Mathematical Curse
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int t, n, m, k;
long long a[1010];
char s[10];
long long mx[1010][10], mn[1010][10];
int main()
{
scanf("%d", &t);
while (t--)
{
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= n; i++)
scanf("%lld", &a[i]);
scanf("%s", s);
memset(mx, 0, sizeof(mx));
memset(mn, 0, sizeof(mn));
mx[0][0] = mn[0][0] = k;
for (int i = 1; i <= n; i++)
for (int j = 1; (j <= m) && (j <= i); j++)
{
mx[i][0] = mn[i][0] = k;
if (s[j - 1] == '+')
mx[i][j] = mx[i - 1][j - 1] + a[i], mn[i][j] = mn[i - 1][j - 1] + a[i];
else if (s[j - 1] == '-')
mx[i][j] = mx[i - 1][j - 1] - a[i], mn[i][j] = mn[i - 1][j - 1] - a[i];
else if (s[j - 1] == '*')
{
if (a[i] >= 0)
mx[i][j] = mx[i - 1][j - 1] * a[i], mn[i][j] = mn[i - 1][j - 1] * a[i];
else
mx[i][j] = mn[i - 1][j - 1] * a[i], mn[i][j] = mx[i - 1][j - 1] * a[i];
}
else
{
if (a[i] >= 0)
mx[i][j] = mx[i - 1][j - 1] / a[i], mn[i][j] = mn[i - 1][j - 1] / a[i];
else
mx[i][j] = mn[i - 1][j - 1] / a[i], mn[i][j] = mx[i - 1][j - 1] / a[i];
}
if (i > j)
mx[i][j] = max(mx[i][j], mx[i - 1][j]), mn[i][j] = min(mn[i][j], mn[i - 1][j]);
}
printf("%lld\n", mx[n][m]);
}
}
Password
Sequence
Jiu Yuan Wants to Eat
链剖+双标记维护区间和，区间取反操作等价于区间乘 -1 后区间加 -1 。
时限卡的有点紧，线段树用 vector 建的时候卡时限 2832ms/3000ms，改成数组也要跑 2448ms/3000ms。
#include <cstdio>
#include <vector>
using namespace std;
typedef unsigned long long ll;
const int N = 1e5 + 9;
struct Node
{
int l, r;
ll mul, add, sum;
void upd(ll m, ll a)
{
mul *= m;
add = add * m + a;
sum = sum * m + a * (r - l + 1);
}
void up(const Node &lc, const Node &rc) { sum = lc.sum + rc.sum; }
void down(Node &lc, Node &rc) { lc.upd(mul, add), rc.upd(mul, add), mul = 1, add = 0; }
} v[N << 2];
struct SegmentTree
{
SegmentTree(int l, int r) { build(l, r); }
void build(int l, int r, int rt = 1)
{
v[rt] = {l, r};
if (l == r)
return;
int m = v[rt].r + v[rt].l >> 1;
build(l, m, rt << 1), build(m + 1, r, rt << 1 | 1), v[rt].up(v[rt << 1], v[rt << 1 | 1]);
}
void upd(int l, int r, ll mul, ll add, int rt = 1)
{
if (l <= v[rt].l && v[rt].r <= r)
return v[rt].upd(mul, add);
v[rt].down(v[rt << 1], v[rt << 1 | 1]);
int m = v[rt].r + v[rt].l >> 1;
if (m >= r)
upd(l, r, mul, add, rt << 1);
else if (m < l)
upd(l, r, mul, add, rt << 1 | 1);
else
upd(l, m, mul, add, rt << 1), upd(m + 1, r, mul, add, rt << 1 | 1);
v[rt].up(v[rt << 1], v[rt << 1 | 1]);
}
Node ask(int l, int r, int rt = 1)
{
if (l <= v[rt].l && v[rt].r <= r)
return v[rt];
v[rt].down(v[rt << 1], v[rt << 1 | 1]);
int m = v[rt].l + v[rt].r >> 1;
if (m >= r)
return ask(l, r, rt << 1);
if (m < l)
return ask(l, r, rt << 1 | 1);
return v[0].up(ask(l, m, rt << 1), ask(m + 1, r, rt << 1 | 1)), v[0];
}
};
struct Graph
{
struct Vertex
{
vector<int> o, i; //相关出边和入边编号
int siz, dep, top, dfn; //树链剖分中使用，依次代表子树节点数、深度、所在链的顶端节点、dfs序
};
typedef pair<int, int> Edge;
vector<Vertex> v; //点集
vector<Edge> e; //边集
Graph(int n) : v(n) {}
void add(const Edge &ed)
{
v[ed.first].o.push_back(e.size());
v[ed.second].i.push_back(e.size());
e.push_back(ed);
}
int ch(int u, int i = 0) { return e[v[u].o[i]].second; } //u的第i个孩子节点
int fa(int u, int i = 0) { return e[v[u].i[i]].first; } //u的第i个父节点
};
struct Diagram : Graph
{
SegmentTree data; //暂用树状数组作为默认数据结构
Diagram(const Graph &g, int root) : Graph(g.v.size()), data(0, g.v.size() - 1)
{
build(root, g);
int cnt = v[root].dfn = v[root].dep = 1;
dfs(v[root].top = root, cnt);
}
void build(int u, const Graph &g) //无向图dfs建树，且重边在最前，u为根节点
{
v[u].siz = 1;
for (int i = 0, k, to; i < g.v[u].o.size(); ++i)
if (k = g.v[u].o[i], to = g.e[k].second, !v[to].siz) //没访问过的点siz默认0
{
build(to, g);
v[u].siz += v[to].siz;
Graph::add(g.e[k]);
if (v[ch(u)].siz < v[to].siz) //重边移到最前
swap(v[u].o.front(), v[u].o.back());
}
}
void dfs(int u, int &cnt)
{
for (int i = 0, to; i < v[u].o.size(); ++i)
{
v[to = ch(u, i)].dfn = ++cnt;
v[to].top = i ? to : v[u].top;
v[to].dep = v[u].dep + 1;
dfs(to, cnt);
}
}
Node ask(int x, int y)
{
Node ans;
ans.sum = 0;
for (; v[x].top != v[y].top; x = fa(v[x].top))
{
if (v[v[x].top].dep < v[v[y].top].dep)
swap(x, y);
ans.up(ans, data.ask(v[v[x].top].dfn, v[x].dfn));
}
if (v[x].dep < v[y].dep)
swap(x, y);
return ans.up(ans, data.ask(v[y].dfn, v[x].dfn)), ans;
}
void upd(int x, int y, ll mul, ll add)
{
for (; v[x].top != v[y].top; x = fa(v[x].top))
{
if (v[v[x].top].dep < v[v[y].top].dep)
swap(x, y);
data.upd(v[v[x].top].dfn, v[x].dfn, mul, add);
}
if (v[x].dep < v[y].dep)
swap(x, y);
data.upd(v[y].dfn, v[x].dfn, mul, add);
}
};
int main()
{
for (int n; ~scanf("%d", &n);)
{
Graph g(n + 1);
for (int i = 2, b; i <= n; ++i)
scanf("%d", &b), g.add({b, i});
Diagram d(g, 1);
scanf("%d", &n);
for (int i = 0, u, v; i < n; ++i)
{
ll x;
scanf("%llu%d%d", &x, &u, &v);
if (x == 1)
scanf("%llu", &x), d.upd(u, v, x, 0);
else if (x == 2)
scanf("%llu", &x), d.upd(u, v, 1, x);
else if (x == 3)
d.upd(u, v, -1, -1);
else
printf("%llu\n", d.ask(u, v).sum);
}
}
}
Modular Production Line
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll N = 100009, NPOS = -1, INF = 1e18;
struct Ranker : vector<ll>
{
void init()
{
sort(begin(), end()), resize(unique(begin(), end()) - begin());
}
int ask(ll x) const
{
return lower_bound(begin(), end(), x) - begin();
}
};
struct Graph
{
struct Vertex
{
vector<int> a /*,b*/; //相关出边和入边编号
//int siz,dep,top,dfn;//树链剖分中使用，依次代表子树节点数、深度、所在链的顶端节点、dfs序
};
struct Edge
{
int from, to;
ll dist, cap; //边长、容量，图论算法使用
};
vector<Vertex> v; //点集
vector<Edge> e; //边集
Graph(int n) : v(n) {}
void add(const Edge &ed)
{
if (ed.from == ed.to)
return; //如果有需要请拆点
v[ed.from].a.push_back(e.size());
//v[ed.to].b.push_back(e.size());
e.push_back(ed);
}
};
struct EdmondKarp : Graph
{
ll flow, cost;
vector<ll> f;
EdmondKarp(int n) : Graph(n) {}
void add(Edge ed)
{
Graph::add(ed);
swap(ed.from, ed.to), ed.cap = 0, ed.dist *= -1;
Graph::add(ed);
}
void ask(int s, int t)
{
vector<int> p(v.size(), NPOS);
for (f.assign(e.size(), flow = cost = 0);;)
{
vector<ll> d(v.size(), INF);
vector<int> flag(v.size(), d[s] = 0);
for (deque<int> q(flag[s] = 1, s); !q.empty(); q.pop_front())
for (int u = q.front(), i = flag[u] = 0, k, to; i < v[u].a.size(); ++i)
if (k = v[u].a[i], to = e[k].to,
e[k].cap > f[k] && d[to] > d[u] + e[k].dist)
{
d[to] = d[u] + e[k].dist, p[to] = k;
if (!flag[to])
q.push_back(to), flag[to] = 1;
}
if (d[t] == INF)
return;
ll _f = INF;
for (int u = t; u != s; u = e[p[u]].from)
_f = min(_f, e[p[u]].cap - f[p[u]]);
for (int u = t; u != s; u = e[p[u]].from)
cost += _f * e[p[u]].dist, f[p[u]] += _f, f[p[u] ^ 1] -= _f;
flow += _f;
}
}
};
int t, n, m, k, x[N], y[N], w[N];
int main()
{
for (scanf("%d", &t); t--;)
{
Ranker rk;
scanf("%d%d%d", &n, &k, &m);
for (int i = 0; i < m; ++i)
{
scanf("%d%d%d", &x[i], &y[i], &w[i]);
rk.push_back(x[i]);
rk.push_back(++y[i]);
}
rk.init();
EdmondKarp g(rk.size() + 2);
for (int i = 0; i < rk.size(); ++i)
g.add({i, i + 1, 0, k});
for (int i = 0; i < m; ++i)
g.add({rk.ask(x[i]), rk.ask(y[i]), -w[i], 1});
g.add({rk.size() + 1, 0, 0, k});
g.ask(rk.size() + 1, rk.size());
printf("%lld\n", -g.cost);
}
}
Give Candies
答案是$2^{n-2}$，用费马小定理把指数对 M-1 取模后进行运算避免更多的高精度运算。
#include <stdio.h>
#define mul(a, b, c) (1LL * (a) * (b) % (c))
typedef int ll;
const ll M = 1e9 + 7;
ll pow(ll a, ll b, ll m)
{
ll r = 1;
for (a %= m; b; b >>= 1, a = mul(a, a, m))
if (b & 1)
r = mul(r, a, m);
return r;
}
char s[100009];
int t, n;
int main()
{
for (scanf("%d", &t); t--;)
{
scanf("%s", s);
for (int i = n = 0; s[i]; ++i)
n = mul(n, 10, M - 1) + s[i] - '0';
printf("%d\n", pow(2, n + M - 2, M));
}
}
String and Times
拉一个后缀数组的板子跑掉了。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct SufArr
{
vector<int> sa, rk, h;
SufArr(const vector<int> &s, int m) : sa(s.size(), 0), rk(s), h(s.size(), 0)
{
vector<int> cnt(s.size() + m, 0);
for (int i = 0; i < s.size(); ++i)
++cnt[rk[i]];
for (int i = 1; i < m; ++i)
cnt[i] += cnt[i - 1];
for (int i = 0; i < s.size(); ++i)
sa[--cnt[rk[i]]] = i;
for (int k = 1, j = 0; k <= s.size() && j < s.size() - 1; k <<= 1)
{
for (int i = 0; i < s.size(); ++i)
{
if (j = sa[i] - k, j < 0)
j += s.size();
h[cnt[rk[j]]++] = j;
}
cnt[0] = sa[h[0]] = j = 0;
for (int i = 1; i < s.size(); ++i)
{
if (rk[h[i]] != rk[h[i - 1]] || rk[h[i] + k] != rk[h[i - 1] + k])
cnt[++j] = i;
sa[h[i]] = j;
}
swap(rk, sa), swap(sa, h);
}
for (int i = 0, k = 0, j = rk[0]; i < s.size() - 1; ++i, ++k)
for (; ~k && s[i] != s[sa[j - 1] + k]; j = rk[sa[j] + 1], --k)
h[j] = k;
}
};
struct SparseTable
{
typedef int ll;
vector<vector<ll>> f;
SparseTable(const vector<ll> &a) : f(log2(a.size()) + 1, a)
{
for (int k = 0; k + 1 < f.size(); ++k)
for (int i = 0; i + (1 << k) < a.size(); ++i)
f[k + 1][i] = min(f[k][i], f[k][i + (1 << k)]);
}
ll ask(int l, int r)
{
int k = log2(r - l + 1);
return min(f[k][l], f[k][r + 1 - (1 << k)]);
}
};
ll cal(SufArr &sa, SparseTable &st, int k) //原串中至少出现k次的子串数量
{
ll ans = 0;
if (k > 1)
for (int l = 2, r = k; r < sa.h.size(); ++l, ++r)
ans += max(st.ask(l, r) - sa.h[l - 1], 0);
else
for (int i = 1; i < sa.h.size(); ++i)
ans += sa.h.size() - 1 - sa.sa[i] - sa.h[i];
return ans;
}
char s[2000009];
int main()
{
for (int a, b; ~scanf("%s%d%d", s, &a, &b);)
{
SufArr sa(vector<int>(s, s + strlen(s) + 1), 'Z' + 1);
SparseTable st(sa.h);
printf("%lld\n", cal(sa, st, a) - cal(sa, st, b + 1));
}
}
Save the Room
#include <stdio.h>
int main()
{
for (int a, b, c; ~scanf("%d%d%d", &a, &b, &c);)
printf(a % 2 && b % 2 && c % 2 ? "No\n" : "Yes\n");
}
Participate in E-sports
交了个高精度开根号上去。
#include <cmath>
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
struct Wint : vector<int> //继承vector
{
static const int width = 9, base = 1e9;
Wint(unsigned long long n = 0) //普通初始化，当整型数和Wint同时运算时会提升至Wint
{
for (; n; n /= base)
push_back(n % base);
}
explicit Wint(const string &s) //字符串初始化函数，未判断字符串合法情况
{
for (int len = int(s.size() - 1) / width + 1, b, e, i = 0; i < len; ++i)
for (e = s.size() - i * width, b = max(0, e - width), push_back(0); b != e; ++b)
back() = back() * 10 + s[b] - '0';
trim(0);
}
Wint &trim(bool up = 1) //去前导0，是否需要进位，很常用的小函数，为方便返回自身
{
for (int i = 1; up && i < size(); ++i)
{
if ((*this)[i - 1] < 0)
--(*this)[i], (*this)[i - 1] += base;
if ((*this)[i - 1] >= base)
(*this)[i] += (*this)[i - 1] / base, (*this)[i - 1] %= base;
}
while (!empty() && back() <= 0)
pop_back();
for (; up && !empty() && back() >= base; (*this)[size() - 2] %= base)
push_back(back() / base);
return *this;
}
friend istream &operator>>(istream &is, Wint &n)
{
string s; //懒
return is >> s, n = Wint(s), is;
}
friend ostream &operator<<(ostream &os, const Wint &n)
{
if (n.empty())
return os.put('0');
os << n.back();
char ch = os.fill('0');
for (int i = n.size() - 2; ~i; --i)
os.width(n.width), os << n[i];
return os.fill(ch), os;
}
friend bool operator<(const Wint &a, const Wint &b)
{
if (a.size() != b.size())
return a.size() < b.size();
for (int i = a.size() - 1; ~i; --i)
if (a[i] != b[i])
return a[i] < b[i];
return 0;
}
friend bool operator>(const Wint &a, const Wint &b)
{
return b < a;
}
friend bool operator<=(const Wint &a, const Wint &b)
{
return !(a > b);
}
friend bool operator>=(const Wint &a, const Wint &b)
{
return !(a < b);
}
Wint &operator+=(const Wint &b)
{
if (size() < b.size())
resize(b.size()); //保证有足够的位数
for (int i = 0; i < b.size(); ++i)
(*this)[i] += b[i];
return trim(); //单独进位防自运算
}
friend Wint operator+(Wint a, const Wint &b)
{
return a += b;
}
Wint &operator++() //前置版本
{
return *this += 1; //懒
}
Wint operator++(int) //后置版本
{
Wint b(*this);
return ++*this, b;
}
Wint &operator-=(const Wint &b) //a<b会使a变为0
{
if (size() < b.size())
resize(b.size()); //保证有足够的位数
for (int i = 0; i < b.size(); ++i)
(*this)[i] -= b[i];
return trim(); //单独进位防自运算
}
friend Wint operator-(Wint a, const Wint &b)
{
return a -= b;
}
Wint &operator--() //前置版本
{
return *this -= 1; //懒
}
Wint operator--(int) //后置版本
{
Wint b(*this);
return --*this, b;
}
Wint &operator*=(const Wint &b) //高精度乘法，常规写法
{
Wint c;
c.assign(size() + b.size(), 0);
for (int j = 0, k, l; j < b.size(); ++j)
if (b[j]) //稀疏优化，特殊情况很有效
for (int i = 0; i < size(); ++i)
{
unsigned long long n = (*this)[i];
for (n *= b[j], k = i + j; n; n /= base)
c[k++] += n % base;
for (l = i + j; c[l] >= base || l + 1 < k; c[l++] %= base)
c[l + 1] += c[l] / base;
}
return swap(c), trim(0);
}
/*
Wint& operator*=(const Wint &b)//一种效率略高但对位宽有限制的写法
{
vector<unsigned long long> n(size()+b.size(),0);//防爆int
//乘法算完后统一进位效率高，防止乘法溢出（unsigned long long范围0~1.8e19）
//位宽为9时size()不能超过18（十进制162位），位宽为8时size()不能超过1800（十进制14400位）等等。
for(int j=0; j!=b.size(); ++j)
if(b[j])//稀疏优化，特殊情况很有效
for(int i=0; i!=size(); ++i)
n[i+j]+=(unsigned long long)(*this)[i]*b[j];
for(int i=1; i<n.size(); ++i)//这里用<防止位数0，单独进位防自运算
n[i]+=n[i-1]/base,n[i-1]%=base;
return assign(n.begin(),n.end()),trim(0);
}
Wint& operator*=(const Wint &b)//fft优化乘法，注意double仅15位有效数字，调小Wint::width不超过2，计算自2*log2(base)+2*log2(len)<53
{
vector<ll> ax(begin(),end()),bx(b.begin(),b.end());
ax=FFT(size()+b.size()).ask(ax,bx);
for(int i=1; i<ax.size(); ++i)
ax[i]+=ax[i-1]/base,ax[i-1]%=base;
return assign(ax.begin(),ax.end()),trim(0);
}
Wint& operator*=(const Wint &b)//ntt优化，Wint::width不超过2
{
vector<ll> ax(begin(),end()),bx(b.begin(),b.end());
ax=FNTT(size()+b.size(),(7<<26)+1,3).ask(ax,bx);
for(int i=1; i<ax.size(); ++i)
ax[i]+=ax[i-1]/base,ax[i-1]%=base;
return assign(ax.begin(),ax.end()),trim(0);
}
*/
friend Wint operator*(Wint a, const Wint &b)
{
return a *= b;
}
Wint &operator/=(Wint b)
{
Wint r, c, d = b.base / (b.back() + 1);
*this *= d, b *= d, c.assign(size(), 0);
for (int i = size() - 1; ~i; --i)
{
r.insert(r.begin(), (*this)[i]);
unsigned long long s = 0;
for (int j = b.size(); j + 1 >= b.size(); --j) //b.size()==0肯定第一行就出问题的
s = s * b.base + (j < r.size() ? r[j] : 0);
for (d = c[i] = s / b.back(), d *= b; r < d; r += b)
--c[i];
r -= d;
}
return swap(c), trim(0); //r为加倍后的余数，可通过高精度除低精度得到真正余数，此处略
}
friend Wint operator/(Wint a, const Wint &b)
{
return a /= b;
}
Wint &operator%=(const Wint &b)
{
return *this -= *this / b * b;
}
friend Wint operator%(Wint a, const Wint &b)
{
return a %= b;
}
//开平方，改自ZJU模板
bool cmp(long long c, int d, const Wint &b) const
{
if ((int)b.size() - (int)size() < d + 1 && c)
return 1;
long long t = 0;
for (int i = b.size() - 1, lo = -(base << 1); lo <= t && t <= 0 && ~i; --i)
if (t = t * base - b[i], 0 <= i - d - 1 && i - d - 1 < size())
t += (*this)[i - d - 1] * c;
return t > 0;
}
Wint &sub(const Wint &b, long long k, int d)
{
int l = b.size() + d;
for (int i = d + 1; i <= l; ++i)
{
long long tmp = (*this)[i] - k * b[i - d - 1];
if (tmp < 0)
{
(*this)[i + 1] += (tmp - base + 1) / base;
(*this)[i] = tmp - (tmp - base + 1) / base * base;
}
else
(*this)[i] = tmp;
}
for (int i = l + 1; i < size() && (*this)[i] < 0; ++i)
{
(*this)[i + 1] += ((*this)[i] - base + 1) / base;
(*this)[i] -= ((*this)[i] - base + 1) / base * base;
}
return trim(0);
}
friend Wint sqrt(Wint a)
{
Wint n;
n.assign(a.size() + 1 >> 1, 0);
for (int i = n.size() - 1, l, r; ~i; --i)
{
for (l = 0, r = a.base, n[i] = l + r >> 1; r - l > 1; n[i] = l + r >> 1)
{
if (n.cmp(n[i], i - 1, a))
r = n[i];
else
l = n[i];
}
a.sub(n, n[i], i - 1), n[i] += l + r >> 1;
}
for (int i = 0; i < n.size(); ++i)
n[i] >>= 1;
return n.trim(0);
}
/*
friend Wint sqrt(const Wint &a)//常规牛顿迭代实现的开平方算法，慢但是好敲
{
Wint b=a,c=(b+1)/2;
while(b!=c)swap(b,c),c=(b+a/b)/2;
return c;
}
friend Wint sqrt(const Wint &a)
{
Wint ret,t;
ret.assign((a.size()+1)>>1,0);
for(int i=ret.size()-1,l,r; ~i; --i)
{
for(l=0,r=a.base; r-l>1;)
{
ret[i]=l+(r-l)/2;
t=ret*ret;
if(a<t)r=ret[i];
else l=ret[i];
}
if(!l&&i==ret.size()-1)ret.pop_back();
else ret[i]=l;
}
return ret;
}
*/
};
int check(Wint n)
{
Wint sn = sqrt(n);
return sn * sn == n;
}
int main()
{
int t;
for (cin >> t; t--;)
{
Wint n;
cin >> n;
int ans = check(n) * 2 + check(n * (n - 1) / 2);
cout << (ans == 0 ? "League of Legends\n" : ans == 1 ? "Clash Royale\n" : ans == 2 ? "Hearth Stone\n" : "Arena of Valor\n");
}
}
Transport Ship
拆成 01 背包。
#include <stdio.h>
#include <string.h>
const int N = 511, S = 32767 >> 1, M = 1e9 + 7;
int t, n, q, m, v[N], f[N][S];
int main()
{
for (scanf("%d", &t); t--;)
{
scanf("%d%d", &n, &q);
for (int i = m = 0, V, C; i < n; ++i)
{
scanf("%d%d", &V, &C);
for (int i = 0; i < C; ++i)
v[++m] = (1 << i) * V;
}
for (int i = f[0][0] = 1; i <= m; ++i)
for (int s = 0; s < S; ++s)
if (f[i][s] = f[i - 1][s], s >= v[i])
f[i][s] = (f[i][s] + f[i - 1][s - v[i]]) % M;
for (int i = 0, s; i < q; ++i)
{
scanf("%d", &s);
printf("%d\n", f[m][s]);
}
}
}
Poor God Water
矩阵乘一下。
#include <cstdio>
#include <algorithm>
#define mul(a, b, c) (1LL * (a) * (b) % (c))
using namespace std;
typedef long long ll;
const ll N = 9, M = 1e9 + 7;
struct Matrix
{
static int n;
ll a[N][N];
Matrix(ll k = 0)
{
for (int i = 0; i < n; ++i)
fill(a[i], a[i] + n, 0), a[i][i] = k;
}
ll *operator[](int n)
{
return a[n];
}
};
int Matrix::n = N;
Matrix operator*(const Matrix &a, const Matrix &b)
{
Matrix r(0);
for (int i = 0; i < r.n; ++i)
for (int j = 0; j < r.n; ++j)
for (int k = 0; k < r.n; ++k)
r.a[i][j] = (r.a[i][j] + mul(a.a[i][k], b.a[k][j], M)) % M;
return r;
}
Matrix pow(Matrix a, ll b)
{
Matrix r(1);
for (; b; b >>= 1, a = a * a)
if (b & 1)
r = r * a;
return r;
}
int main()
{
ll t, n, ans;
for (scanf("%lld", &t); t--;)
{
scanf("%lld", &n);
if (n < 3)
{
printf("%d\n", n == 1 ? 3 : 9);
continue;
}
Matrix A, P;
for (int i = 0; i < N; ++i)
A[i][0] = 1;
P[0][3] = P[0][6] = 1;
P[1][0] = P[1][3] = P[1][6] = 1;
P[2][0] = P[2][3] = 1;
P[3][1] = P[3][4] = P[3][7] = 1;
P[4][1] = P[4][7] = 1;
P[5][1] = P[5][4] = 1;
P[6][5] = P[6][8] = 1;
P[7][2] = P[7][8] = 1;
P[8][2] = P[8][5] = 1;
A = pow(P, n - 2) * A;
for (int i = ans = 0; i < N; ++i)
ans = (ans + A[i][0]) % M;
printf("%lld\n", ans);
}
}