当前位置：首页 > news >正文

ACM-ICPC 2018 焦作赛区网络预赛

news 来源：原创 2024/5/9 2:53:45

这场打得还是比较爽的，但是队友差一点就再过一题，还是难受啊。

每天都有新的难过

A. Magic Mirror

Jessie has a magic mirror.

Every morning she will ask the mirror: 'Mirror mirror tell me, who is the most beautiful girl in the world?' If the mirror says her name, she will praise the mirror: 'Good guy!', but if the mirror says the name of another person, she will assail the mirror: 'Dare you say that again?'

Today Jessie asks the mirror the same question above, and you are given a series of mirror's answers. For each answer, please output Jessie's response. You can assume that the uppercase or lowercase letters appearing anywhere in the name will have no influence on the answer. For example, 'Jessie' and 'jessie' represent the same person.

Input

The first line contains an integer $\le T \le 100)T(1≤T≤100), which is the number of test cases.$

Each test case contains one line with a single-word name, which contains only English letters. The length of each name is no more than

Output

For each test case, output one line containing the answer.

样例输入复制

2
Jessie
Justin

样例输出复制

Good guy!
Dare you say that again?

题目来源

ACM-ICPC 2018 焦作赛区网络预赛

大小写转换一下

#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lson l,(l+r)/2,rt<<1
#define rson (l+r)/2+1,r,rt<<1|1
#define dbg(x) cout<<#x<<" = "<< (x)<< endl
#define pb push_back
#define fi first
#define se second
#define sz(x) (int)(x).size()
#define pll pair<long long,long long>
#define pii pair<int,int>
#define pq priority_queue
const int N=1e5+5,MD=1e9+7,INF=0x3f3f3f3f;
const ll LL_INF=0x3f3f3f3f3f3f3f3f;
const double eps=1e-9,e=exp(1),PI=acos(-1.);
int a[N];
int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int T;
    cin>>T;
    while(T--)
    {
        string s;
        cin>>s;
        for(int i=0;s[i];i++)if(s[i]>='A'&&s[i]<='Z')s[i]+=32;
        if(s=="jessie")cout<<"Good guy!\n";
        else cout<<"Dare you say that again?\n";
    }
    return 0;
}

B. Mathematical Curse

A prince of the Science Continent was imprisoned in a castle because of his contempt for mathematics when he was young, and was entangled in some mathematical curses. He studied hard until he reached adulthood and decided to use his knowledge to escape the castle.

There are $i^{th}ith room, there is a wizard who has a resentment value of a[i]a[i]. The prince has MM curses, the j^{th}jthcurse is f[j]f[j], and f[j]f[j] represents one of the four arithmetic operations, namely addition('+'), subtraction('-'), multiplication('*'), and integer division('/'). The prince's initial resentment value is KK. Entering a room and fighting with the wizard will eliminate a curse, but the prince's resentment value will become the result of the arithmetic operation f[j]f[j] with the wizard's resentment value. That is, if the prince eliminates the j^{th}jth curse in the i^{th}ithroom, then his resentment value will change from xx to (x\ f[j]\ a[i]x f[j] a[i]), for example, when x=1, a[i]=2, f[j]=x=1,a[i]=2,f[j]='+', then xxwill become 1+2=31+2=3.$

Before the prince escapes from the castle, he must eliminate all the curses. He must go from $N\ge MN≥M). What is the maximum resentment value that the prince may have when he leaves the castle?$

Input

The first line contains an integer $\le T \le 1000)T(1≤T≤1000), which is the number of test cases.$

