#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f3f3f3f3f;
ll calc(ll x,char op,ll y)
{
if (op=='+') return x+y;
if (op=='-') return x-y;
if (op=='*') return x*y;
if (op=='/') return x/y;
}
ll dp[1010][10][3],n,m,k,a[1010];
char s[11];
int main()
{
int T;
scanf("%d",&T);
while (T--)
{
memset(dp,0,sizeof(dp));
scanf("%lld%lld%lld",&n,&m,&k);
for (int i=1; i<=n; i++)
{
scanf("%lld",&a[i]);
}
scanf("%s",s+1);
for (int i=0; i<=n; i++)
{
for (int j=0; j<=m; j++)
{
dp[i][j][1]=-inf;
dp[i][j][0]=inf;
}
}
for (int i=0; i<=n; i++)
{
dp[i][0][1]=dp[i][0][0]=k;
}
for (ll i=1; i<=n; i++)
{
for (ll j=1; j<=min(i,m); j++)
{
dp[i][j][1]=max(dp[i-1][j][1],calc(dp[i-1][j-1][1],s[j],a[i]));
dp[i][j][1]=max(dp[i][j][1],calc(dp[i-1][j-1][0],s[j],a[i]));
dp[i][j][0]=min(dp[i-1][j][0],calc(dp[i-1][j-1][0],s[j],a[i]));
dp[i][j][0]=min(dp[i][j][0],calc(dp[i-1][j-1][1],s[j],a[i]));
}
}
ll ans=-inf;
for (ll i=m; i<=n; i++)
{
ans=max(ans,dp[i][m][1]);
}
printf("%lld
",ans);
}
}
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1000000007;
ll n,m;
struct node
{
ll a[9][9];
node()
{
memset(a,0,sizeof(a));
}
node operator*(const node &b) const
{
node res;
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
res.a[i][j] = 0;
for (int k = 0; k < 9; k++)
{
res.a[i][j] = (res.a[i][j] + a[i][k] * b.a[k][j]%mod) % mod;
}
}
}
return res;
}
};
node pow(node b,ll c)
{
node res;
for (int i=0; i<9; i++)
{
res.a[i][i]=1;
}
while (c)
{
if (c & 1)
{
res = res * b;
}
c >>= 1;
b = b * b;
}
return res;
}
int a[9][9]={
0,1,1,0,0,0,0,0,0,
0,0,0,1,1,1,0,0,0,
0,0,0,0,0,0,1,0,1,
1,1,1,0,0,0,0,0,0,
0,0,0,1,0,1,0,0,0,
0,0,0,0,0,0,0,1,1,
1,1,0,0,0,0,0,0,0,
0,0,0,1,1,0,0,0,0,
0,0,0,0,0,0,1,1,0};
node f;
int main()
{
for (int i=0; i<9; i++)
{
for (int j=0; j<9; j++)
f.a[i][j]=a[i][j];
}
int T;
scanf("%d",&T);
while (T--)
{
scanf("%lld",&n);
if (n==1){
printf("3
");
continue;
}
if (n==2){
printf("9
");
continue;
}
node ans=pow(f,n-2);
ll ans1=0;
for (int i=0; i<9; i++)
{
for (int j=0; j<9; j++)
{
ans1=(ans1+ans.a[i][j])%mod;
}
}
printf("%lld
",ans1);
}
}
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<n;i++)
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
const ll mod = 1e9+7;
ll powmod(ll a,ll b) {
ll ret = 1;
a%=mod;
while(b) {
if(b&1) ret = ret*a%mod;
a = a*a%mod;
b>>=1;
}
return ret;
}
int _,n;
namespace linear_seq {
const int N = 10010;
ll res[N],base[N],_c[N],_md[N];
vector<int> Md;
void mul(ll *a,ll *b,int k) {
for(int i=0; i<k+k; i++)
_c[i] = 0;
for(int i=0; i<k; ++i)
if(a[i])
for(int j=0; j<k; j++)
_c[i+j] = (_c[i+j]+a[i]*b[j])%mod;
for(int i=k+k-1; i>=k; i--)
if(_c[i])
for(int j=0; j<(int) Md.size(); j++)
_c[i-k+Md[j]] = (_c[i-k+Md[j]]-_c[i]*_md[Md[j]])%mod;
for(int i=0; i<k; i++)
a[i] = _c[i];
}
int solve(ll n,VI a,VI b) {
ll ans = 0,pnt = 0;
int k = SZ(a);
for(int i=0; i<k; i++)
_md[k-1-i] = -a[i];
_md[k] = 1;
Md.clear();
for(int i=0; i<k; i++)
if(_md[i]!=0)
Md.push_back(i);
for(int i=0; i<k; i++)
res[i] = base[i] = 0;
res[0] = 1;
while((1ll<<pnt)<=n)
pnt++;
for(int p = pnt; p>=0; p--) {
mul(res,res,k);
if((n>>p)&1) {
for(int i=k-1; i>=0; i--) res[i+1] = res[i];
res[0] = 0;
for(int j=0; j<(int) Md.size(); ++j)
res[Md[j]] = (res[Md[j]]-res[k]*_md[Md[j]])%mod;
}
}
rep(i,0,k) ans = (ans+res[i]*b[i])%mod;
if(ans<0) ans+=mod;
return ans;
}
VI BM(VI s) {
VI C(1,1),B(1,1);
int L = 0,m = 1,b = 1;
for(int n=0; n<(int)s.size(); ++n) {
ll d = 0;
for(int i=0; i<L+1; i++)
d = (d+(ll)C[i]*s[n-i])%mod;
if(d==0) ++m;
else if(2*L<=n) {
VI T=C;
ll c = mod-d*powmod(b,mod-2)%mod;
while(SZ(C)<SZ(B)+m)
C.push_back(0);
for(int i=0; i<(int) B.size(); i++)
C[i+m] = (C[i+m]+c*B[i])%mod;
L = n+1-L;
B = T;
b = d;
m = 1;
} else {
ll c = mod-d*powmod(b,mod-2)%mod;
while(SZ(C)<SZ(B)+m)
C.push_back(0);
for(int i=0; i<(int)B.size(); i++)
C[i+m] = (C[i+m]+c*B[i])%mod;
++m;
}
}
return C;
}
ll gao(VI a,ll n) {
VI c = BM(a);
c.erase(c.begin());
for(int i=0; i<(int) c.size(); i++)
c[i] = (mod-c[i])%mod;
return (ll) solve(n,c,VI(a.begin(),a.begin()+SZ(c)));
}
}
int main() {
ll t;
ll nnn;
VI a;
a.push_back(3);
a.push_back(9);
a.push_back(20);
a.push_back(46);
a.push_back(106);
a.push_back(244);
a.push_back(560);
a.push_back(1286);
a.push_back(2956);
a.push_back(6794);
scanf("%lld",&t);
while(t--) {
scanf("%lld",&nnn);
printf("%lld
",linear_seq::gao(a,nnn-1));
}
}
#include <bits/stdc++.h>
using namespace std;
int T;
int n,q;
int v,c;
typedef long long ll;
const ll mod=1e9+7;
ll dp[10005];
int main()
{
scanf("%d",&T);
while(T--)
{
memset(dp,0,sizeof dp);
dp[0]=1;
scanf("%d %d",&n,&q);
for(int i=1;i<=n;++i)
{
scanf("%d %d",&v,&c);
for(int j=0;j<c;++j)
{
int V=v<<j;
for(int k=10000;k>=V;--k)
{
dp[k]+=dp[k-V];
dp[k]%=mod;
}
}
}
while(q--)
{
int x;
scanf("%d",&x);
printf("%lld
",dp[x]);
}
}
return 0;
}
import java.util.Scanner;
import java.math.BigInteger;
public class Main {
public static void main(String[] args){
Scanner cin=new Scanner(System.in);
int T=cin.nextInt();
for(int i=1;i<=T;i+=1){
BigInteger S=cin.nextBigInteger();
BigInteger k1=BigInteger.valueOf(1);
BigInteger k2=BigInteger.valueOf(2);
BigInteger k3=S.subtract(k1);
BigInteger X=S.multiply(k3).divide(k2);
BigInteger l=k1;
BigInteger r=S;
int f1=0;
for (;;){
BigInteger sum=l.add(r);
BigInteger mid=sum.divide(k2);
BigInteger k=mid.multiply(mid);
int tmp=k.compareTo(S);
if (tmp==0){
f1=1;
break;
}
if (tmp>0){
r=mid.subtract(k1);
}
if (tmp<0){
l=mid.add(k1);
}
int tmp1=l.compareTo(r);
if (tmp1>0){
break;
}
}
int f2=0;
l=k1;
r=X;
for (;;){
BigInteger sum=l.add(r);
BigInteger mid=sum.divide(k2);
BigInteger k=mid.multiply(mid);
int tmp=k.compareTo(X);
if (tmp==0){
f2=1;
break;
}
if (tmp>0){
r=mid.subtract(k1);
}
if (tmp<0){
l=mid.add(k1);
}
int tmp1=l.compareTo(r);
if (tmp1>0){
break;
}
}
if(f1==1&&f2==1){
System.out.println("Arena of Valor");
}
if(f1==1&&f2==0){
System.out.println("Hearth Stone");
}
if(f1==0&&f2==1){
System.out.println("Clash Royale");
}
if(f1==0&&f2==0)
{
System.out.println("League of Legends");
}
}
}
}
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
string str;
int a,b,c;
int main() {
//freopen("1.txt","r",stdin);
while(scanf("%d%d%d",&a,&b,&c)!=EOF){
if(a%2==0||b%2==0||c%2==0){
puts("Yes");
}
else puts("No");
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 10;
const ll mod=1000000007;
int T;
char str[maxn];
ll fast_pow(ll a,ll b) {
ll ans = 1;
while (b) {
if (b & 1)ans = ans * a % mod;
a = a * a % mod;
b >>= 1;
}
return ans;
}
int main() {
//freopen("1.txt","r",stdin);
scanf("%d", &T);
while (T--) {
scanf("%s", str);
int len = strlen(str);
ll cur = 0;
for (int i = 0; i <len; i++) {
cur = (cur * 10 + str[i] - '0') % (mod - 1);
}
cur = (cur - 1 + mod - 1) % (mod - 1);
cur = fast_pow(2, cur);
printf("%lld
", cur);
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
int T;
string str;
int main() {
//freopen("1.txt","r",stdin);
scanf("%d",&T);
while(T--){
cin>>str;
int len=str.length();
for (int i=0;i<len;i++){
if ('A'<=str[i]&&str[i]<='Z'){
str[i]+=32;
}
}
if (str=="jessie"){
puts("Good guy!");
}else{
puts("Dare you say that again?");
}
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+100;
char s[maxn];
struct SAM
{
int next[maxn<<1][26];
int link[maxn<<1],step[maxn<<1];
ll endpos[maxn<<1];
int b[maxn<<1],a[maxn<<1];
int sz,last,len;
void init()
{
memset(next,0,sizeof(next));
memset(endpos,0,sizeof(endpos));
memset(a,0,sizeof(a));
memset(a,0,sizeof(b));
sz=last=1;
}
void add(int c)
{
int p=last;
int np=++sz;
last=np;
endpos[np]=1;
step[np]=step[p]+1;
while (!next[p][c]&&p)
{
next[p][c]=np;
p=link[p];
}
if (p==0)
{
link[np]=1;
}
else
{
int q=next[p][c];
if (step[p]+1==step[q])
{
link[np]=q;
}
else
{
int clone=++sz;
memcpy(next[clone],next[q],sizeof(next[q]));
step[clone]=step[p]+1;
link[clone]=link[q];
link[q]=link[np]=clone;
while (next[p][c]==q&&p)
{
next[p][c]=clone;
p=link[p];
}
}
}
}
void build ()
{
init();
for (int i=0; i<len; i++)
{
add(s[i]-'A');
}
for (int i=1; i<=sz; i++)
{
a[step[i]]++;
}
for (int i=1; i<=len; i++)
{
a[i]+=a[i-1];
}
for (int i=1; i<=sz; i++)
{
b[a[step[i]]--]=i;
}
for (int i=sz; i>=1; i--)
{
int e=b[i];
endpos[link[e]]+=endpos[e];
}
}
void solve()
{
int A,B;
scanf("%d%d",&A,&B);
len=strlen(s);
build();
ll ans=0;
for (int i=1; i<=sz; i++)
{
if (endpos[i]>=A&&endpos[i]<=B)
{
ans+=step[i]-step[link[i]];
}
}
printf("%lld
",ans);
}
} sam;
int main()
{
while (~scanf("%s",s))
{
sam.solve();
}
}
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PI;
const int maxn=5005;
const int M=200005;
const int inf=0x3f3f3f3f;
int a[M];
int n,k,m;
struct Point{
int x,y,w;
}point[maxn];
struct Min_Cost_Max_Flow
{
struct edge
{
int to,cap,cost,rev;
edge() {};
edge(int _to,int _cap,int _cost,int _rev):to(_to),cap(_cap),cost(_cost),rev(_rev) {};
};
vector<edge>E[maxn];
int h[maxn],n,d[maxn],preV[maxn],preE[maxn];
void init(int n)
{
this->n=n;
for (int i=0; i<=n; i++)
{
E[i].clear();
h[i]=0;
}
}
void add(int from,int to,int cap,int cost)
{
E[from].push_back(edge(to,cap,cost,E[to].size()));
E[to].push_back(edge(from,0,-cost,E[from].size()-1));
}
PI dijkstra(int s,int t,int f)
{
int cost=0,flow=0;
for (int i=0; i<=n; i++)
{
h[i]=0;
}
while (f)
{
priority_queue<PI,vector<PI>,greater<PI> >q;
for (int i=0; i<=n; i++)
{
d[i]=inf;
}
d[s]=0;
q.push(make_pair(0,s));
while (!q.empty())
{
PI now=q.top();
q.pop();
int v=now.second;
if (d[v]<now.first)
{
continue;
}
for (int i=0; i<E[v].size(); i++)
{
edge &e=E[v][i];
if (e.cap>0&&d[e.to]>d[v]+e.cost+h[v]-h[e.to])
{
d[e.to]=d[v]+e.cost+h[v]-h[e.to];
preV[e.to]=v;
preE[e.to]=i;
q.push(make_pair(d[e.to],e.to));
}
}
}
if (d[t]==inf)break;
for (int i=0; i<=n; i++)
{
h[i]+=d[i];
}
int d=f;
for (int i=t; i!=s; i=preV[i])
{
d=min(d,E[preV[i]][preE[i]].cap);
}
f-=d;
flow+=d;
cost+=d*h[t];
for (int i=t; i!=s; i=preV[i])
{
edge &e=E[preV[i]][preE[i]];
e.cap-=d;
E[i][e.rev].cap+=d;
}
}
return make_pair(flow,cost);
}
} G;
int main()
{
int T;
scanf("%d",&T);
while (T--)
{
scanf("%d%d%d",&n,&k,&m);
for (int i=1; i<=m; i++)
{
scanf("%d%d%d",&point[i].x,&point[i].y,&point[i].w);
point[i].y++;
}
for (int i=1;i<=m;i++){
a[i]=point[i].x;
a[i+m]=point[i].y;
}
sort(a+1,a+m*2+1);
int nn=unique(a+1,a+m*2+1)-a-1;
G.init(nn+2);
for (int i=1;i<=m;i++){
point[i].x=lower_bound(a+1,a+1+nn,point[i].x)-a;
point[i].y=lower_bound(a+1,a+1+nn,point[i].y)-a;
}
for (int i=1;i<=nn;i++) {
G.add(i,i+1,k,0);
}
for (int i=1;i<=m;i++) {
G.add(point[i].x,point[i].y,1,-point[i].w);
}
G.add(nn+2,1,k,0);
PI ans=G.dijkstra(nn+2,nn+1,inf);
printf("%d
",-ans.second);
}
}
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const ull mod=18446744073709551615;
const int maxn=100010;
struct node1{
int v;
int next;
}e[maxn*2];
struct node2{
int l,r;
ull val,lazy1,lazy2;
}tree[maxn*4];
int head[maxn],fa[maxn],deep[maxn],sum[maxn],son[maxn],top[maxn],mp1[maxn],mp2[maxn];
int q,n,num;
void add(int u,int v){
num++;
e[num].v=v;
e[num].next=head[u];
head[u]=num;
}
void dfs1(int u) {
sum[u] = 1;
son[u] = -1;
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].v;
if (v != fa[u]) {
fa[v] = u;
deep[v] = deep[u] + 1;
dfs1(v);
sum[u] += sum[v];
if (son[u] == -1 || sum[son[u]] < sum[v]) {
son[u] = v;
}
}
}
}
void dfs2(int u,int tp) {
num++;
top[u] = tp;
mp1[u] = num;
mp2[num] = u;
if (son[u] == -1) {
return;
}
dfs2(son[u], tp);
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].v;
if (v != fa[u] && v != son[u]) {
dfs2(v, v);
}
}
}
void change1(int rt,ull val) {
tree[rt].val = tree[rt].val + val * (tree[rt].r - tree[rt].l + 1);
}
void change2(int rt,ull val) {
tree[rt].val = tree[rt].val * val;
}
void pushup(int rt) {
tree[rt].val = tree[rt << 1].val + tree[rt << 1 | 1].val;
}
void pushdown(int rt){
if (tree[rt].lazy1!=0||tree[rt].lazy2!=1){
change2(rt<<1,tree[rt].lazy2);
change1(rt<<1,tree[rt].lazy1);
tree[rt<<1].lazy2=tree[rt<<1].lazy2*tree[rt].lazy2;
tree[rt<<1].lazy1=tree[rt<<1].lazy1*tree[rt].lazy2+tree[rt].lazy1;
change2(rt<<1|1,tree[rt].lazy2);
change1(rt<<1|1,tree[rt].lazy1);
tree[rt<<1|1].lazy2=tree[rt<<1|1].lazy2*tree[rt].lazy2;
tree[rt<<1|1].lazy1=tree[rt<<1|1].lazy1*tree[rt].lazy2+tree[rt].lazy1;
tree[rt].lazy2=1;
tree[rt].lazy1=0;
}
}
void build(int rt,int l,int r) {
tree[rt].l = l;
tree[rt].r = r;
tree[rt].val = 0;
tree[rt].lazy1 = 0;
tree[rt].lazy2 = 1;
if (l==r){
return;
}
int mid = (l + r) >> 1;
build(rt << 1, l, mid);
build(rt << 1 | 1, mid + 1, r);
pushup(rt);
}
void update2(int op,int pl,int pr,ull val,int rt) {
if (pl <= tree[rt].l && tree[rt].r <= pr) {
if (op == 1) {
change1(rt, val);
tree[rt].lazy1 += val;
} else {
change2(rt, val);
tree[rt].lazy1 *= val;
tree[rt].lazy2 *= val;
}
return;
}
pushdown(rt);
if (pl <= tree[rt << 1].r) {
update2(op, pl, pr, val, rt << 1);
}
if (pr >= tree[rt << 1 | 1].l) {
update2(op, pl, pr, val, rt << 1 | 1);
}
pushup(rt);
}
void update1(int op,int u,int v,ull val) {
while (top[u] != top[v]) {
if (deep[top[u]] < deep[top[v]]) {
swap(u, v);
}
update2(op, mp1[top[u]], mp1[u], val, 1);
u = fa[top[u]];
}
if (deep[u] < deep[v]) {
swap(u, v);
}
update2(op, mp1[v], mp1[u], val, 1);
}
ull query2(int pl,int pr,int rt) {
if (pl <= tree[rt].l && tree[rt].r <= pr) {
return tree[rt].val;
}
ull res = 0;
pushdown(rt);
if (pl <= tree[rt << 1].r) {
res += query2(pl, pr, rt << 1);
}
if (pr >= tree[rt << 1 | 1].l) {
res += query2(pl, pr, rt << 1|1);
}
return res;
}
ull query1(int u,int v) {
ull res = 0;
while (top[u] != top[v]) {
if (deep[top[u]] < deep[top[v]]) {
swap(u, v);
}
res += query2(mp1[top[u]], mp1[u], 1);
u = fa[top[u]];
}
if (deep[u] < deep[v]) {
swap(u, v);
}
res += query2(mp1[v], mp1[u], 1);
return res;
}
int main() {
ull w;
int op, u, v;
while (~scanf("%d", &n)) {
memset(head, 0, sizeof(head));
num = 0;
for (int i = 2; i <= n; i++) {
scanf("%d", &u);
add(u, i);
add(i, u);
}
fa[1] = 0;
deep[1] = 1;
dfs1(1);
num = 0;
dfs2(1, 1);
build(1, 1, n);
scanf("%d", &q);
while (q--) {
scanf("%d", &op);
if (op == 1) {
scanf("%d%d%llu", &u, &v, &w);
update1(2, u, v, w);
}
if (op == 2) {
scanf("%d%d%llu", &u, &v, &w);
update1(1, u, v, w);
}
if (op == 3) {
scanf("%d%d", &u, &v);
update1(2, u, v, -1);
update1(1, u, v, mod);
}
if (op == 4) {
scanf("%d%d", &u, &v);
printf("%llu
", query1(u, v));
}
}
}
return 0;
}