For each test case, the first line contains three non-zero integers: $\le N \le 1000), M(1 \le M \le 5)N(1≤N≤1000),M(1≤M≤5)and K(-1000 \le K \le 1000K(−1000≤K≤1000), the second line contains NN non-zero integers: a[1], a[2], ..., a[N](-1000 \le a[i] \le 1000)a[1],a[2],...,a[N](−1000≤a[i]≤1000), and the third line contains MM characters: f[1], f[2], ..., f[M](f[j] =f[1],f[2],...,f[M](f[j]='+','-','*','/', with no spaces in between.$

Output

For each test case, output one line containing a single integer.

样例输入复制

样例输出复制

2
6
3

题目来源

ACM-ICPC 2018 焦作赛区网络预赛

有一个负的，还有一个正的，所以都要进入dp

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=1LL<<62;
ll dp1[1005][6],dp2[1005][6];
int a[1005];
char s[10];
ll calc(ll x,char c,int y)
{
    if(c=='-') return x-y;
    if(c=='+') return x+y;
    if(c=='/') return x/y;
    if(c=='*') return x*y;
}
int main()
{
    int T,n,m,k;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d%d",&n,&m,&k);
        for(int i=0;i<=n;i++)
            for(int j=0;j<=m;j++)
                dp1[i][j]=-INF,dp2[i][j]=INF;
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        for(int i=0;i<=n;i++)
            dp1[i][0]=dp2[i][0]=k;
        scanf("%s",s+1);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
            {
                dp1[i][j]=dp1[i-1][j];
                dp2[i][j]=dp2[i-1][j];
                if(dp1[i-1][j-1]!=-INF) dp1[i][j]=max(dp1[i][j],calc(dp1[i-1][j-1],s[j],a[i]));
                if(dp2[i-1][j-1]!=INF) dp1[i][j]=max(dp1[i][j],calc(dp2[i-1][j-1],s[j],a[i]));
                if(dp1[i-1][j-1]!=-INF) dp2[i][j]=min(dp2[i][j],calc(dp1[i-1][j-1],s[j],a[i]));
                if(dp2[i-1][j-1]!=INF) dp2[i][j]=min(dp2[i][j],calc(dp2[i-1][j-1],s[j],a[i]));
            }
        printf("%lld\n",dp1[n][m]);
    }
    return 0;
}

E. Jiu Yuan Wants to Eat

You ye Jiu yuan is the daughter of the Great GOD Emancipator. And when she becomes an adult, she will be queen of Tusikur, so she wanted to travel the world while she was still young. In a country, she found a small pub called Whitehouse. Just as she was about to go in for a drink, the boss Carola appeared. And ask her to solve this problem or she will not be allowed to enter the pub. The problem description is as follows:

There is a tree with

The answer modulo $2^{64}264.$

Jiu Yuan is a clever girl, but she was not good at algorithm, so she hopes that you can help her solve this problem. Ding $\backsim\backsim\backsim∽∽∽$

The bitwise NOT is a unary operation that performs logical negation on each bit, forming the ones' complement of the given binary value. Bits that are

NOT 0111 (decimal 7) = 1000 (decimal 8)

NOT 10101011 = 01010100

Input

The input contains multiple groups of data.

For each group of data, the first line contains a number of

The second line contains $b_ibi, which means that the father node of node (i +1)(i+1) is b_ibi.$

The third line contains one integer

The next

At first, we input one integer opt

$\le n,m,u,v \le 10^51≤n,m,u,v≤105$

$\le x < 2^{64}1≤x<264$

Output

For each operation

样例输入复制

7
1 1 1 2 2 4
5
2 5 6 1
1 1 6 2
4 5 6
3 5 2
4 2 2
2
1
4
3 1 2
4 1 2
3 1 1
4 1 1

样例输出复制

5
18446744073709551613
18446744073709551614
0

题目来源

ACM-ICPC 2018 焦作赛区网络预赛

队友LCT差一点调出来唉

划重点按位取反是*-1+MAX

#include<iostream>
#include<cstdio>
#include<cstring>
#define N 100010
using namespace std;
typedef unsigned long long ull;
ull st[N],n,m,q,x,y,op,w,rev[N],size[N],c[N][2],fa[N];
ull mt[N],a[N],v[N],s[N];
bool isroot(ull x)
{
    return c[fa[x]][0]!=x&&c[fa[x]][1]!=x;
}
void updata(ull x)
{
    ull l=c[x][0],r=c[x][1];
    size[x]=size[l]+size[r]+1;
    s[x]=s[l]+s[r]+v[x];
}
void paint(ull x,ull cc,ull aa)
{
    if (!x) return;
    v[x]=v[x]*cc+aa;
    s[x]=s[x]*cc+size[x]*aa;
    a[x]=a[x]*cc+aa;
    mt[x]=mt[x]*cc;
}
void pushdown(ull x)
{
    ull l=c[x][0],r=c[x][1];
    if (rev[x])
    {
        rev[l]^=1;
        rev[r]^=1;
        rev[x]^=1;
        swap(c[x][0],c[x][1]);
    }
    ull aa=a[x],cc=mt[x];
    a[x]=0;
    mt[x]=1;
    if (cc!=1||aa!=0)
    {
        paint(l,cc,aa);
        paint(r,cc,aa);
    }
}
void rotata(ull x)
{
    ull y=fa[x],z=fa[y],l,r;
    if (x==c[y][0]) l=0;
    else l=1;
    r=l^1;
    if (!isroot(y))
    {
        if (c[z][0]==y)c[z][0]=x;
        else c[z][1]=x;
    }
    fa[x]=z;
    fa[y]=x;
    fa[c[x][r]]=y;
    c[y][l]=c[x][r];
    c[x][r]=y;
    updata(y);
    updata(x);
}
void splay(ull x)
{
    ull top(0);
    st[++top]=x;
    for(ull i=x; !isroot(i); i=fa[i]) st[++top]=fa[i];
    for (ull i=top; i; i--) pushdown(st[i]);
    while (!isroot(x))
    {
        ull y=fa[x],z=fa[y];
        if (!isroot(y))
        {
            if (c[y][0]==x^c[z][0]==y) rotata(x);
            else rotata(y);
        }
        rotata(x);
    }
}
void access(ull x)
{
    ull t(0);
    while (x)
    {
        splay(x);
        c[x][1]=t;
        t=x;
        updata(x);
        x=fa[x];
    }
}
void makeroot(ull x)
{
    access(x);
    splay(x);
    rev[x]^=1;
}
void link(ull x,ull y)
{
    makeroot(x);
    fa[x]=y;
}
void cut(ull x,ull y)
{
    makeroot(x);
    access(y);
    splay(y);
    c[y][0]=fa[x]=0;
}
void split(ull x,ull y)
{
    makeroot(y);
    access(x);
    splay(x);
}
int main()
{
    while(scanf("%llu",&n)!=EOF)
    {
        for (ull i=1; i<=n; i++) v[i]=0,size[i]=s[i]=mt[i]=1;
        memset(c,0,sizeof c);
        memset(fa,0,sizeof fa);
        for (ull i=2; i<=n; i++)
        {
            scanf("%llu",&y);
            link(y,i);
        }
        scanf("%llu",&q);
        for (ull i=1; i<=q; i++)
        {
            scanf("%llu%llu%llu",&op,&x,&y);
            if (op==2)//+w
            {
                scanf("%llu",&w);
                split(x,y);
                paint(x,1,w);
            }
            if (op==3)//not 2^64-1 18446744073709551615
            {
                split(x,y);
                paint(x,-1,18446744073709551615ull);
            }
            if (op==1)//*w
            {
                scanf("%llu",&w);
                split(x,y);
                paint(x,w,0);
            }
            if (op==4)//u,v
            {
                split(x,y);
                printf("%llu\n",s[x]);
            }
        }
    }
    return 0;
}

F. Modular Production Line

An automobile factory has a car production line. Now the market is oversupply and the production line is often shut down. To make full use of resources, the manager divides the entire production line into

Input

The first line of input is

The first line of each test case contains three integers,

The next $A_i, B_i, W_iAi,Bi,Wi describing a sub-product. The sub-product has value W_iWi. Only A_iAi to B_iBi parts work simultaneously will the sub-product be produced (include A_iAi to B_iBi).$

$\le T \le 1001≤T≤100$

$\le K \le M \le 2001≤K≤M≤200$

$\le N \le 10^51≤N≤105$

$\le A_i \le B_i \le N1≤Ai≤Bi≤N$

$\le W_i \le 10^51≤Wi≤105$

Output

For each test case output the maximum value in a separate line.

样例输入复制

4
10 1 3
1 2 2
2 3 4
3 4 8
10 1 3
1 3 2
2 3 4
3 4 8
100000 1 3
1 100000 100000
1 2 3
100 200 300
100000 2 3
1 100000 100000
1 150 301
100 200 300

样例输出复制

题目来源

ACM-ICPC 2018 焦作赛区网络预赛

建图网络流

先对区间的端点进行离散化，然后建边

#include<bits/stdc++.h>
using namespace std;

const int N=1e4+5;
const int M=1e5+5;
const int INF=0x3f3f3f3f;

int FIR[N],TO[M],CAP[M],FLOW[M],COST[M],NEXT[M],tote;
int pre[N],dist[N],q[400000];
bool vis[N];
int n,m,S,T;
void init()
{
    tote=0;
    memset(FIR,-1,sizeof(FIR));
}
void add(int u,int v,int cap,int cost)
{
    TO[tote]=v;
    CAP[tote]=cap;
    FLOW[tote]=0;
    COST[tote]=cost;
    NEXT[tote]=FIR[u];
    FIR[u]=tote++;

    TO[tote]=u;
    CAP[tote]=0;
    FLOW[tote]=0;
    COST[tote]=-cost;
    NEXT[tote]=FIR[v];
    FIR[v]=tote++;
}
bool SPFA(int s, int t)
{
    memset(dist,INF,sizeof(dist));
    memset(vis,false,sizeof(vis));
    memset(pre,-1,sizeof(pre));
    dist[s] = 0;
    vis[s]=true;
    q[1]=s;
    int head=0,tail=1;
    while(head!=tail)
    {
        int u=q[++head];
        vis[u]=false;
        for(int v=FIR[u]; v!=-1; v=NEXT[v])
        {
            if(dist[TO[v]]>dist[u]+COST[v]&&CAP[v]>FLOW[v])
            {
                dist[TO[v]]=dist[u]+COST[v];
                pre[TO[v]]=v;
                if(!vis[TO[v]])
                {
                    vis[TO[v]] = true;
                    q[++tail]=TO[v];
                }
            }
        }
    }
    return pre[t]!=-1;
}
void MCMF(int s, int t, int &cost, int &flow)
{
    flow=cost=0;
    while(SPFA(s,t))
    {
        int Min=INF;
        for(int v=pre[t]; v!=-1; v=pre[TO[v^1]])
            Min=min(Min, CAP[v]-FLOW[v]);
        for(int v=pre[t]; v!=-1; v=pre[TO[v^1]])
        {
            FLOW[v]+=Min;
            FLOW[v^1]-=Min;
            cost+=COST[v]*Min;
        }
        flow+=Min;
    }
}
int l[205],r[205],c[205];
int a[405],b[100005];
int main()
{
    int ca,k;
    scanf("%d",&ca);
    while(ca--)
    {
        scanf("%d%d%d",&n,&k,&m);
        init();
        int num=0;
        for(int i=1; i<=m; i++)
        {
            scanf("%d%d%d",&l[i],&r[i],&c[i]),r[i]+=1;
            a[++num]=l[i],a[++num]=r[i];
        }
        sort(a+1,a+num+1);
        num=unique(a+1,a+num+1)-a-1;
        for(int i=1;i<=num;i++)b[a[i]]=i;
        S=0;
        T=num+1;
        for(int i=0;i<=num;i++)add(i,i+1,k,0);
        for(int i=1;i<=m;i++)add(b[l[i]],b[r[i]],1,-c[i]);
        int cost,flow;
        MCMF(S,T,cost,flow);
        printf("%d\n",-cost);
    }
    return 0;
}

G. Give Candies

There are

Input

The first line contains an integer

The next

$\le T \le 1001≤T≤100$

$\le N \le 10^{100000}1≤N≤10100000$

Output

For each test case output the number of possible results (mod 1000000007).

样例输入复制

1
4

样例输出复制

题目来源

ACM-ICPC 2018 焦作赛区网络预赛

输出2^(n-1)，可以直接降幂啊，就是一个大数取余

#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lson l,(l+r)/2,rt<<1
#define rson (l+r)/2+1,r,rt<<1|1
#define dbg(x) cout<<#x<<" = "<< (x)<< endl
#define pb push_back
#define fi first
#define se second
#define sz(x) (int)(x).size()
#define pll pair<long long,long long>
#define pii pair<int,int>
#define pq priority_queue
const int N=1e5+5,MD=1e9+7,INF=0x3f3f3f3f;
const ll LL_INF=0x3f3f3f3f3f3f3f3f;
const double eps=1e-9,e=exp(1),PI=acos(-1.);
char s[N];
ll la(ll m)
{
    int l=strlen(s);
    ll ans=0;
    for(int i=0;i<l;i++)ans=(ans*10+s[i]-'0')%m;
    return ans;
}
ll lb(ll a,ll b)
{
    ll ans=1;
    for(;b;a=a*a%MD,b>>=1)if(b&1)ans=ans*a%MD;
    return ans;
}
int main()
{
    int T;
    scanf("%d",&T);
    getchar();
    while(T--)
    {
        gets(s);
        ll k=(la(MD-1)-1+MD)%MD;
        printf("%lld\n",lb(2,k));
    }
    return 0;
}

H. String and Times

Now you have a string consists of uppercase letters, two integers $\le times \le BA≤times≤B). Can you calculate the number of wonderful substrings in that string?$

Input

Input has multiple test cases.

For each line, there is a string

$\sum length(S) \le 2 \times 10^6∑length(S)≤2×106,$

$\le A \le B \le length(S)1≤A≤B≤length(S)$

Output

For each test case, print the number of the wonderful substrings in a line.

样例输入复制

AAA 2 3
ABAB 2 2

样例输出复制

2
3

题目来源

ACM-ICPC 2018 焦作赛区网络预赛

SAM直接过啊，原题

#include<stdio.h>
#include<string.h>
const int N=2e5+5;
int go[N][26],mx[N],fa[N],sa[N],w[N],s[N/2];
int k,t,last,n;
char a[N];
int newid(int x)
{
    memset(go[x],0,sizeof go[x]);
    w[x]=0;
    return x;
}
void add(int c)
{
    int p=last,np=last=newid(++t);
    mx[np]=mx[p]+1,w[np]=1;
    for(; p&&!go[p][c]; p=fa[p])go[p][c]=np;
    if(!p)fa[np]=1;
    else
    {
        int q=go[p][c];
        if(mx[q]==mx[p]+1)fa[np]=q;
        else
        {
            int nq=newid(++t);
            mx[nq]=mx[p]+1;
            memcpy(go[nq],go[q],sizeof go[q]);
            fa[nq]=fa[q];
            fa[q]=fa[np]=nq;
            for(; go[p][c]==q; p=fa[p])go[p][c]=nq;
        }
    }
}
void pre()
{
    memset(s,0,sizeof s);
    for(int i=1; i<=t; i++)s[mx[i]]++;
    for(int i=1; i<=n; i++)s[i]+=s[i-1];
    for(int i=t; i; i--)sa[s[mx[i]]--]=i;
    for(int i=t; i; i--)w[fa[sa[i]]]+=w[sa[i]];
}
int main()
{
    while(~scanf("%s",a+1))
    {
        n=strlen(a+1),t=0,last=newid(++t);
        for(int i=1; i<=n; i++)add(a[i]-'A');
        pre();
        long long ans=0;
        int l,r;
        scanf("%d%d",&l,&r);
        for(int i=2; i<=t; i++)
            if(w[i]>=l&&w[i]<=r)ans+=mx[i]-mx[fa[i]];
        printf("%lld\n",ans);
    }
    return 0;
}

I. Save the Room

Bob is a sorcerer. He lives in a cuboid room which has a length of

Input

Input has $\le 100T≤100$

For each line, there are three integers

$\le A, B, C \le 1001≤A,B,C≤100$

Output

For each test case, if Bob can save his room, print"Yes", otherwise print"No".

样例输入复制

1 1 2
1 1 4
1 1 1

样例输出复制

Yes
Yes
No

题目来源

ACM-ICPC 2018 焦作赛区网络预赛

你去组合的体积肯定是个偶数，三个奇数肯定不行啊

#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lson l,(l+r)/2,rt<<1
#define rson (l+r)/2+1,r,rt<<1|1
#define dbg(x) cout<<#x<<" = "<< (x)<< endl
#define pb push_back
#define fi first
#define se second
#define sz(x) (int)(x).size()
#define pll pair<long long,long long>
#define pii pair<int,int>
#define pq priority_queue
const int N=1e5+5,MD=1e9+7,INF=0x3f3f3f3f;
const ll LL_INF=0x3f3f3f3f3f3f3f3f;
const double eps=1e-9,e=exp(1),PI=acos(-1.);
int a[N];
int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int A,B,C;
    while(cin>>A>>B>>C)
    {

        int f=A*B*C;
        if(f&1)cout<<"No\n";
        else cout<<"Yes\n";
    }
    return 0;
}

J. Participate in E-sports

Jessie and Justin want to participate in e-sports. E-sports contain many games, but they don't know which one to choose, so they use a way to make decisions.

They have several boxes of candies, and there are $i^{th}ith box, each candy is wrapped in a piece of candy paper. Jessie opens the candy boxes in turn from the first box. Every time a box is opened, Jessie will take out all the candies inside, finish it, and hand all the candy papers to Justin.$

When Jessie takes out the candies in the $N^{th}Nth box and hasn't eaten yet, if the amount of candies in Jessie's hand and the amount of candy papers in Justin's hand are both perfect square numbers, they will choose Arena of Valor. If only the amount of candies in Jessie's hand is a perfect square number, they will choose Hearth Stone. If only the amount of candy papers in Justin's hand is a perfect square number, they will choose Clash Royale. Otherwise they will choose League of Legends.$

Now tell you the value of

Input

The first line contains an integer $\le T \le 800)T(1≤T≤800) , which is the number of test cases.$

Each test case contains one line with a single integer: $\le N \le 10^{200})N(1≤N≤10200) .$

Output

For each test case, output one line containing the answer.

样例输入复制

样例输出复制

Arena of Valor
Clash Royale
League of Legends
Hearth Stone

题目来源

ACM-ICPC 2018 焦作赛区网络预赛

判断n和n*(n-1)/2是不是平方数，直接上我们的牛顿迭代啊

import java.math.*;
import java.util.*;
public class Main {
    public static void main(String args[])
    {  
        Scanner cin=new Scanner(System.in);
        int T=cin.nextInt();
        for(int i=0;i<T;i++)
        {
            BigInteger n=cin.nextBigInteger();
            BigInteger x=cal(n);
            BigInteger y=n.multiply(n.subtract(BigInteger.valueOf(1))).shiftRight(1);
            BigInteger z=cal(y);
            if(x.multiply(x).equals(n)==true)
            {
                if(z.multiply(z).equals(y)==true)
                    System.out.println("Arena of Valor");
                else
                    System.out.println("Hearth Stone");
            }
            else
            {
                if(z.multiply(z).equals(y)==true)
                    System.out.println("Clash Royale");
                else
                    System.out.println("League of Legends");
            }
            
        }
    }
    static BigInteger cal(BigInteger x)
    {
        BigInteger ans=BigInteger.valueOf(0);
        if(x.equals(BigInteger.valueOf(0))==true)return ans;
        BigInteger rt=BigInteger.valueOf(1);
        BigInteger lst=BigInteger.valueOf(-1);
        while(true)
        {
            BigInteger nxt=rt.add(x.divide(rt)).shiftRight(1);
            if(nxt.equals(lst)==true)
            {
                if(lst.compareTo(rt)==-1)
                    return lst;
                else return rt;
            }
            lst=rt;
            rt=nxt;
        }
    }
}

二分开根的，这个可以过这个题

Game of Taking Stones

HDU - 5973

    static BigDecimal cal(int x)
    {
        BigDecimal tmp=BigDecimal.valueOf(2);
        BigDecimal xx=BigDecimal.valueOf(x);
        BigDecimal l=BigDecimal.ZERO;
        BigDecimal r=BigDecimal.valueOf(x);
        for(int i=0;i<1000;i++)
        {
            BigDecimal mid=(l.add(r)).divide(tmp);
            if(mid.multiply(mid).compareTo(xx)==1)
            {
                r=mid;
            }
            else
            {
                l=mid;
            }
        }
        return l;
    }

K. Transport Ship

There are $i^{th}ith kind of ship can carry the weight of V[i]V[i] and the number of the i^{th}ith kind of ship is 2^{C[i]} - 12C[i]−1. How many different schemes there are if you want to use these ships to transport cargo with a total weight of SS?$

It is required that each ship must be full-filled. Two schemes are considered to be the same if they use the same kinds of ships and the same number for each kind.

Input

The first line contains an integer $\le T \le 20)T(1≤T≤20), which is the number of test cases.$

For each test case:

The first line contains two integers: $\le N \le 20), Q(1 \le Q \le 10000)N(1≤N≤20),Q(1≤Q≤10000), representing the number of kinds of ships and the number of queries.$

For the next $\le V[i] \le 20), C[i](1 \le C[i] \le 20)V[i](1≤V[i]≤20),C[i](1≤C[i]≤20), representing the weight the i^{th}ith kind of ship can carry, and the number of the i^{th}ithkind of ship is 2^{C[i]} - 12C[i]−1.$

For the next $\le S \le 10000)S(1≤S≤10000), representing the queried weight.$

Output

For each query, output one line containing a single integer which represents the number of schemes for arranging ships. Since the answer may be very large, output the answer modulo

样例输入复制

样例输出复制

0
1

题目来源

ACM-ICPC 2018 焦作赛区网络预赛

完全背包，顺便计数就好了

#include <bits/stdc++.h>
using namespace std;
const int MD=1e9+7;
int dp[10005],v[25],c[25];
void pack1(int v)
{
    for(int i=10000;i>=v;i--)
        dp[i]+=dp[i-v],dp[i]%=MD;
}
void pack2(int v)
{
    for(int i=v;i<=10000;i++)
        dp[i]+=dp[i-v],dp[i]%=MD;
}
void pack3(int v,int num)
{
    if(v*num>=10000)
    {
        pack2(v);
        return;
    }
    int k=1;
    while(k<num)
    {
        pack1(k*v);
        num-=k;
        k<<=1;
    }
    pack1(num*v);
}
int main()
{
    int T,n,q,s;
    scanf("%d",&T);
    while(T--)
    {
        memset(dp,0,sizeof dp);
        scanf("%d%d",&n,&q);
        for(int i=0;i<n;i++)
            scanf("%d%d",&v[i],&c[i]),c[i]=(1<<c[i])-1;
        dp[0]=1;
        for(int i=0;i<n;i++)
            pack3(v[i],c[i]);
        while(q--)
        {
            scanf("%d",&s);
            printf("%d\n",dp[s]);
        }
    }
    return 0;
}

L. Poor God Water

God Water likes to eat meat, fish and chocolate very much, but unfortunately, the doctor tells him that some sequence of eating will make them poisonous.

Every hour, God Water will eat one kind of food among meat, fish and chocolate. If there are

Now, you are the doctor. Can you find out how many different kinds of diet that can make God Water happy and safe during

Input

The fist line puts an integer $\le 1000T≤1000)$

Each of the next $\le N \le 10^{10}1≤N≤1010)$

Output

For each test case, output a single line containing the answer.

样例输入复制

样例输出复制

20
46
435170

题目来源

ACM-ICPC 2018 焦作赛区网络预赛

矩阵快速幂，比较难找到公式，所以暴力打表，直接dls模板过题

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define SZ(x) ((int)(x).size())
#define pb push_back
typedef vector<int> VI;
typedef long long ll;
const ll mod=1000000007;
ll powmod(ll a,ll b)
{
    ll res=1;
    a%=mod;
    assert(b>=0);
    for(; b; b>>=1)
    {
        if(b&1)res=res*a%mod;
        a=a*a%mod;
    }
    return res;
}

int t;
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)
{
    rep(i,0,k+k) _c[i]=0;
    rep(i,0,k) if (a[i]) rep(j,0,k) _c[i+j]=(_c[i+j]+a[i]*b[j])%mod;
    for (int i=k+k-1; i>=k; i--) if (_c[i])
            rep(j,0,SZ(Md)) _c[i-k+Md[j]]=(_c[i-k+Md[j]]-_c[i]*_md[Md[j]])%mod;
    rep(i,0,k) a[i]=_c[i];
}
int solve(ll n,VI a,VI b)   // a 系数 b 初值 b[n+1]=a[0]*b[n]+...
{
//        printf("%d\n",SZ(b));
    ll ans=0,pnt=0;
    int k=SZ(a);
    assert(SZ(a)==SZ(b));
    rep(i,0,k) _md[k-1-i]=-a[i];
    _md[k]=1;
    Md.clear();
    rep(i,0,k) if (_md[i]!=0) Md.push_back(i);
    rep(i,0,k) 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;
            rep(j,0,SZ(Md)) 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;
    rep(n,0,SZ(s))
    {
        ll d=0;
        rep(i,0,L+1) 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.pb(0);
            rep(i,0,SZ(B)) 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.pb(0);
            rep(i,0,SZ(B)) C[i+m]=(C[i+m]+c*B[i])%mod;
            ++m;
        }
    }
    return C;
}
int gao(VI a,ll n)
{
    VI c=BM(a);
    c.erase(c.begin());
    rep(i,0,SZ(c)) c[i]=(mod-c[i])%mod;
    return solve(n,c,VI(a.begin(),a.begin()+SZ(c)));
}
};

int main()
{
    for(scanf("%d",&t); t; t--)
    {
        ll n;
        scanf("%lld",&n);
        printf("%d\n",linear_seq::gao(VI{3,9,20,46,106,244,560,1286,2956,6794,15610,35866,82416},n-1));
    }
    return 0;
}