Karp的21个NPC问题和部分证明

问题

1. SAT问题

问题P为若干个子句的逻辑与,每个子句是若干变量的逻辑或(P是合取范式/CNF),问是否存在一组输入,使得P为真。

根据对偶性,这一问题可以表述为:命题S是若干子句的逻辑或,每个子句是若干变量的逻辑与(S是析取范式/DNF),问S是否为恒真命题。

2. 01整数规划

给定整数矩阵C和整数向量d,问是否存在01向量x使得[latex]Cx\geq d[/latex].

注:似乎Karp原论文中此处把“大于等于”误为“等于”:

https://cs.stackexchange.com/questions/19716/0-1-integer-programming-and-karps-reduction

SAT问题(合取范式P)规约到01整数规划:

我们构造矩阵A和向量b,对于P的子句i(Pi是若干个变量的逻辑或):

  • 如果Pi中有变量xj,则A[i,j]=1
  • 如果Pi中有变量not xj,则A[i,j]=-1
  • 否则,A[i,j]=0
  • bi = 1 – (Pi中出现的not xj形式的变量个数)

01向量x满足问题P当且仅当[latex]Ax\geq b[/latex]。

原理是:如果x不满足Pi,我们假设Pi是n个“xi”和m个“not xi”的并,可以想象,Pi中所有应当为True的变量在x中都为False,它们贡献的和为0,而所有应为False的变量在x中都为True,它们贡献的和为-m,所以总的和就是-m.其余所有情况下,Pi均满足,和都大于-m,也就是大于等于1-m.因此x满足Pi当且仅当[latex]A_i x\geq b_i[/latex]

3. 团问题

问图G中是否存在大小为k的团(完全子图)。

SAT问题(合取范式P)规约到团问题:

构造点集V为{<x, i> : 变量x出现在子句Pi中}

构造边集E为{ {<x, i>, <y,j>} : i,j不等且x不是not y }

假设SAT问题有解。我们按照点集V的构造法,让所有“变量x在Pi中为True”的<x,i>构成一个G中的点集R。显然,R中有每一个i(因为要求P的每一个子句为True),所以R中至少p个点。另一方面,R中不能有矛盾,即R中所有属于不同子句的点均按照规则“x不是not y”连边。我们取出R中属于不同子句的p个点,则它们构成一个大小为p的团。所以在团问题中检查是否存在大小为p的团,就可以解SAT。

另一方面,如果G中有大小为p的团,则这个团一定是在每个子句中包含一个变量,且变量之间无矛盾。我们在SAT中选取这些变量为True,即得到一组解。

4. 不相交集合

给定一组集合{Sn},问其中是否存在k个互不相交的集合。

团问题规约到不相交集合:

假设图G的点集是{1,2,…,n}.构造n个集合{S1,S2,…,Sn},其中Si = { {i,j} : {i,j}是G中的边 },其中{i,j}是无序集。注意到集合相交的唯一情况是形如Si和Sj中都包含{i,j},这意味着i和j相邻。因此,i,j不相邻当且仅当Si和Sj不相交,所以G中大小为k的团等价于{Sn}中k个不相交集合。

5. 点覆盖

问是否能用不超过k个点覆盖图G中的所有边。

团问题规约到点覆盖:

假设图G有n个顶点。G中存在点数不少于k的团当且仅当G的补图中存在点数不少于k的独立集(就是这个团),当且仅当G的补图中存在点数不超过n-k的点覆盖(就是那个独立集的补集,如果它未覆盖一条边,说明这条边的两端都在独立集中,矛盾)。所以G中存在点数不少于k的团等价于G的补图中存在点数不超过n-k的点覆盖。

6. 集合覆盖

给定有限个有限集合{Sn},问能否找出其中不超过k个集合,覆盖{Sn}之并中所有的元素。

点覆盖规约到集合覆盖:

集合i就是顶点i引出的边集。大小为k的点覆盖等价于这k个集合覆盖所有边集。

7. 反馈点集

给定有向图G,问是否存在大小不超过k的点集R,使得G中所有环都包含一个R中的点。

点覆盖规约到反馈点集:

把图G中的每条边(u,v)拆成一条去边<u,v>和一条回边<v,u>,这样形成的新图为H。

一方面,如果G中存在点数不超过k的点覆盖R,则R覆盖了H中的所有边,毋宁说H中的环。

另一方面,如果H中存在点数不超过k的反馈点集,可以看到,每个<u,v>和<v,u>构成一个环,所以这个反馈点集覆盖了G中的(u,v),这就是G中点数不超过k的点覆盖。

所以G中存在点数不超过k的点覆盖当且仅当H中存在点数不超过k的反馈点集。

8. 反馈边集

给定有向图G,问是否存在大小不超过k的边集S,使得G中所有环都包含一条S中的边。

点覆盖规约到反馈边集:

把G中每个点u拆成入点u0和出点u1,对于G中的边(u,v),作新图中两条边<u1,v0>和<v1,u0>,记新图为H。

一方面,对于G中的点覆盖R,我们在H中选取所有的<u0,u1>,其中u在R中。由于R覆盖了G中所有的边,那么H中的一个环必然包括R中的某个u,而我们选了<u0,u1>,就符合反馈边集的条件。

另一方面,G中每条边(u,v)在H中对应一个环(<u0,u1>,<u1,v0>,<v0,v1>,<v1,u0>),如果H中存在一个反馈边集,它应当至少包括这四条边之一。在G中选取那个对应的入点,显然它在G中覆盖了(u,v).

所以G中存在一个大小为k的点覆盖当且仅当H中存在一个大小为k的反馈边集。

9. 有向哈密顿回路

给定有向图G,问是否存在一条恰经过所有点一次的回路。

证明待补充

10. 无向哈密顿回路

给定无向图G,问是否存在一条恰经过所有点一次的回路。

有向哈密顿回路规约到无向哈密顿回路:

把G中的每个点u拆成三个点u0,u1,u2.连无向边(u0,u1),(u1,u2),对于G中的有向边<u,v>,连无向边(u2,v0).记新图为H。如果G中有有向哈密顿回路,那么按着走下来就是H中的无向哈密顿回路。如果H中有无向哈密顿回路,那么它每个点的类型一定是012012012……或者210210210……这就是说,它要么是正着走的G的有向哈密顿回路,要么是倒着走的G的有向哈密顿回路。

所以G中的有向哈密顿回路等价于H中的无向哈密顿回路。

11. 3-SAT问题

问是否存在一组输入满足所有的子句,每个子句是至多3个变量做逻辑或,每个变量形如x或者not x

SAT问题规约到3-SAT:

对于一个子句x1 or x2 or … or xm,我们新建一个变量y1,然后把它转化成以下的子句:

  • x1 or x2 or y1
  • x3 or x4 or … or xm or (not y1)
  • (not x3) or y1
  • (not x4) or y1
  • (not xm) or y1

可以证明它和原来的x1 or x2 or … or xm等价。

如此往复,直至把SAT问题变成若干个三元子句。

12. 染色数

给定一张图G,问是否可以做k染色。

3-SAT规约到染色问题:

假设3-SAT问题D的子句是D1,D2,…,Dr.不失一般性,假设D中的元素是u1,u2,…,um.

我们建一个图G,它的点集为:u1, u2, …, um, u1′, u2′, …, um’, D1, D2, …, Dr, v1, v2, …, vm. 其中ui’代表not ui,v1,…,vm是新加的点。

我们添加五类边:

  1. 每个ui和ui’连边。
  2. 如果i,j不等,连(vi,vj)
  3. 如果i,j不等,连(vi,xj)和(vi,xj’)
  4. 如果ui不在子句Df中,连(ui,Df)
  5. 如果ui’ 在Df中,连(ui’, Df)

证明待补充

 

13. 团覆盖

给定图G,问G中是否存在不超过k个团,覆盖所有的顶点。

染色问题规约到团覆盖:

把i号团的顶点染成颜色i(或者取颜色为i的顶点为i号团),那么G中存在不超过k个团的覆盖当且仅当G的补图可以k染色。

14. 恰好覆盖

给定一组集合{Sn},每个都是U={u1,…,ut}的子集,问是否存在若干个{Sn}中的集合,使得它们两两不交,而且覆盖U(全部并起来等于U).

证明待补充

15. 击中集

给定一组集合{Un},每个都是S={s1,…,sr}的子集,问是否存在一个S的子集W,使得[latex]|W\cap U_i|=1[/latex]对每个i成立。也就是W恰好“击中”每个Ui一次。

“恰好覆盖”规约到击中集:

我们把“恰好覆盖”问题中的元素u1,…,ut作为二分图的左边节点,集合S1,S2,…,Sm作为二分图的右边节点。ui在Sj中,就在它们之间连一条边。那么,恰好覆盖问题等于:选择右边的一些节点,把它们发出的所有边染红,使得左边每个点都恰巧连了一条红边。

另一方面,我们把击中集问题的元素s1,…,sr作为二分图的右边节点,集合U1,…,Un作为二分图的左边节点,如果si在Uj中,就在二者之间连边。那么击中集问题等于:选择右边的一些节点,把它们发出的所有边染红,使得左边每个点都恰巧连了一条红边。

所以击中集和恰好覆盖等价。

16. 斯坦纳树

给定图G和其中的一个顶点集R,问是否存在一个G的生成树T,使得T的边权值不超过k,且T包含R中所有顶点。要求所有边的权值都是整数。

“恰好覆盖”规约到斯坦纳树:

我们假设“恰好覆盖”问题的全体元素是{u1,u2,…,ut},有若干个集合{Si}。现在构造图G:每个ui都是G中的一个点,每个Si也是G中的一个点,除此之外再加上一个点n0.

n0和所有的Sj连权值为[latex]|S_j|[/latex]的边,如果ui在Sj中,则ui和Sj之间连权值为0的边。

我们把{ui}排成一竖列放在最右边,{Si}排成一竖列放在中间,n0放在最左边。那么图G中一棵生成树的样子是:n0向中间一列的若干个Si连边,这些Si再引出边,覆盖右边一列的所有ui。其中,u0向中间Si一列连的边的权值是Si中的元素数,Si一列向ui一列的边不消耗权值。因此这棵生成树的权值就是选取的集合的元素个数之和。

显然,“恰好覆盖”当且仅当能选出若干个元素个数之和恰好为t的集合,覆盖所有的ui,也就是说,存在一个权值为t的斯坦纳树。因此二者等价。

17. 三维匹配

给定一个集合[latex]U\subset T\times T\times T[/latex],其中T是一个n元集。问是否存在U的子集W,使得W中有n个元素,但是W中的任意两个元素的任意两个坐标都不相等。

证明待补充

18. 01背包

给定r件物品,重量为a1,a2,…,ar,问其中能否选出若干个,使得重量之和恰好为b.
“恰好覆盖”规约到01背包:

我们令元素ui的重量为2^i,每个集合的重量就是它包含的元素重量之和。那么恰好覆盖和选中的集合的重量在每个第i位上只有一个1等价。所以恰好覆盖等价于01背包。

19. 任务分配

有p个任务,i号任务的执行时间是Ti,期限是Di,完不成任务的惩罚是Pi。问是否存在一个执行任务的序列(也就是1,2,…,p的一个排列[latex]\pi[/latex]),使得未完成任务的总惩罚不超过k.

01背包规约到任务分配:

假设背包总容量为b。我们对于重量为ai的物品,构造任务i:它的耗时为ai,超时惩罚为ai,期限b。那么,背包能“恰好放满”就等价于能构造出一个“恰好用完时间”的任务,它的超时惩罚为(总耗时-b).于是01背包等价于任务分配。

20. 求和划分

给定一个整数集合C,问能否把C中的元素分成两部分,每一部分的和相等。

01背包规约到求和划分:
假设现有的元素为a1,a2,…,ar.

再构造两个元素:b+1, (a1+…+ar)+1-b.这r+2个元素的和为2(a1+…+ar+1).假设它能划分成和相等的两份,(a1+…+ar)+1-b所在的一份中,余下的元素肯定不包括b+1(否则就超了),所以一定是若干个ai加起来等于b。于是01背包等价于求和划分。

21. 最大割
给定图G,边权为整数 。求是否存在一个点集S,使得S向外的边的权值之和大于等于W.
求和划分规约到最大割:
假设有n个数{c1,c2,…,cn}.我们建立n个顶点的完全图G,其中i的点权为ci,边(i,j)的权值为ci*cj.
设c1+c2+…+cn=C.如果我们选取的点集S的点权之和为a,则这个割的割值就是a*(C-a)。这是一个关于a的二次函数,当a=C/2的时候取最大值。因此,{c1,c2,…,cn}可划分成和相等的两部分当且仅当有一个值等于[latex]C^2/4[/latex]的割。

ACM/ICPC乌鲁木齐2017解题报告

两位队友的博客:

http://hzwer.com/

http://kuribohg.github.io/

BEH三题是我写的,其余题目鸣谢二位大腿。

A:Banana

开始样例错了。
代码:
#include
#include
#include
#include
using namespace std;
int T,n,m,a[100][100],b[100][100],ans[100][100];
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        for(int i=1;i<=50;i++)
            for(int j=1;j<=50;j++)
                a[i][j]=0,b[i][j]=0,ans[i][j]=0;
        for(int i=1,x,y;i<=n;i++)
            scanf("%d%d",&x,&y),a[x][y]=1;
        for(int i=1,x,y;i<=m;i++)
            scanf("%d%d",&x,&y),b[x][y]=1;
        for(int i=1;i<=50;i++)
            for(int j=1;j<=50;j++)
                for(int k=1;k<=50;k++)
                    if(a[i][k]&&b[k][j]) ans[i][j]=1;
        for(int i=1;i<=50;i++)
            for(int j=1;j<=50;j++)
                if(ans[i][j]) printf("%d %d\n",i,j);
        puts("");
    }
    return 0;
}

B:Out-out control cars

题意:两个三角形匀速直线运动,问是否会撞上。

题解:只需单独计算每个三角形的某个顶点是否会和另一个三角形撞上,进一步地,只需要计算每个三角形的每个顶点是否与另一个三角形的每一条边撞上。方法就是计算一下相对速度(建立一个坐标系,相当于三角形静止,顶点匀速直线运动),然后问题转化为射线和线段相交,解二元一次方程组即可。

代码:

#include
#include
#include
#include
#include
using namespace std;
const double eps=1e-10;
bool solve_mat(double a00,double a01,double a10,double a11,double b0,double b1,double &x0,double &x1){
    double det=a00*a11-a01*a10;
    if(fabs(det)1) return false;
    return true;
}
bool work(void){
    Point A[3],Ad;
    Point B[3],Bd;
    for(int i=0;i<3;i++) scanf("%lf%lf",&A[i].x,&A[i].y);scanf("%lf%lf",&Ad.x,&Ad.y);
    for(int i=0;i<3;i++) scanf("%lf%lf",&B[i].x,&B[i].y);scanf("%lf%lf",&Bd.x,&Bd.y);
    for(int i=0;i<3;i++){
        for(int j=0;j<3;j++){
            Point p=A[i];
            Point d=Ad-Bd;
            Point a=B[j],b=B[(j+1)%3];
            if(hit(p,d,a,b)) return true;
            p=B[i];
            d=Bd-Ad;
            a=A[j],b=A[(j+1)%3];
            if(hit(p,d,a,b)) return true;
        }
    }
    return false;
}
int main(){
    int T;scanf("%d",&T);
    for(int tot=1;tot<=T;tot++){
        printf("Case #%d: ",tot);
        if(work()) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

C:Coconut

代码:
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define mod 1000000007
#define ll long long
using namespace std;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int T;
int n, b;
int c[1005], d[1005];
int main()
{
    T = read();
    while(T--)
    {
        n = read(); b = read();
        for(int i = 1; i <= n; i++)
            c[i] = read();
        for(int i = 1; i < n; i++)
            d[i] = read();
        int tot = 0;
        bool flag = 1;
        for(int i = 1; i < n; i++)
        {
            tot += c[i] - d[i] * b;
            if(tot < 0)
            {
                puts("No");
                flag = 0;
                break;
            }
        }
        if(flag)puts("Yes");
    }
    return 0;
}

D:Hack Portals

题意:数轴上有一堆点。你可以每秒走长度1,也可以静止。每个点有一个出现时间,你必须按任意顺序访问所有的点(在其出现之后),你一开始在0,最后回到坐标K,问最少需要多少秒。坐标均为整数,点数和坐标不超过1000,出现时间不超过32768.
题解:枚举一开始在0静止的时长。然后一定是:先走到没被访问的最右点,再走到没被访问的最左点……直到完成。该过程可以O(n)模拟,见代码。
代码:
#include
#include
#include
#include
#include
using namespace std;
const int MAXN=1010;
int T,n,L,K,gol[MAXN],x[MAXN],y[MAXN];
int q[MAXN],l,r;
bool used[MAXN];
bool cmp(int i,int j)
{
    return x[i]r) break;
                if(nowy+nowx-x[q[l]]=l&&x[q[r]]+y[q[r]]<=nowx+nowy) r--;
                if(l>r) break;
            }
            if(ok) ans=min(ans,nowy+abs(nowx-K));
        }
        printf("%d\n",ans);
    }
    return 0;
}

E:Half-consecutive Numbers

题意:定义序列t[i]=i*(i+1)/2,每次给定一个n,问t序列第n项以后的第一个完全平方数是什么,n<=10^16。
题解:i和i+1/2互质,故要么i=n^2, i+1=2m^2,或者i=2m^2, i+1=n^2。枚举n,n不超过10^8,  打表。
代码:

#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long LL;
bool test(LL x){
    LL r=sqrt(x+0.5);
    return r*r==x;
}
bool check(LL n,LL k){
    LL m=n*n+k;
    return test(m/2);
}
LL lis[100]={0LL,1LL,8LL,49LL,288LL,1681LL,9800LL,57121LL,332928LL,1940449LL,11309768LL,65918161LL,384199200LL,2239277041LL,13051463048LL,76069501249LL,443365544448LL,2584123765441LL,15061377048200LL,87784138523761LL,511643454094368LL,2982076586042449LL,17380816062160328LL,};
int main(){
    /*freopen("ilis.out","w",stdout);
    LL mx=1e16;
    cout<=mx) break;
        }
        if(check(i,1)){
            cout<=mx) break;
        }
    }*/
    int T;scanf("%d",&T);
    for(int tot=1;tot<=T;tot++){
        LL n;scanf("%lld",&n);
        int i;for(i=0;lis[i]

F:Islands

题解:缩点之后,所有块的入度、出度取max。
代码:
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define eps 1e-12
#define mp(a, b) make_pair(a, b)
#define ll long long
#define inf 9000000000000000000LL
#define mod 1000000007
#define pa pair
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int T, n, m;
int ind, scc, top;
int in[10005], out[10005];
int low[10005], dfn[10005], q[10005], bl[10005];
bool inq[10005];
vectore[10005];
void tarjan(int x)
{
	low[x] = dfn[x] = ++ind;
    q[++top]=x; inq[x]=1;        
	for(int i = 0; i < e[x].size(); i++)
		if(!dfn[e[x][i]])
		{
			tarjan(e[x][i]);
			low[x] = min(low[x], low[e[x][i]]);
		}
		else if(inq[e[x][i]])
            low[x] = min(low[x], dfn[e[x][i]]);
    if(low[x] == dfn[x])
    {
        int now = 0; scc++;
        while(x != now)
        {
            now = q[top]; top--;
            bl[now] = scc;
            inq[now] = 0;
        }
    }
}
int main()
{
    T = read();
    while(T--)
    {
        scc = ind = 0;
        memset(dfn, 0, sizeof(dfn));
        memset(low, 0, sizeof(low));
        memset(out, 0, sizeof(out));
        memset(in, 0, sizeof(in));
        memset(bl, 0, sizeof(bl));
        for(int i = 1; i <= 10000; i++)
            e[i].clear();        
        n = read(); m = read();
        for(int i = 1; i <= m; i++)
        {
            int u = read(), v =read();
            e[u].push_back(v);
        }
        for(int i = 1; i <= n; i++)
            if(!dfn[i])tarjan(i);
        for(int i = 1; i <= n; i++)
            for(int j = 0; j < e[i].size(); j++)
                if(bl[i] != bl[e[i][j]])
                    in[bl[e[i][j]]]++, out[bl[i]]++;
        int t1 = 0, t2 = 0;
        for(int i = 1; i <= scc; i++)
        {
            if(!in[i])t1++;
            if(!out[i])t2++;
        }
        if(scc == 1)puts("0");
        else printf("%d\n", max(t1, t2));
    }
    return 0;
}

G:Query on String

题意:给字符串S,T,T的长度不超过10.每次询问S[l..r]中有多少个T,或者改S的一位。

题解:先预处理一下,就变成了区间和查询。改S的一位至多影响10个值,用树状数组即可。
代码:
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define eps 1e-12
#define mp(a, b) make_pair(a, b)
#define ll long long
#define inf 9000000000000000000LL
#define mod 1000000007
#define pa pair
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int q, n, m, Tes;
int t[100005];
void add(int x, int val)
{
    x++;
    if(val == 0)return;
    for(int i = x; i <= n; i += i & -i)
        t[i] += val;
}
int query(int x)
{
    x++;
    int ans = 0;
    for(int i = x; i; i -= i & -i)
        ans += t[i];
    return ans;
}
string S, T;
bool check(int x)
{
    if(x + m - 1 > n - 1)return 0;
    for(int i = 0; i < m; i++)
        if(S[x + i] != T[i])return 0;
    return 1;
}
int main()
{
    Tes = read();
    while(Tes--)
    {
        memset(t, 0, sizeof(t));
        q = read();
        cin >> S; n = S.length();
        cin >> T; m = T.length();
        for(int i = 0; i < n; i++)
            add(i, check(i));
        char ch[2];
        while(q--)
        {
            scanf("%s", ch);
            if(ch[0] == 'Q')
            {
                int l = read() - 1, r = read() - 1;
                r = r - m + 1;
                if(l > r)
                {
                    puts("0");
                }
                else
                {
                    int ans = query(r) - query(l - 1);
                    printf("%d\n", ans);
                }
            }
            else
            {
                int pos = read() - 1;
                scanf("%s", ch);
                for(int i = max(0, pos - m + 1); i <= pos; i++)
                    add(i, -check(i));
                S[pos] = ch[0];
                for(int i = max(0, pos - m + 1); i <= pos; i++)
                    add(i, check(i));
            }
        }
        puts("");
    }
    return 0;
}

H:Skiing

题意:DAG最长路。DAG是题目保证的……
题解:随便写。我抄了个SPFA的板子。
代码:

#include
#include
#include
#include
#include
#include
using namespace std;
const int INF=0x7fffffff/2;
const int SIZEN=10010;
int N,M;
vector > c[SIZEN];
void SPFA(vector > c[SIZEN],int N,int S,int f[SIZEN]){//图中顶点0~N-1,邻接表为c,以S出发,结果存于f
	queue Q;
	bool inq[SIZEN]={0};
	for(int i=0;i<=N+1;i++) f[i]=-INF;
	f[S]=0,inq[S]=true,Q.push(S);
	while(!Q.empty()){
		int x=Q.front();Q.pop();inq[x]=false;
		for(int i=0;if[u]){
				f[u]=f[x]+c[x][i].second;
				if(!inq[u]){
					inq[u]=true;
					Q.push(u);
				}
			}
		}
	}
}
int f[SIZEN];
void work(void){
    SPFA(c,N,0,f);
    printf("%d\n",f[N+1]);
}
void read(void){
    scanf("%d%d",&N,&M);
    int a,b,w;
    for(int i=0;i<=N+1;i++) c[i].clear();
    for(int i=1;i<=M;i++){
        scanf("%d%d%d",&a,&b,&w);
        c[a].push_back(make_pair(b,w));
    }
    for(int i=1;i<=N;i++){
        c[0].push_back(make_pair(i,0));
        c[i].push_back(make_pair(N+1,0));
    }
}
int main(){
    int T;scanf("%d",&T);
    while(T--){
        read();
        work();
    }
    return 0;
}

I:Colored Graph

题意:给一张N个点完全图,求把每条边黑白染色,最少生成多少个纯色三角形。

代码:

#include
#include
#include
#include
using namespace std;
int T,n;
int d[510][510],a[510];
int gcd(int a,int b)
{
    if(b==0) return a;
    return gcd(b,a%b);
}
void print()
{
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            printf("%d",d[i][j]);
            if(j!=n) putchar(' ');
            else printf("\n");
        }
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        if(n%2==0)
        {
            for(int i=1;i<=n/2;i++)
                for(int j=1;j<=n/2;j++)
                    if(i!=j) d[i][j]=2;
            for(int i=n/2+1;i<=n;i++)
                for(int j=n/2+1;j<=n;j++)
                    if(i!=j) d[i][j]=2;
            for(int i=1;i<=n;i++)
                for(int j=1;j<=n;j++)
                    if(i!=j&&d[i][j]==0) d[i][j]=1;
        }
        else if(n%4==1)
        {
            int total=0;
            for(int i=1;i

J:Our Journey of Dalian Ends

题意:一张无向图,求从1走到N,必须经过K,每个节点至多经过一次的最短路。

题解:费用流。

代码:

#include
#include
#include
#include
#include
#include
#define next next2
using namespace std;
const int INF=1000000000;
int TT,m,tot;
char str1[100010],str2[100010];
map M;
int getid(char s[])
{
    string str=string(s);
    if(M.find(str)==M.end())
    {
        M[str]=++tot;
        return tot;
    }
    else return M[str];
}
struct Edge
{
    int x,y,w;
    Edge(){}
    Edge(int x,int y,int w):x(x),y(y),w(w){}
}E[100010];
const int MAXN=100010;
const int MAXM=200010;
int S,T;
int head[MAXN],fr[MAXM],to[MAXM],next[MAXM],from[MAXM],cnt=1;
int w[MAXM],c[MAXM],cost,flow,dis[MAXN];
int q[MAXN],l,r;
bool used[MAXN];
inline void adde(int f,int t,int ww,int cc)
{
    cnt++,fr[cnt]=f,to[cnt]=t,w[cnt]=ww,c[cnt]=cc,next[cnt]=head[f],head[f]=cnt;
    cnt++,fr[cnt]=t,to[cnt]=f,w[cnt]=0LL,c[cnt]=-cc,next[cnt]=head[t],head[t]=cnt;
}
bool SPFA()
{
	for(int i=1;i<=T;i++) dis[i]=INF,from[i]=0;
	dis[S]=0,used[S]=true,q[l=0]=S,r=1;
	while(l!=r)
	{
		int x=q[l++];if(l==T) l=0;
		used[x]=false;
		for(int i=head[x];i;i=next[i])
			if(w[i]>0&&dis[to[i]]>dis[x]+c[i])
			{
				dis[to[i]]=dis[x]+c[i];
				from[to[i]]=i;
				if(!used[to[i]])
				{
					q[r++]=to[i];
					if(r==T) r=0;
					used[to[i]]=true;
				}
			}
	}
	return dis[T]!=INF;
}
void DFS()
{
	int x=INF;
	for(int i=from[T];i;i=from[fr[i]])
		x=min(x,w[i]);
	flow+=x;
	for(int i=from[T];i;i=from[fr[i]])
		w[i]-=x,w[i^1]+=x,cost+=c[i]*x;
}
void MCMF()
{
	while(SPFA())
		DFS();
}
int main()
{
    scanf("%d",&TT);
    while(TT--)
    {
        scanf("%d",&m);
        for(int i=1;i<=m;i++)
        {
            int www;
            scanf("%s%s%d",str1,str2,&www);
            int x=getid(str1),y=getid(str2);
            E[i]=Edge(x,y,www);
        }
        for(int i=1;i<=tot;i++) adde(i,tot+i,1,0);
        for(int i=1;i<=m;i++) adde(tot+E[i].x,E[i].y,INF,E[i].w),adde(tot+E[i].y,E[i].x,INF,E[i].w);
        int dalian=getid("Dalian");
        int xian=getid("Xian");
        int shanghai=getid("Shanghai");
        S=2*tot+1,T=2*tot+2;
        adde(S,shanghai,2,0);
        adde(shanghai,tot+shanghai,1,0);
        adde(tot+dalian,T,1,0);
        adde(tot+xian,T,1,0);
        MCMF();
        if(flow!=2) puts("-1");
        else printf("%d\n",cost);
        M.clear();
        for(int i=1;i<=T;i++) head[i]=0;
        cnt=1;
        flow=0,cost=0;
        tot=0;
    }
    return 0;
}

[CCPC2015][HDU5548]Mahjong解题报告

题目



给定点数为1~K的麻将牌各4张(这4张完全相同),问有多少种方案,从中选出一个M张牌组成的集合,能够和牌。“和牌”指:其中有两张完全相同的将牌,其他牌可以被三三分组,每组要么是“n-1 n n+1”型,要么是“n n n”型。注意:集合相同而和法不同仅算一次。

题解

我们考虑这样一个命题:如果给定一个集合,能否和牌。这是一个很简单的DP:大致是:f[i][n2][n1][p]={0,1},其中i是到了点数为i的,n2是以i-2开始的连牌组数,n1以i-1的连牌组数,p是是否有将牌。对于点数为i的牌,枚举是否从中选取将牌,尔后贪心转移即可。

我们可以发现:这样的(n2,n1,p)的状态只有3*3*2=18个(n2,n1<=2,p<=1)。换言之:用一个长度为18的01数即可表示出某个状态的所有DP情况。我们设这个状态是s,那么对于原先的题目,如果开一个DP数组:F[i][s],表示到了点数为i的牌,到达DP情况为s的方案数。不妨把这个s想象成某种“虚拟机”,F[i][s]就是到达这个“虚拟机”的方案数。在最后,如果“虚拟机”中代表结束的状态为1,就代表能够和牌。

但是还有个问题:2^18显然太大,我们不能都存下来。怎么办呢?实际上我们可以发现,合法的“虚拟机”个数很少(仅有68)个,先BFS把它们都找出来,哈希一下编个号即可。

这个做法是队友@KuribohG告诉我的,当时惊为天人,因为这个算法背后的思想十分深刻。它在一个DP的基础上进行了更高一层的抽象,实质上是在下标里储存了全部的DP信息,即一个“虚拟机”。

代码

#include
#include
#include
#include
#include
#include
using namespace std;
const int SIZEN=210;
const int MOD=1000000000+7;
int get(int s,int k){
    return (s>>k)&1;
}
int change(int s,int k,int t){
    s&=(~(1<=3) n0-=3;
    return n0;
}
int state_goto(int s0,int n0,int jiang){
    int n2,n1,p;
    decode(s0,n2,n1,p);
    if(p&&jiang) return -1;
    int t0=trans(n2,n1,n0,jiang);
    if(t0==-1) return -1;
    return encode(n1,t0,p|jiang);
}
int VM_goto(int vm0,int n0){
    int vm1=0;
    for(int s0=0;s0<3*3*2;s0++){
        if(!get(vm0,s0)) continue;
        for(int p=0;p<=1;p++){
            int s1=state_goto(s0,n0,p);
            if(s1!=-1){
                vm1=change(vm1,s1,1);
            }
        }
    }
    return vm1;
}
map Dict;
int cnt=0;
int table[SIZEN][SIZEN]={0};
bool success[SIZEN]={0};
queue Q;
bool add_state(int vm){
    if(!Dict.count(vm)){
        Dict[vm]=cnt;
        Q.push(vm);
        if(get(vm,encode(0,0,1))) success[cnt]=true;
        cnt++;
        return true;
    }
    return false;
}
void BFS_states(void){
    int vm0=0;
    vm0=change(vm0,encode(0,0,0),1);
    add_state(vm0);
    while(!Q.empty()){
        vm0=Q.front();Q.pop();
        for(int i=0;i<=4;i++){
            int vm1=VM_goto(vm0,i);
            add_state(vm1);
            table[Dict[vm0]][i]=Dict[vm1];
        }
    }
}
int N,M;
int F[SIZEN][SIZEN][SIZEN];
void add(int &a,int b){
    a+=b;
    a%=MOD;
}
void work(void){
    static int kase=0;
    int vm0=0;
    vm0=change(vm0,encode(0,0,0),1);
    memset(F,0,sizeof(F));
    F[0][0][Dict[vm0]]=1;
    for(int i=1;i<=N+3;i++){
        int h=i>N?0:4;
        for(int j=0;j<=M;j++){
            for(int id=0;id

[Shanghai2015]Discover Water Tank解题报告

题目:

http://acm.hdu.edu.cn/diy/diy_previewproblem.php?cid=30741&pid=1004

http://cogs.pro/cogs/problem/problem.php?pid=1407

A lot of frogs are living in a water tank, but none of them know exactly how much water are there.

The water tank has an infinite height, but with a narrow bottom. The length of the tank is N,
and the width is only 1.

Now N1 boards
has divided the tank into N parts,
each with an 1×1 bottom.
Boards may have different heights. Water cannot flow through the boards, but can run freely if the water level is higher, following the basic physical rules.

The Frog King wants to know more details of the tank, so he sent someone to choose M positions
and find whether there’s water at that position.

For example, each time he’ll choose(x,y),
checking the xth part
of the tank(1xN),
counting from left to right, and find whether there’s water at height (y+0.5).

Now the King gets M results,
but he finds some of them might be wrong. The King wants to find out the maximum possible number of the correct results.


题解:

基础想法是很简单的:假设先考虑所有N个部分。我们找出其中最高的那个隔板,分两种情况讨论:①如果这个隔板没有被淹没,那就可以分别处理左右两个部分。②如果这个隔板被淹没,我们就取出那些比这个隔板高的观测点,顺序扫描一遍,找出最优解。综合①②就能得到答案了。

但是细节比较……麻烦。怎么“找出最高的隔板”呢?我写了个ST算法求RMQ。怎么“取出比它高的观测点”呢?我在分治时,对每个区间储存两个set(分别表示观测值为0和1的结果),递归上来时按秩合并,删掉那些比隔板低的观测点,并固定下来它们对答案的贡献。总之写的非常不优美。

更好的解法能在网上找到,似乎是类似建一棵树然后DP。

模拟训练的时候出了两个错误:第一个是打错了一个变量名,第二个是没有把删去点的贡献传给上一层。始终没debug出来。

代码:

#include
#include
#include
#include
#include
#include
using namespace std;
typedef multiset::iterator ITER;
const int SIZEN=100010;
const int INF=0x7fffffff/2;
void printset(multiset s){
	for(ITER key=s.begin();key!=s.end();key++){cout<<(*key)<<" ";}cout<>=1;}
	if(ans<0) ans=0;
	return ans;
}
int ST[20][SIZEN];
void build_st(int a[],int n){
	int m=log2(n);
	for(int i=0;ia[q]?p:q);
			}
		}
	}
}
int RMQ(int a[],int l,int r){
	int m=log2(r-l+1);
	int p=ST[m][l],q=ST[m][r-(1<a[q]?p:q;
}
int N;
int H[SIZEN];
multiset SL[SIZEN],SH[SIZEN];
int calc(multiset &sl,multiset &sh,int high){//l:0,h:1
	ITER key1=sl.begin(),key2=sh.begin();
	int now=sl.size(),ans=now;
	for(;key1!=sl.end()&&(*key1)<=high;key1++){
		while(key2!=sh.end()&&(*key1)>=(*key2)) now++,key2++;
		ans=max(ans,now);
		now--;
	}
	key1=sl.begin(),key2=sh.begin();
	now=sl.size();
	for(;key2!=sh.end()&&(*key2)<=high;key2++){
		now++;
		while(key1!=sl.end()&&(*key2)>(*key1)) now--,key1++;
		ans=max(ans,now);
	}
	return ans;
}
int merge(int a,int b,int lim,int &cnt){
	if(SL[a].size()+SH[a].size()>SL[b].size()+SH[b].size()) swap(a,b);
	for(ITER key=SL[a].begin();key!=SL[a].end();key++){
		if((*key)>lim) SL[b].insert(*key);
	}
	for(ITER key=SH[a].begin();key!=SH[a].end();key++){
		if((*key)>lim) SH[b].insert(*key);
		else cnt++;
	}
	for(ITER key=SL[b].begin();key!=SL[b].end();){
		ITER key1=key;key1++;
		if((*key)<=lim){
			SL[b].erase(key);
			key=key1;
		}
		else break;
	}
	for(ITER key=SH[b].begin();key!=SH[b].end();){
		if((*key)<=lim){
			ITER key1=key;key1++;
			SH[b].erase(key);
			key=key1;
			cnt++;
		}
		else break;
	}
	return b;
}
int DQ(int a,int b,int mx,int &s,int &cnt){
	if(a==b){
		cnt=0;
		s=a;
		return calc(SL[a],SH[a],mx);
	}
	int p=RMQ(H,a,b-1);
	int ans=0;
	int s1,s2,cnt1,cnt2;
	ans=DQ(a,p,H[p],s1,cnt1)+DQ(p+1,b,H[p],s2,cnt2);
	cnt=cnt1+cnt2;
	s=merge(s1,s2,H[p],cnt);
	ans=max(ans,calc(SL[s],SH[s],mx)+cnt);
	return ans;
}
void read(void){
	int Q;
	scanf("%d%d",&N,&Q);
	for(int i=1;i

CF 461D Appleman and Complicated Task解题报告

题目


给你一个n*n网格,每一格要么是0要么是1要么为空,要求你用0或1填满所有空格,使得每个格子周围的0有偶数个。

题解

首先我们观察到这样一个事实:当第一行确定后,整个网格的填法就确定了。我们以N=8为例,把这种确定方法列出来:其中,“0246”这样的数的含义为,假设第一行为a[0..7],它表示该格的值是a[0] xor a[2] xor a[4] xor a[6].



可以发现,这个形式是很规整的。都是“246”或者“1357”这种,连续的奇/偶数。

因此,我们的问题就变成了:问有多少种a的取值,满足K组形如a[1] xor a[3] xor a[5] xor a[7] = 1(或者0)这样的限制。

不妨设a的“奇/偶前缀和”为s,就是说s[6] = a[0] xor a[2] xor a[4],s[5] = a[0] xor a[3],等等。那么a[1] xor a[3] xor a[5] xor a[7] = 1这个限制就变成了s[1] xor x[9] = 1.可以发现,所有对a的“段”限制都变成了s中某两个数的限制:它们要么相等要么相反。

这就变成了一道有成熟算法的题目:让每个s[i]都对应两个元素i和i’,二者的值相反。对于s[a] xor s[b] = 0这种限制,就把a和b,a’和b’放在同一个并查集中;对于s[a] xor s[b] = 1这种限制,就把a和b’,a’和b放在同一个并查集中。如果在某个时刻,某个a和a’被并在了一起,则无解。

设最后剩下的等价类数量是cnt,可以发现,其中有4个的值是确定的:s[0]和s[1],以及它们的反。因此,答案就是2^((cnt-4)/2).

代码

#include
#include
#include
#include
using namespace std;
const int SIZEN=100010;
const int MOD=1000000007;
int pow2(int n){
	int ans=1;
	for(int i=1;i<=n;i++){
		ans=(ans<<1)%MOD;
	}
	return ans;
}
class EQ2{//solver
public:
	int ufs[SIZEN*2];
	void clear(void){
		memset(ufs,-1,sizeof(ufs));
	}
	EQ2(){clear();}
	int grand(int x){
		return ufs[x]==-1?x:ufs[x]=grand(ufs[x]);
	}
	bool merge(int a,int b){//元素a和元素b 
		int ga=grand(a),gb=grand(b);
		if(grand(a^1)==gb) return false;
		if(grand(b^1)==ga) return false;
		if(ga!=gb) ufs[ga]=gb;
		return true;
	}
	bool test(int a,int b,int t){//变量a和变量b的xor是t 
		if(t==0){
			return merge(2*a,2*b)&&merge(2*a+1,2*b+1);
		}
		else if(t==1){
			return merge(2*a,2*b+1)&&merge(2*a+1,2*b);
		}
	}
	int count(int N){//0~N
		N=2*N+1;
		int ans=0;
		for(int i=0;i<=N;i++){
			if(grand(i)==i) ans++;
		}
		return ans;
	}
}S;
void work(void){
	int N,K,a,b,p;
	char ch[10];
	scanf("%d%d",&N,&K);
	for(int i=1;i<=K;i++){
		scanf("%d%d",&a,&b);
		a--,b--;
		scanf("%s",ch);
		p=(ch[0]=='x'?0:1);
		int l=abs(a-b);
		int r=min(a+b,2*(N-1)-(a+b));
		if(!S.test(l,r+2,p)){
			printf("0\n");
			return;
		}
	}
	int cnt=S.count(N+1);
	printf("%d\n",pow2((cnt-4)/2));
}
int main(){
	//freopen("input.in","r",stdin);
	work();
	return 0;
}

CF 449E Jzzhu and Squares解题报告

题目大意


给定一个N*M的网格。对一个顶点为格点的正方形R(不一定与格线平行),计算出其中有多少个单位格被R完全包含(记作F(R))。求所有正方形的F(R)之和。

题解

首先画一个“勾股图”:



粉色是我们的正方形(不和格线平行),设其外接正方形的边长为L,四周直角三角形的短边为a,则长边为L-a。设其中完整包含了F(L,a)个单位格。

可以发现,其中完全包含的单位正方形分成两部分:第一部分是中间小正方形里的个,第二部分是周边直角三角形里包含的。

我们这么计算第二部分:一红一白两个直角三角形拼成的矩形内有(L-a)*a个单位格,而对角线穿过了L-gcd(L,a)格,再除以2,就得到了一个三角形内的单位格数。将其乘以4,总共加起来得到:



没错,“斜线下方的格点数”没有简单公式,但“单位格数”有!

可以发现,F(L,a)即使当a>L-a时也成立,所以我们可以直接用a枚举到底,整道题目的答案就是:



我们把展开:



这分成两部分:第一部分是一个关于L的多项式,第二部分是gcd(L,a)的前缀和。

可以想象,也是如此分成两部分:第一部分是一个关于L的多项式(确切地说,是5次多项式),第二部分也是一个关于L的“多项式”,但其“未知数项”不是这种形式,而是这种形式。

至于怎么得到这个多项式呢,如果你数学好可以手推……作为一名数学技能荒废一年的咸鱼选手,我就直接用vector当低配版多项式类,让电脑推了……

不要忘了,我们要求的是上面那个玩意的前缀和。因此,只需要求出来这两种形式关于L的“前缀和”,然后乘以多项式中相应的系数,就可以完成任务。

前者很简单:L不超过10^6,暴力递推即可。后者也差不多,只需要先递推出来phi函数,然后枚举gcd(a,L)的值,就可以把Σgcd的表都打出来,详见代码。

代码

#include
#include
#include
#include
#include
using namespace std;
typedef long long LL;
typedef vector Poly;
const LL MOD=1000000007;
const int H=6;
LL gcd(LL a,LL b){
	return !b?a:gcd(b,a%b);
}
LL lcm(LL a,LL b){
	return a*b/gcd(a,b);
}
LL quickpow(LL a,LL n){
	LL ans=1;
	while(n){
		if(n&1) ans=(ans*a)%MOD;
		a=(a*a)%MOD;
		n>>=1;
	}
	return ans;
}
LL inverse(LL a){
	return quickpow(a,MOD-2);
}
void print(Poly a){
	for(int i=0;iM) swap(N,M);
	//N是较小者
	A[0]=M+1,A[1]=-1;Poly D(A,A+2);
	A[0]=N+1,A[1]=-1;D=D*Poly(A,A+2);
	Poly F=give_Fsum_L();
	Poly F1=D*F;
	LL ans=0;
	ans+=calc_presum_with(F1,P[N]);
	ans%=MOD;
	A[0]=2;
	Poly F2=D*Poly(A,A+1);
	ans+=calc_presum_with(F2,PG[N]);
	ans%=MOD;
	ans=(ans+MOD)%MOD;
	printf("%I64d\n",ans);
}
void prepare(void){
	for(int i=1;i

ACM/ICPC2016沈阳网络赛(不完全)解题报告

比赛地址:


1003.hannnnah_j’s Biological Test

题目大意:

圆周上有N个不同的椅子,要让M个相同的人坐在上面,使得两人之间至少隔K把空椅子,求方案数(模1e9+7)。

0

题解:

考虑每两个人之间隔了几把椅子。可以发现,一共有M个数,和为N-M,且每个数都>=K.将每个数都减去K-1,即得到:M个正数之和为N-K*M,方案数为C(N-K*M-1,M-1).需要乘以圆排列的N,同时每个方案被算了M次,再除以M。
答案为:C(N-K*M-1,M-1)*N/M。需要用预处理阶乘的方法计算组合数。注意特判M=1的情况。

代码:

#include
#include
#include
#include
using namespace std;
typedef long long LL;
const LL MOD=1000000000+7;
LL quickpow(LL a,LL n){
    LL ans=1;
    while(n){
        if(n&1) ans=(ans*a)%MOD;
        a=(a*a)%MOD;
        n>>=1;
    }
    return ans;
}
LL inv(LL a){
    return quickpow(a,MOD-2);
}
LL fact[2000010];
void prepare(void){
    fact[0]=1;
    for(LL i=1;i<=2000000;i++){
        fact[i]=fact[i-1]*i%MOD;
    }
}
LL C(LL n,LL m){
    if(n<0||n-m<0||m<0) return 0;
    LL ret=fact[n];
    ret=ret*inv(fact[n-m])%MOD;
    ret=ret*inv(fact[m])%MOD;
    return ret;
}
LL calcadd(LL n,LL k){//k non-neg nums add up to N
    if(n<0) return 0;
    return C(n+k-1,k-1);
}
LL calc(LL N,LL M,LL K){
    if(M==1) return N;
    LL ret=C(N-M*K-1,M-1);
    ret=ret*N%MOD;
    ret=ret*inv(M)%MOD;
    return ret;
}
void work(void){
    LL N,M,K;
    cin>>N>>M>>K;
    cout<

1007.odd-even number

题目大意:

对于一个十进制整数,如果它的数位表示中,连续的奇数总有偶数个,连续的偶数总有奇数个,就称它是“好”的。给定1 <= L,R <= 9e18,求[L,R]内“好数”的数量。

题解:

首先容斥一下,只需要求“<=x的好数”这样一个问题。


数位DP,枚举“从哪一位开始和x不同”。例如,x为47397456,我们就需要求一些例如“有多少个形如47395???的好数”这样的问题。特别注意位数比x少的那些数,即类似于“有多少个形如????????的好数”这种问题。对此,我们可以先DP出来一个数组F:F[i][j][n],其中i=0/1/2代表开头一段是偶数/奇数/未开始,j=0/1代表开头一段有偶数/奇数个(如果i=2就规定j=0),n代表后面有n个未定位,F[i][j][n]就是这种情况下的“好数”个数。例如,形如“47395???”的好数就有F[1][0][3]个,形如“????”的好数就有F[2][0][4]个。

代码:

#include
#include
#include
#include
#include
using namespace std;
typedef long long LL;
LL F[3][2][30]={0};
void DP(void){
    F[0][1][0]=F[1][0][0]=1;
    for(int i=1;i<=20;i++){
        F[0][0][i]=F[0][1][i-1]*5;
        F[0][1][i]=F[0][0][i-1]*5+F[1][1][i-1]*5;
        F[1][0][i]=F[1][1][i-1]*5+F[0][1][i-1]*5;
        F[1][1][i]=F[1][0][i-1]*5;
        F[2][0][i]=F[0][1][i-1]*4+F[1][1][i-1]*5+F[2][0][i-1];
    }
}
bool add_sta(int &r,int &l,int x){
    if(r==2){
        if(x!=0){
            r=(x&1);
            l=1;
        }
        return true;
    }
    if(!(x&1)){
        if(r==1&&l==1) return false;
        if(r==0) l^=1;
        else{
            r=0;
            l=1;
        }
        return true;
    }
    else if(x&1){
        if(r==0&&l==0) return false;
        if(r==1) l^=1;
        else{
            r=1;
            l=1;
        }
        return true;
    }
}
LL calc(const vector &A){
    LL ret=0;
    int n=A.size();
    int r=2,l=0;
    for(int i=0;i getdec(LL x){
    vector ret;
    while(x){
        ret.push_back(x%10);
        x/=10;
    }
    reverse(ret.begin(),ret.end());
    return ret;
}
LL calc(LL x){
    return calc(getdec(x));
}
LL calc(LL L,LL R){
    return calc(R)-calc(L-1);
}
int main(){
    DP();
    int T,kase=0;scanf("%d",&T);
    while(T--){
        LL l,r;cin>>l>>r;
        printf("Case #%d: %lld\n",++kase,calc(l,r));
    }
    return 0;
}

1008.oasis in desert

题目大意:

给定一张N<=500的边带权无向图和一个整数K。定义:

1. “最大危险集”:是顶点集的一个子集,该集合中任意两顶点的最短路大于K。最大危险集是所有这种集合中最大的。

2. “最小安全集”:是顶点集的一个子集,如果全部顶点中,任意二者的最短路小于等于K,该集合中必须至少包含其中的一个。最小安全集是所有这种集合中最小的。

要求找出一个集合,它既是最大危险集,又是最小安全集。若有多组解,输出字典序最小者。无解输出“Impossible”。

题解:

2016/11/23更新:

感谢@cmershen 的评论,他指出了这个做法的错误:

“楼主你好,你这个1008题的题解是错的,而且代码交上去也是wa。
我认为错在这里:“注意,这张图有可能不连通,但这并不影响结论,因为每一个连通块都应符合上述条件。”

如果两个子图不连通,其中每个子图都有符合题意的集合,那么按LZ代码的思路,答案应为两个子图的并集。如果我从这两个子图里分别拿出一个点,他俩根本就是不可达的,题中的“minimum distance longer than K”就没有意义。


还有,二分图就算是一边有N/2个点,也不一定存在完美匹配的。。。。。。我在LZ的代码上补充了这两种情况,提交到hdu 5899上,确实AC了。

详见评论区。就是说,下面的题解和代码都少考虑了这些情况,请大家不要被误导(我也懒得改代码了(逃)。

首先建一张新图,其中两点之间连一条单位边当且仅当它们在原图中的最短路<=K。

我们不妨假设一个点在集合中,看看会发生什么:

1. 它本身在集合中。
2. 和它相邻的点不在集合中。
3. 和2中点相邻的点在集合中(这是最小安全集的规定)。
4. 和3中点相邻的点不在集合中。
5. 和4中点相邻的点在集合中。
……

可以发现,这实质上是对图进行二分染色。换言之,这张图必须是二分图。

在此基础上,显然“最大危险集”就是二分图的最大独立集,“最小安全集”就是二分图的最小支配集。这二者应当相等。我们注意到,最小支配集的大小等于匹配数,而最大独立集的大小等于N-匹配数,换言之,应当有匹配数=N/2。也就是说,图的左右两边应当一样大,并且有完备匹配。

因此我们总结出三条(其实是两条)判据:

1. 图是二分图。
2. 二分图的两边均有N/2个点。
3. 二分图的匹配数为N/2.

注意,这张图有可能不连通,但这并不影响结论,因为每一个连通块都应符合上述条件。

如果判断图是合法的,那么取字典序较小的那一边输出即可。注意输出格式:行末无空格,而且如果输出0个点,就不应换行。我们队当时PE了三次。

代码:

#include
#include
#include
#include
#include
using namespace std;
const int INF=0x7fffffff/2;
const int SIZEN=510;
int N,M,K;
int dis[SIZEN][SIZEN];
bool vis[SIZEN];
int match[SIZEN];
int col[SIZEN];
int find(int x){
    for(int i=1;i<=N;i++){
        if(dis[x][i]&&col[i]==1&&!vis[i]){
            vis[i]=true;
            if(match[i]==-1||find(match[i])){
                match[i]=x;
                return true;
            }
        }
    }
    return false;
}
bool DFS(int x){
    for(int i=1;i<=N;i++){
        if(i!=x&&dis[x][i]){
            if(col[i]==-1){
                col[i]=(col[x]^1);
                if(!DFS(i)) return false;
            }
            else{
                if(col[i]==col[x]){
                    return false;
                }
            }
        }
    }
    return true;
}
bool check(void){
    memset(col,-1,sizeof(col));
    for(int i=1;i<=N;i++){
        if(col[i]==-1){
            col[i]=0;
            if(!DFS(i)) return false;
        }
    }
    int cnt=0;
    for(int i=1;i<=N;i++) cnt+=col[i];
    if(cnt*2!=N) return false;
    memset(match,-1,sizeof(match));
    memset(vis,0,sizeof(vis));
    int ans=0;
    for(int i=1;i<=N;i++){
        if(!col[i]){
            memset(vis,0,sizeof(vis));
            if(find(i)) ans++;
        }
    }
    return ans==cnt;
}
void work(void){
    if(!check()){
        printf("Impossible\n");
    }
    else{
        printf("%d\n",N/2);
        int cnt=0;
        for(int i=1;i<=N;i++){
            if(col[i]==0){
                printf("%d",i);
                cnt++;
                if(cnt

1009.QSC and Master

题目大意:

在黑板上写一排N<=300个数,每个数都有一个价值val。若相邻两个数不互质,就可以把它们擦去,并获得它们的价值之和(注意,操作后原先不相邻的数可能变得相邻)。问最多能获得多少价值。

题解:

DP:F[i][j][0]代表把区间i~j全部消掉,在这一区间能获得的最大价值。F[i][j][1]代表不把区间i~j全部消掉,在这一区间能获得的最大价值。

转移:

1. F[i][j][0] <- F[i+1][j-1][0]+val[i]+val[j],代表中间全部消掉以后i和j“碰头”,然后再把它们消掉。要求第i个数和第j个数不互质。
2. F[i][j][0] <- F[i][k][0]+F[k+1][j][0],代表分别把前半截和后半截消掉。
3. F[i][j][1] <- F[i][k][0]+F[k+1][j][1],代表前半截消掉,后半截不消掉。
4. F[i][j][1] <- F[i][k][1]+F[k+1][j][0],前半截不消掉,后半截消掉。
5. F[i][j][1] <- F[i][k][1]+F[k+1][j][1],前后都不消掉。

最后答案就是max(F[1][N][0], F[1][N][1]).

代码:

#include
#include
#include
#include
using namespace std;
typedef long long LL;
const LL INF=1e16;
const int SIZEN=310;
int gcd(int a,int b){
    return !b?a:gcd(b,a%b);
}
int ncp(int a,int b){
    return gcd(a,b)>1;
}
int N;
int key[SIZEN],val[SIZEN];
LL F[SIZEN][SIZEN][2];
void update(LL &a,LL b){
    a=max(a,b);
}
void work(void){
    //memset(F,0,sizeof(F));
    for(int i=1;i<=N;i++){for(int j=1;j<=N;j++){F[i][j][0]=F[i][j][1]=-INF;}}
    for(int i=1;i<=N;i++) F[i][i][1]=0;
    for(int i=1;i

1010. Count Primes 

题目大意:

计算[1..n]内的素数个数,n<=1e11.

题解:

一开始没敢写……其实就是打表。首先观察到一个事实:只需要先筛出1e6以内的素数,就可以判断一个1e11以内的数是不是素数。

每隔1.2e7打表,这样表大概有60KB,正好不超过限制。注意,表里存“这一段有多少个素数”,而不是“1..i内有多少个素数”,因为后者数比较大,占空间多。然后求个前缀和。查询时,先查表,然后暴力筛剩下的部分(至多1.2e7)即可。筛法的的效率大概是每秒筛1e8个数,因此不会超时。我筛法的数组只开了1e6,但是用记录“时间戳”的方法,每次不用memset整个数组,因此筛的速度和数组大小无关。

#include
#include
#include
#include
#include
using namespace std;
typedef long long LL;
LL S[]={0,788060,719062,697140,683882,673971,666543,660481,655062,650762,646685,643541,640215,637221,634839,632921,629642,628146,626220,624144,623007,621138,619537,618148,616476,615482,614305,612803,611568,610715,609572,608349,608169,606481,605663,604529,604072,603273,602289,601600,600711,599777,598971,597752,598222,597235,596579,595844,595003,594603,594293,593511,592636,592338,591685,591297,590568,589729,590262,588956,588363,588082,587759,586931,586251,586405,586488,585210,585400,584383,584453,583642,583108,583072,582279,581704,582455,581569,581006,580544,580527,580160,579508,579416,579125,578796,578462,578185,577082,577739,576846,577250,576740,576079,575653,575057,574904,575333,574815,574040,574199,573700,573703,572935,573044,572879,572918,572201,571881,571814,571502,570775,571778,571174,570549,569849,570233,569584,569305,569503,568970,569094,569036,568221,568743,568432,567552,567777,567512,567177,567147,566103,567107,566319,566109,565464,566067,566007,564584,565332,565020,565135,564233,564742,564414,563772,563890,563758,563303,563658,563712,562755,562538,562726,562341,562122,561820,561881,561773,561861,561184,561193,560959,561334,560506,561025,560486,560728,560636,559698,559883,559844,559217,559372,559113,559109,559691,558591,557843,559005,558287,558347,557918,558131,557388,557608,557572,557197,557542,557668,557337,556963,556756,556794,556078,556104,555851,555863,556001,555959,555427,555164,555445,555133,555581,554615,554676,555534,554063,554457,554642,554445,554432,554260,554249,554058,553930,553247,553163,553478,552871,552700,552889,553142,552799,552772,552709,552065,551872,551871,551979,552188,551831,551633,551898,551619,551573,550979,551376,551483,550922,550619,550946,550494,550759,550438,550607,549866,549968,550392,549258,549694,549706,549464,549895,549419,549693,549406,548832,548619,549081,549050,548468,549082,548719,548321,548484,548293,548207,547848,547963,547991,547855,547160,547800,547242,547582,547893,547388,546738,546689,547252,546533,547244,546497,546740,546880,546402,546765,546612,546053,546207,545973,546678,545989,545703,545858,545598,545552,545527,544954,545267,545395,545350,545454,544866,545186,544918,544624,544356,544845,544901,544802,543941,544460,544094,543950,544279,543944,543767,543947,543217,543568,543583,543708,543067,543671,542384,543106,543339,543264,542946,542827,542353,543034,542164,542552,542433,542534,542687,541622,542193,541983,542502,542400,541892,541833,541302,541474,541359,541624,541997,541693,541237,541130,540990,541152,541663,540781,540774,541015,541014,541134,540888,540923,540831,540287,540064,540766,539976,540106,539788,540159,539736,539663,540453,539901,539696,539790,539751,539481,539859,539111,539506,539336,539076,539627,538967,538462,539281,539200,539553,538591,538589,539012,538560,539043,538755,537824,538116,538333,538461,538048,537955,538128,537927,537850,538314,538081,537802,537138,537607,538135,537568,537316,537494,537086,536813,537978,537610,536890,536342,537333,537042,536995,536337,537217,536565,536640,536881,536904,536355,536357,536825,536122,536443,536243,536209,536029,536480,535633,536465,536222,535225,535815,535510,535877,535865,535430,535402,535358,535141,535676,534718,535867,535672,535126,534746,535337,534672,534867,534905,534926,534727,534855,535106,534903,534680,535129,534513,534449,534356,534433,534771,534918,533736,534448,533753,534289,534184,533674,533759,533693,533438,534088,533564,533595,533426,533397,533791,534001,532858,532953,533322,533448,533286,532914,533256,533216,534136,532585,533130,532242,532782,532219,532928,533067,532665,532762,532479,532420,533662,532668,531913,532416,532581,532208,532664,532044,532106,531966,531029,532556,531914,532557,532075,531637,531634,531527,531165,531236,532049,531574,531252,531128,530849,531177,531071,530891,531361,531130,531137,531371,531521,531458,531374,530423,530613,531305,530765,531542,530399,530921,530529,530381,530737,530310,530881,530450,530291,529436,531040,529534,530634,530155,530728,530111,529267,529973,530443,529743,529494,529263,530144,529110,530136,530119,529186,529362,529684,529000,529747,529344,529745,529285,529147,529620,529161,529330,529596,529255,529029,529032,528558,529279,529091,528147,528953,528690,528416,528403,528700,528564,528433,528629,528336,529020,528136,528152,528168,528429,528913,528307,528053,527961,527411,528371,528520,528546,528050,527920,528152,527663,527313,527959,528006,528037,527291,527669,527208,527738,527854,526469,526962,527138,527492,527778,527082,527271,527022,527317,527084,526812,526895,527176,527076,526923,527246,527124,526931,526310,526700,527537,527162,526801,526257,526941,526023,526492,527294,526043,526402,526474,526315,526503,526963,526463,526389,526721,526147,525764,526129,526076,526273,526569,525811,525699,525607,525444,526059,525680,526076,525255,526159,526069,525994,525437,526083,525295,525686,525967,525354,525658,524915,525026,525557,525414,525373,525528,524694,525036,525219,525281,525348,524449,524425,525035,525037,524963,524704,524952,524477,525075,525446,524984,523962,524716,524880,524519,524242,524566,524330,524366,523924,524067,524877,524253,524428,524442,523652,523942,523895,524140,524312,524064,524013,524190,524297,523879,523514,523903,523829,523544,523395,523875,523811,523570,523531,523752,523487,523802,523575,524170,523273,523087,523508,523515,523084,523705,523075,523543,522864,523136,522616,523076,523132,522439,522672,523584,523059,523555,522844,523532,523322,522852,522996,522555,523056,522855,522218,522381,522191,522520,523079,522574,522915,522155,522708,522205,522708,521964,522199,522222,522112,522434,522570,521769,522261,522292,522089,522231,522123,522341,522027,521484,522548,522302,522057,522033,522563,521885,521641,522048,521372,521475,521789,521496,522183,521308,521504,521677,520985,521608,521579,521702,521375,520644,521629,521438,521461,521141,521659,520698,521475,521155,521678,520873,520533,521412,520077,521388,521110,520861,520531,520617,521062,520646,521012,520511,520540,520698,520727,520531,520562,520473,520406,519997,521339,520928,520423,520739,520072,520155,520726,520059,519766,520779,520323,519542,520270,520299,520425,519480,520282,519561,520478,519228,520119,519499,519390,520259,520309,520320,520053,519973,519454,520352,519714,519497,519475,519121,520527,519806,519194,519485,519313,520189,519432,519967,519666,519711,519680,519527,519107,519173,518566,518878,519224,519802,519219,518899,519544,519070,518725,518621,518965,518885,519566,518755,519263,518543,518904,518615,518859,518853,519311,519063,518852,518769,518990,518673,518818,518698,518774,517960,518261,517963,518590,518247,518781,518359,518215,517943,518318,518581,518299,517448,518207,518626,518629,518057,517551,518227,517630,518472,518228,517523,518625,518404,518052,518042,517962,518397,518267,518229,518296,518071,518402,517065,517631,517514,517794,518309,517912,517802,518424,517566,516794,517486,517574,517532,517152,517590,517682,516827,517468,517477,517488,516780,517451,517855,517039,517555,516812,517151,516886,516775,516727,517243,517088,517328,516778,516547,517320,516851,517672,516385,517098,517188,517226,516279,517366,517042,517344,516608,516362,516379,516412,517129,516411,517030,517170,516291,516555,516395,516481,516461,516400,515917,516594,516389,516152,516747,516015,516129,516912,516391,515992,516946,516431,516539,515844,516776,515490,516232,516531,516263,516193,515972,515493,515724,515659,515740,515891,515683,515563,515669,515942,515950,515757,515963,515239,515931,515976,516370,515223,515764,515056,515961,515346,515547,515815,515961,515648,515519,515606,515388,515992,515131,515370,515365,515486,515226,514978,515218,515168,515671,515161,514828,515414,514946,514989,514976,514522,515281,515141,515182,515074,514770,515510,514820,515015,514838,515349,514628,514851,514818,514231,515334,514360,515236,514396,514536,514759,514945,514321,515353,514939,514009,514597,514596,514965,513909,514586,514714,514306,514337,513988,514296,514649,514250,513935,514753,514609,514617,513797,514473,514586,514048,514585,513894,513520,514054,514372,514632,513675,514448,514287,513968,513908,514254,513334,513615,514093,513955,513499,513550,513642,513589,514076,513873,513364,514145,513572,513959,514045,513226,513363,513064,513351,514029,513324,513584,512978,513129,513008,513762,513629,513563,513589,513322,513906,513234,513360,513337,513073,513659,512832,513394,513320,513378,513514,513460,513270,513472,512899,512906,512611,512984,513557,512909,512933,513024,513035,512935,513227,513245,512898,512808,512464,513080,512702,512488,512928,513442,512965,512397,512474,512938,512861,512913,512882,512263,512163,512511,512641,513126,512070,512952,512208,513080,512202,513003,512551,512291,512345,512709,512597,512393,512128,511925,511946,512197,512263,512019,512434,512574,512413,512183,511490,512278,511941,512228,511785,512178,512171,512561,511946,511949,512448,512110,512030,512159,512531,511922,511916,511773,511549,512149,511746,511444,511636,511980,511385,512016,511499,510935,511851,511496,511696,511734,511179,511853,512277,511263,511426,511279,511814,511121,511838,511209,511125,511246,511672,511323,512201,511319,511696,511797,511399,510608,511392,511112,511433,511552,511327,511462,511565,510695,511253,511106,511083,510742,510754,511026,510801,511251,510623,511272,511070,511444,510650,510698,510802,511110,510409,510868,510419,511004,510767,510920,511017,510525,510319,510654,510647,510780,510872,510889,510853,509837,510575,510927,511338,510764,509976,509973,510595,511107,510275,510590,510160,510246,510879,509934,510350,510430,510180,510472,510745,510262,509707,510238,510284,510277,509806,509767,510050,510430,510058,510407,510436,510362,509725,509624,510631,509702,509749,509897,510522,510241,509996,510152,509565,509903,509932,510000,509927,510570,509467,509849,510140,509526,510131,509148,509948,509765,510310,509568,510376,509179,510127,509178,509430,509888,509932,509506,509716,509397,509690,509711,509366,509934,509445,509305,509122,509587,509459,509173,509556,509318,509380,509773,509120,508506,509314,509566,508483,509221,509077,509176,509374,509221,510073,509614,508444,508837,509016,509320,509025,508677,508608,509480,509311,509262,509005,508550,509141,508158,508948,509182,507813,509183,508872,509056,508346,508677,508874,509654,508659,509172,508073,509179,508596,508508,509266,508522,508746,508614,508240,508119,508810,508723,507826,509299,508869,508294,509019,508313,508301,508137,508488,508284,508372,507939,508409,508488,508578,508997,508082,508116,508440,508655,508392,508809,507861,508057,508042,508532,508067,508257,508271,507632,508039,508827,508066,508382,507919,507953,507836,507831,507254,507723,508001,508561,507652,507925,507587,507631,508163,508033,508096,507865,507679,508241,507391,507187,508282,507735,507378,508214,507677,508391,507200,507616,507625,507465,507913,507917,507611,508059,507634,507475,507320,506793,507621,507097,507921,507622,507675,507382,506749,507966,507512,507769,507292,507041,507313,507598,507779,506847,507463,507812,507265,506065,507308,507679,507004,506904,506658,507366,507094,507685,507256,506942,506631,507213,507408,506499,507769,507661,507324,506382,506897,507053,507035,506471,507539,507155,506913,506905,507002,506759,507309,507155,506855,507587,506928,506374,507236,507057,506780,506569,506702,507002,507033,506958,507402,506780,505960,506941,506887,506014,506325,507060,506305,506941,506397,506335,507133,506811,506112,506587,506774,506129,506731,506332,506187,506197,506075,506041,506512,505952,506167,506763,506268,506089,506677,506555,506793,506228,506321,505932,506375,506357,506665,505415,506117,506295,505929,505532,506150,506767,505848,505788,506493,506131,505416,505894,506098,506372,506511,505654,506238,505475,506484,505558,505742,505453,505740,506060,506037,505762,506083,505802,505965,505958,505045,505406,506232,506119,505647,505662,506100,506157,505541,505993,505717,505544,505365,505315,505589,505862,505476,505305,505496,505751,505499,505660,506342,505425,505704,505286,504556,506106,505356,505563,505483,505241,505308,505815,505174,506010,505648,504961,505184,504898,505273,505806,505398,505108,504549,505494,505218,505839,504984,504934,504915,505517,504879,505254,504798,504712,505357,505472,505819,504902,505125,505587,504572,504863,505371,504961,505066,505069,504442,505314,504703,505211,504902,504363,504439,505331,505712,504624,504763,505060,505220,504541,504468,504879,505127,504938,504686,504658,504791,504429,504224,504813,504603,504781,504880,504349,505199,504969,503790,504362,504817,504048,504939,504573,504346,504134,504412,504583,503996,504536,504523,504563,504287,504708,504749,504783,504127,503845,503978,505057,504661,504775,504193,504589,504253,504743,504186,504278,503874,504878,504465,504213,504128,504227,505035,503606,503893,503616,503933,503524,503634,503947,503968,504027,505099,503925,504001,503830,504054,503738,503848,503719,503904,504047,504320,504246,503430,504272,504003,504254,503759,503736,503987,503400,503450,504155,504168,503332,504180,503215,504144,503955,503949,504003,503093,503550,503718,503655,503910,503595,503214,503045,503279,503350,502804,504035,503097,503544,503753,503920,503737,503842,503605,503071,503519,503665,503707,503136,503627,503742,503565,503812,502998,503328,503500,503537,503319,503792,503656,503161,503341,503449,503256,503133,503085,502624,503689,503276,503608,503219,502917,502700,502322,503656,503118,502742,502907,503733,503315,503465,502125,502719,503568,503073,502635,503189,503331,502524,503268,502542,503094,502809,502882,503049,503011,503018,502662,502742,502683,502913,502862,502558,502403,502423,502793,503539,503429,502341,502121,502691,502988,502559,502402,503093,502582,502649,503149,501954,502624,502701,502562,502694,502868,502019,502655,502654,502722,502875,502965,502578,502608,502962,501915,503515,502179,502697,502778,502227,502375,502423,502646,502825,503167,502182,502669,501903,502227,502150,502222,502503,502359,502052,501644,502682,501842,502128,501814,502049,502419,502507,502197,502761,502066,501823,502684,502146,501993,502213,501365,502339,502468,501754,503060,502205,502486,501812,502633,502076,501713,501811,502150,502122,502079,501542,501946,503033,501560,502505,501399,501195,501182,502415,501889,502010,501948,501451,501657,501874,501621,502151,501746,501698,501860,501106,501956,502288,501760,500846,501560,501600,501360,501609,501148,501334,501941,501689,502323,501980,501511,501194,501376,501957,501085,501395,501446,501271,501175,501724,502261,501354,501268,501655,501019,501960,501076,500758,501351,500636,502337,501348,500920,501921,501238,501624,501118,501710,501210,501394,500841,501578,501288,500713,501254,501401,501612,501532,501316,501100,501348,501549,500949,501657,501170,500844,501041,500726,501177,500632,501259,500713,501206,500846,501543,501642,501387,500532,501125,500699,501311,500707,500598,500847,501421,500839,500499,501028,500543,500486,501051,500810,500623,500614,500681,501290,500897,500604,500627,501110,500316,500627,501395,500692,500222,501471,500983,500748,501471,500416,500148,500455,499972,501038,500218,500846,500769,500545,500532,500286,500263,499789,501132,500917,500888,500501,500087,500417,500974,500684,500647,500742,500231,500114,500352,500886,500887,499935,500135,500736,500512,499880,500855,500315,500559,499783,500196,500127,500550,500592,500366,500556,500425,500140,499741,500807,500216,500547,499916,500214,499769,500523,500622,500130,500236,500450,500169,500170,500186,500440,500038,500041,500126,500333,500345,500317,500146,499850,499686,499740,500466,499740,499956,500134,500340,499700,500373,500383,500167,499771,499780,500044,500092,499455,499618,500693,499812,500193,499539,500017,499480,499611,500176,499771,499819,500245,498810,500139,500014,499284,499535,499248,499542,499843,499184,500005,500232,499487,499769,499501,500311,499607,499745,499265,499878,499311,499518,499564,500016,499419,499963,499818,499344,500020,499496,498985,499095,499585,499598,499161,500175,499509,499211,499606,499383,499877,499598,499412,499239,500004,499629,499482,498510,498772,499620,499249,498993,499159,499842,499381,499195,499210,499356,500152,499261,499091,498832,499259,499488,498827,499915,499588,498894,499466,498920,499311,498889,498739,499540,499652,498659,499073,499012,499309,498598,499216,499209,499076,499733,499042,498665,498754,498917,498437,498837,498376,499051,498635,498462,499548,498213,499617,499045,499184,498724,498787,498732,498725,498993,499025,499189,499144,498685,499284,498318,498499,498512,499333,499029,498416,498822,498902,498724,498625,498313,498450,498763,498237,498494,498331,499191,498050,498186,499135,497732,498618,498252,498659,498941,498365,498936,498385,497910,498256,498263,498974,498889,498629,498909,498088,499105,498389,498471,499006,497868,498359,498110,498580,498029,499067,498677,499011,498426,498507,497946,498105,498088,497761,498699,499228,498486,498294,498338,498143,498320,498800,497909,497476,498295,498345,498324,498024,498715,498079,498325,498208,498068,498220,497733,498732,497909,498559,498594,497915,498367,497475,498260,497688,498021,498127,498278,497785,498447,497767,497817,497880,498238,497722,497843,497321,498065,497739,497686,498257,498125,498273,497143,498287,497781,497774,497788,497910,498478,498166,497231,497585,497941,497474,497789,498428,497537,497684,497764,497576,498142,498113,497971,497293,497519,497486,497914,497360,497782,496738,497546,497646,497602,498004,497455,498119,497358,497150,497820,498210,498119,497413,497681,497945,497263,497819,497971,497042,497907,497358,497627,497509,497401,497431,497878,497024,496895,497844,497134,497321,497487,496804,498179,497186,497295,497233,496821,497847,497385,496643,497429,497671,497470,497380,497314,497517,497947,497190,498198,497115,497068,497786,497156,497145,497542,497043,497092,497382,497375,497164,496893,497268,497409,496730,497059,497049,496905,497040,497184,496832,497033,496743,496873,496974,497645,497312,497150,496613,497250,497387,496705,497466,497205,497167,497094,497038,496419,497137,497591,497274,496965,497101,497074,497020,496678,497000,497144,497053,496410,496750,497455,497004,496773,496660,495940,496839,496999,497174,497452,496626,496595,497181,496426,496071,496094,496559,496603,496489,496909,496649,496971,496230,497158,496605,496234,497097,496206,496352,496572,496198,496299,497662,496682,496769,496560,497242,496421,496943,496586,496073,496462,497039,496224,496664,496923,495854,496393,497147,496066,496621,495858,497192,496613,496915,496302,496219,496316,496141,496327,496032,495913,496944,496065,496134,496007,497143,496238,496168,496425,496198,496683,496059,495957,496520,496321,496289,495707,496393,496431,496228,496093,496171,495961,496412,496662,496307,496580,496236,495708,496512,495865,496161,495691,496802,495950,496847,496356,495554,496672,495669,496157,496172,496234,496305,495891,496022,495904,496332,496232,495596,495678,495729,495482,495985,495742,495980,496557,496302,495852,495947,495937,496713,495961,495587,496098,495761,495846,495772,496111,495642,495249,495876,495458,496110,495675,495834,496409,496337,495632,495543,496204,495511,496000,495486,495505,495811,495860,495617,495561,495936,495451,495388,495466,494817,495219,495775,495992,495704,495533,495710,495641,496764,495088,496373,495545,495609,495999,495086,495373,495606,495538,496437,494909,496077,495033,495153,495483,495921,496420,495380,495288,495733,495586,495819,495155,495591,494620,495565,495773,495540,495260,495417,495795,494922,495002,495364,495330,495537,495268,495921,495076,495461,494567,494815,495523,495141,494985,495171,494890,495403,495070,495066,495472,495590,495281,495191,495512,494697,495205,495119,495673,494995,494524,495462,495109,494692,494681,495485,494787,495035,495612,494762,495078,494946,495058,494876,494965,495178,494645,495240,495161,494248,495082,494710,494950,494770,494538,495118,494711,495221,495293,495290,494766,494882,494045,495457,494766,495328,495160,495253,494726,494951,494879,494881,494571,494435,495006,494926,494286,494648,494876,495029,494732,494666,494858,494743,495081,494958,495165,494607,494524,493931,494593,495676,494986,494594,494806,494845,494424,494743,495364,494511,494432,494423,494262,494393,494957,495179,494539,494712,494928,494895,494598,494516,494477,494639,494532,494424,494013,495186,494586,494511,494982,494848,493841,494553,494629,494401,494243,494503,494616,494901,493950,494878,494390,493933,494733,494263,494282,494378,494501,493900,493543,495440,493805,494119,494858,493838,494985,494087,494606,494889,494754,493678,494584,494313,493796,494966,494682,494186,493883,494175,494011,493632,493814,493521,494381,494327,494518,493761,494307,494402,494556,494281,493619,494603,494492,494566,493486,494400,494380,493798,493838,494104,494584,494113,493973,494299,494071,493627,494261,494904,493822,493822,494359,494207,493689,493214,494473,494608,494530,493299,494150,494287,493348,493718,493994,493850,493787,494250,494446,493745,493816,493380,493850,493872,493869,494347,494185,494160,494066,494033,493274,493597,493999,494166,493697,493572,493442,493760,494002,493606,493346,493914,494016,494446,493572,494096,493414,493827,493736,494649,493601,493906,494492,493698,493077,493520,493286,493702,493732,494152,493149,493872,493326,493842,493978,493643,494006,493437,493509,493701,493222,494014,493414,493496,492855,493985,493331,493221,492832,493303,493414,492671,493788,493413,493282,492497,493512,494131,493261,493451,493771,492638,494314,494404,493042,493295,492957,494058,492751,493413,493488,494051,493436,493572,493452,493771,493469,492852,492874,493416,493560,493085,492825,493083,493107,493352,493005,493499,492950,493530,493470,492761,492703,493142,493387,493186,493021,493602,493293,493209,493094,492580,492706,493370,493401,493045,492948,493044,492709,493409,493421,493110,493288,492480,493122,493131,493241,492292,493249,493081,493123,493184,493141,493037,492694,493329,492349,493504,492884,493097,493139,492966,492703,493261,493254,492590,492885,491796,493304,492970,492744,492547,493541,493096,492304,492977,492858,492352,493089,492522,492875,493247,492857,493010,492622,492813,493081,492301,493012,492856,492880,493033,493022,492657,492167,492907,492408,492941,492218,492639,492433,493409,492962,492708,492563,492353,492960,492531,492479,492778,492898,492362,492698,492250,492816,493156,493217,493179,492497,492355,492694,492493,493014,492704,492708,491872,492387,492218,492640,493348,493222,491852,492843,492234,492537,492670,492628,492464,492112,492159,491823,491704,492722,492764,491970,492282,492263,492403,492429,492189,492817,492426,492067,492226,492234,492347,492556,492141,492041,493072,492471,492156,492576,491651,492419,492720,492430,492169,491515,492434,491357,491950,492578,492686,492374,491830,491919,492379,492690,491638,492666,491721,491931,492126,491899,491758,492074,491668,491793,491707,492234,492867,492012,492292,492182,492011,492725,492735,492069,492138,492125,492183,492129,492299,492153,491527,492162,491837,491120,491264,492019,491989,492336,491809,491696,491512,491971,492096,492040,491984,492236,491817,491276,492457,491948,491577,492116,491887,492132,491427,492175,491872,492122,491848,491882,492370,492024,491827,491046,491594,491539,491677,491233,491328,491818,491269,491782,492106,491873,492417,492229,492114,491737,491329,491056,492118,491750,491317,491834,491885,491941,492120,491730,492152,491363,491590,492134,491146,492048,491703,491830,491875,491208,491477,492026,491212,491434,491514,491850,491848,491521,491651,491372,491314,491245,491562,491195,491236,491336,491671,491697,491257,491609,490914,491337,491211,491708,490935,491109,492208,491405,491572,491470,491880,491611,492171,491544,491371,491260,491507,491116,491316,491426,490952,491672,491548,491319,491895,491145,491455,490992,491032,490957,491707,491239,492543,491677,491646,491490,491437,491114,491033,491105,491403,490652,491274,491143,491250,491385,490919,491527,490690,491516,491345,490815,490813,492125,491643,492042,490635,491097,490960,490970,490936,490686,490743,490750,491697,491986,491285,490942,490301,491102,491445,490813,491324,491025,491263,490158,490546,490776,490508,490944,491073,490431,490875,490670,490961,490895,490287,490824,491224,491267,490743,491839,490982,490542,490364,491637,491280,490719,491154,490818,491143,490767,491051,490880,490218,491358,490750,490978,490815,490749,491201,490836,490691,490843,491186,490289,491124,491285,490944,491248,490371,491021,491079,491041,490931,490368,490348,490924,490277,489910,490356,491018,490738,491219,490704,490914,490937,491165,490852,490785,490760,490466,490691,490207,490886,490536,491116,490169,490800,491025,489983,490620,490793,490186,490586,490963,491128,490522,490525,490015,491196,490483,490293,490750,491180,490453,490415,490540,490918,490904,490811,490031,490436,490307,490582,490610,490381,490860,490512,490091,490360,490512,490075,490286,490437,490508,490578,491001,490513,490985,489866,490427,490962,490534,490017,490002,490747,490356,489874,490830,490487,490493,490545,490532,490258,490089,489884,489994,489787,489967,490517,490523,490453,490645,489827,489783,490426,489721,490264,489421,489553,490196,489731,489886,490537,489949,490705,489861,490190,490866,489968,490460,490031,489911,490375,489616,490246,489102,489356,489879,490614,490287,489977,490251,490148,490322,490139,490006,490330,489501,489957,489888,490097,490203,489787,490450,489274,490363,489354,490127,489311,490380,490167,490495,489775,490081,490043,489354,489699,490280,490234,489577,490111,490187,489837,490015,490235,489797,489709,489718,489626,490090,489711,490259,490013,489767,489489,490014,489420,490625,488910,490236,489986,489629,489901,489984,490173,489831,489595,490261,489891,489236,490450,489861,489672,489675,490052,490028,489723,490256,489464,489178,489783,490124,489916,489246,489353,489545,489309,489800,490142,489675,489941,489568,489426,489432,489528,489458,489093,489745,489780,490558,489599,489499,489109,489591,489660,489293,490032,489553,489658,490076,489734,489306,489653,489494,489669,489431,489527,489660,489060,488955,489235,489078,490221,488884,489680,489154,489989,489339,489173,489657,489652,489274,489685,489904,488765,490332,489246,489228,489583,488694,489502,489553,489702,489601,489283,489840,488953,489374,489014,489554,488953,488964,489631,489519,489702,489641,489366,488945,490019,489647,489057,488943,489157,489682,488644,489056,489179,489114,489510,489383,489382,489181,489885,489032,488513,489360,489673,489196,489255,490074,489040,489299,489320,489004,489216,488703,489268,489125,488932,489049,489367,488864,489148,488800,488857,489424,488689,489147,489352,489106,488816,488877,489082,489303,488653,489405,489390,488683,489381,488317,488855,488857,488596,488270,489345,488693,489136,489038,488947,488782,489326,489764,488798,488428,488943,489028,489416,488939,489126,488509,488592,489840,488933,488894,488552,489470,488658,489061,488435,489000,488859,489505,489169,488599,489208,488075,488672,488898,489084,489376,488481,488858,488501,488654,488958,489301,488154,488732,488745,489181,488487,488254,488407,488538,488676,488318,488587,489038,488205,488272,488871,489265,488406,488953,488372,488059,488551,489155,488753,487974,488863,488519,488779,488540,487919,488511,489174,488493,487974,488542,488685,488186,488772,489079,488932,488422,488725,488825,488561,488864,488600,488573,489087,488401,488758,487855,488443,488178,489123,488697,488661,488733,488289,488468,488266,488439,488814,487884,488048,488354,488471,488423,488705,488759,487854,489059,488595,488874,488405,488290,488078,488404,488210,489038,488668,487523,488897,487778,488606,488454,488433,488327,487774,488699,487945,487590,487854,488021,488769,487527,488408,488100,488351,487909,488239,487932,488533,488280,488375,488447,488165,488088,487826,488151,488537,488428,488644,488559,488347,488304,488260,487923,488148,488675,487598,488151,488032,488232,488079,487857,487233,488607,487721,488606,487978,488321,488580,488656,487680,487933,487814,487904,488078,488002,488073,487816,487502,488085,488614,488142,488081,488132,487564,487539,488190,488709,486761,488892,487473,488237,488199,488473,487777,487379,488252,488181,488016,488137,488052,487785,488290,488334,487659,488114,487960,487491,488664,487283,487786,487459,487323,488574,488163,487313,487581,487678,487685,487665,488241,487614,487771,487942,487295,487815,487989,487877,487913,487281,488241,487594,487748,487543,488030,487581,487104,488099,487325,487903,487789,487636,487605,487619,487862,488499,487559,487628,487905,487730,487624,487830,487587,487359,487618,488126,487571,487366,487318,486997,487901,487551,487233,487836,488869,487219,487658,487123,487825,488184,486893,487529,487857,487814,487521,487458,488090,487532,487206,487733,487899,487666,487739,487252,488002,487521,487452,487925,487702,487210,487905,487421,487368,488009,486827,487533,487142,487519,487194,487537,487090,487474,488325,487683,487324,487547,487786,488130,487472,487155,487302,487004,487903,487465,486907,487064,487062,487412,488106,487678,487266,487884,486706,487138,487042,487127,486888,487504,487844,487288,487253,486894,486966,487349,487219,487817,487638,487187,487717,486902,487169,486784,487135,487263,487129,487477,486587,486776,487270,487032,487203,487613,486919,487093,486589,487503,487249,487433,486681,487085,488092,487300,486943,487285,486848,487443,487283,487369,487091,487457,487536,487192,487354,487286,486722,487238,486514,487174,486168,486645,486931,486694,486737,487253,486871,486685,487370,486439,486886,487330,486647,486923,486688,487393,486822,487363,487554,487149,487229,487167,487826,487095,486782,486727,487030,487358,486947,486031,486939,487078,487626,486511,486540,487442,487048,487398,486534,486880,487151,487246,487022,486620,486450,487283,487056,486841,487097,487311,486693,487057,486766,487108,486252,486914,487010,487254,486264,486726,487362,487031,486508,486903,487039,486494,486839,486871,486435,486360,486525,487056,487230,486702,486774,486465,486760,486900,486533,487005,487190,487276,486560,486502,486769,486661,486799,486325,486980,486097,487070,486413,487132,486922,486909,486645,486312,486963,486564,486774,486309,486882,486020,486418,486405,486757,486760,486540,486225,486629,486500,486094,486345,486227,486418,485974,487071,486930,487556,486647,485637,486835,486322,486777,486753,486246,486146,486353,487267,486951,486682,486826,486189,486994,486366,486334,486791,486356,486612,486341,486724,486406,486022,486777,486521,486468,486919,486028,486326,486772,485648,487045,486428,486029,486270,486080,486071,486501,486012,487226,486388,486811,486291,486190,486455,486626,486098,485029,486362,485993,486843,485696,486030,486113,486239,486133,486225,486131,485821,486245,486139,485842,486435,486394,486055,485765,485860,486157,486478,485839,486641,486656,486777,485919,486144,486157,486163,486134,486059,485831,485704,486891,485688,486639,486263,486835,486498,486304,486340,486453,485660,486416,486672,485915,485777,485903,485917,485996,486430,486439,485993,486152,486296,485488,486397,486530,485490,486081,486415,485616,486106,485623,485402,486197,486118,486223,485936,485657,485417,485992,486052,486392,485099,486398,485500,485717,486919,486229,486613,485697,485576,485903,486067,486482,485599,486388,485915,486310,485647,486008,485662,485542,485935,486020,485843,485818,486807,486637,486059,485659,485661,485747,486646,485902,485455,486029,486005,485552,486102,485612,485960,485783,485895,485778,485892,485921,485268,485858,486117,485653,485736,485527,485146,485754,485827,485576,485589,485733,485626,485602,486045,486329,485633,486203,485290,486205,485003,485238,486042,485119,485596,485832,485549,485546,485552,485710,486431,485150,485386,485618,485726,486200,484913,485851,486177,485538,485484,485198,485201,485408,485623,485411,485317,485241,485020,486058,486028,486299,485456,485256,484676,485716,485442,485704,485332,484829,486095,485563,485266,486048,485330,485661,485181,486010,485859,485487,485302,485456,486547,485124,486033,485413,486089,485986,485187,485089,485792,485048,484550,484907,485467,485060,485150,485613,485070,485800,484767,485111,485966,484694,484911,485758,485936,485177,485360,485633,485282,485457,484683,485671,485173,485702,485828,485236,485816,485579,485114,485252,485045,485570,484902,485230,486033,484828,485090,485482,485942,485087,485463,485463,485564,485288,485498,485690,485129,485447,484845,485287,485266,484948,484855,485324,484737,484964,485400,484531,485203,484639,485646,484353,485257,485450,485055,485088,484999,485402,485203,484730,485447,484871,484657,485669,484708,485037,485234,485250,485506,484693,484712,485484,484850,485447,484989,485162,485598,485020,484954,484957,484666,484858,485132,485350,484994,485212,484829,485122,484615,484633,485243,484690,485069,485006,485104,485561,484568,484545,485478,484571,484755,485063,484003,485182,485551,484606,485462,485007,485344,484886,484876,485280,485137,484198,485668,484295,484501,484931,485134,484841,484838,484929,484373,484397,485315,485338,484368,484891,484764,485231,484434,484921,485201,485307,484927,484551,484528,484951,484562,484953,484427,483975,485187,484712,484777,485064,484900,484476,485335,484403,485523,484812,484382,485271,483752,484783,485171,484636,485063,484343,484828,485015,483532,484528,484501,484443,484824,483878,484568,484857,485529,484872,484337,485050,484597,484250,484374,484660,485114,484855,484499,484736,484835,484613,484854,484293,484369,484005,485210,483628,484938,484052,484351,484462,484718,484585,484990,484714,484403,484681,485082,484000,484163,484538,484550,485012,484711,483968,483851,485218,483809,484513,485545,484325,484020,484571,484995,484935,483897,484435,484816,484513,484784,484877,484342,483992,484990,483791,484355,483993,484509,483376,483452,484186,484481,484723,484938,484379,484194,484084,484581,484689,484343,484583,484070,484248,483964,484743,484336,484917,484135,484789,484310,484906,484565,484371,484180,483949,484426,484305,484534,483815,484080,484094,484428,483778,484505,483968,484397,484329,484580,483778,483774,484055,483984,484234,484831,483908,483965,484723,484248,483991,484253,483529,484398,484358,484207,484549,484012,483860,484234,484578,484349,484025,484518,483977,484015,484214,484028,483865,484195,484462,483673,484096,484482,483789,484100,483918,483966,484242,484682,484112,483455,484488,483994,484039,483765,483846,484111,484022,483847,483349,483524,483579,483725,484182,483905,483408,483481,484708,483512,483804,484218,483732,484357,483738,483763,484373,483444,484386,484562,484070,484433,483809,484130,483796,483847,484028,484057,483959,484230,483812,483616,483441,483835,483532,483845,483954,483649,484240,483640,484069,483499,484476,483930,483725,483862,484071,484694,483760,483426,483360,483569,484193,483816,483856,484404,483555,483939,483825,484214,484142,483161,484284,483246,483426,484231,483454,483944,484038,483534,483865,483964,483244,484421,484274,483767,483762,483195,483262,484205,483611,483616,483703,483737,483792,484021,483474,484080,483685,483746,483032,484309,483619,484096,483690,483002,483436,483469,483817,483544,483624,483466,483361,484043,482989,483846,483281,483917,483935,483908,482863,483565,483610,483924,483213,483376,484140,483000,482903,483421,484023,483910,483971,483393,483751,483466,484029,483660,483347,483986,483006,483741,482816,482871,484064,484059,483689,483534,483848,483684,483628,483673,482802,483737,483759,483647,483555,482959,483912,483248,484116,483489,483016,484020,483636,483607,483116,483137,483399,483763,483180,483691,483772,483516,483077,482520,483574,483660,483325,483575,483920,482973,483384,483594,483319,482988,483767,483252,483652,482803,483405,483010,483551,482796,483634,483397,483178,482885,483359,483540,483419,482156,483896,483931,483276,483441,483267,483325,483105,483678,482661,483949,483171,483531,483213,482779,482736,482772,482597,483770,483124,483451,483113,483287,483414,482728,483309,483134,483226,482747,483547,483250,483363,482911,483147,482693,483391,482921,483435,483595,482880,482966,482677,483709,482916,483777,482443,482705,483289,483446,482739,483206,482217,482594,483255,482520,483445,483253,483387,482543,483829,482886,482571,483067,483167,482906,483145,482807,482964,482973,483186,483106,482789,482659,482546,482613,483158,483542,483197,483644,482998,482851,482524,482778,483338,483107,482240,482922,483047,483653,483037,482748,482405,483342,482501,482512,483405,482688,482637,483495,482955,482611,483663,483208,482519,482551,483615,482726,483056,482688,482545,483704,482939,482357,482533,481884,482276,483321,483073,482680,483307,482647,483437,483423,482374,482770,483541,482857,483023,482624,483306,482546,482877,482654,482761,482460,483063,483138,482403,482156,482518,482865,482669,482974,482224,482833,482286,482526,482634,482303,482035,482870,482634,482548,483044,483420,482415,483012,482501,483032,482213,482697,482642,483260,482808,482727,482891,482649,482753,482672,482112,482934,482464,482428,482896,482838,482267,482932,482810,482551,482275,482208,482469,482980,482954,483063,483241,482335,483007,482675,482541,483202,482663,481570,482549,482598,482351,482489,482831,482760,482018,482409,482616,482114,482523,482193,482725,482556,482352,483042,481868,482266,482651,481872,482528,482538,482373,482660,482260,482692,482881,482606,481945,482413,482426,482473,482831,482473,482289,482533,482476,481898,482259,482527,482707,482158,483371,481690,482328,483061,482858,482140,483179,482584,482195,481655,482532,482864,481747,482513,482117,481685,482955,483108,482729,482008,482425,481771,482278,482497,481999,482224,483344,481671,482135,482025,481831,482164,481675,483076,482569,482111,482126,482135,482566,482228,482797,482370,482351,482839,482418,482336,482035,482199,482093,482096,482623,482165,482771,481717,481848,482329,482119,481904,482935,481653,482701,481793,482355,482575,482102,481983,481764,481876,482242,482153,482714,481487,482450,482524,481606,481947,482336,481844,482035,481718,481827,481516,481816,482237,482465,481901,482559,481389,482011,482390,481450,481908,481870,482798,481530,481861,481794,482860,482157,482499,481934,482014,482128,481875,481819,481921,481977,482070,482364,482031,481245,482068,482681,482135,481813,481800,481710,481930,482308,482366,481963,481695,481794,482066,482135,481950,482177,482259,482007,481471,482081,482692,482186,481724,482267,481791,481983,482483,481215,481509,482689,481504,481346,481621,482243,481867,482018,482037,482277,481595,482134,481871,482306,481704,481837,482735,481703,482074,481542,481251,482036,481602,481452,481699,481441,481934,481540,482439,482008,481721,480876,481373,481704,482039,481791,482122,482001,481874,481803,481578,481250,481967,481692,480795,481596,481311,482147,481477,482128,481655,482314,481548,481625,481549,481973,481775,481477,481594,481302,481775,481393,482067,481714,481336,481807,481840,481306,481622,480974,482114,481723,482272,480760,481900,481624,481632,481685,482367,482060,481686,481287,482149,481605,482049,481577,480798,481834,481410,482013,481256,481703,481802,481425,482614,481320,481612,481040,481220,481694,481091,481490,481502,481562,481097,481672,481636,481902,481513,481674,481194,482008,481161,481555,481576,481545,481620,482281,480799,481374,481400,481019,480890,481673,481647,481358,481401,481561,481633,481439,481389,481363,480969,480860,481546,481528,481149,481810,481419,482080,481001,481152,481019,481338,482050,480925,481569,481249,481459,480866,480991,481302,481310,481994,480989,481122,481876,481610,482004,481406,481028,481128,481607,481627,480812,481159,480870,481505,481826,481300,481459,480856,480717,481082,481683,481206,481446,481537,481484,480879,481084,480937,481717,480586,480996,481839,481635,481268,481246,481558,481139,481659,481223,481329,481481,481258,480927,481246,481309,481510,481163,480812,481365,481087,481428,481592,481413,481163,480709,481409,481656,481376,480984,480646,480403,482126,481143,480297,480491,481082,481329,481209,481416,481593,481579,481611,480713,481453,480837,480120,481005,480934,480870,480905,481053,481700,480616,481351,480578,480513,481449,481073,480912,480800,481224,481485,480641,481002,481044,481287,481428,481628,480489,481318,481451,480554,481406,481375,481221,481004,480753,481267,481765,480652,480996,481393,480861,481208,480493,481105,481375,480463,480366,481117,480452,481102,481276,481444,481464,480407,481141,481139,480600,480719,481281,480661,481025,481136,481493,481194,479832,480707,481232,480870,480973,480721,481165,481034,480129,481478,480815,480381,481350,481171,480409,481224,480986,480368,480708,481007,481057,480751,481148,481485,481171,481222,480228,481112,482052,480696,480426,480328,480974,480886,480458,480999,480372,480641,480964,480617,480707,480935,481202,480645,480854,480440,480769,480604,480282,480610,480428,481296,480852,480943,480662,481457,480634,480715,480564,480119,480697,480787,480412,480404,480883,481328,480197,480899,481097,480219,480544,480230,481246,480560,480494,481313,481300,481137,480816,480622,479985,480764,481291,480413,481395,480517,480459,480861,479943,480518,479920,480375,480690,480642,480951,480060,480926,480181,481032,480992,480603,480122,480433,480696,480361,480897,480147,480963,480429,480240,480902,480278,480553,480673,479751,480081,480362,480516,481205,480535,480525,479702,480690,480215,480238,480837,479770,480810,480208,480584,480683,479717,480545,480833,479962,480445,480446,480785,480046,480760,480573,480363,480684,480502,480766,479325,481039,480757,480763,480434,480314,480089,480210,480433,479846,480896,479800,480440,480542,480406,480289,480203,480370,480338,480849,480354,480628,479720,480080,480439,480938,479865,480215,480401,480499,480221,479958,480870,480416,480285,479863,479568,479957,480260,480892,480229,480691,480041,479843,480148,481047,480589,480526,480490,480912,480368,480416,480391,480177,480371,480734,480429,480159,480495,480574,480646,480253,479980,479999,480027,479896,480192,480355,479636,481003,480543,480676,479976,480433,480585,480792,480224,479561,480605,480253,480881,479901,480102,480515,480311,480335,480500,479901,479682,479160,479998,479735,479905,480095,480486,480184,479014,480389,479956,480203,479160,479792,480497,480618,480085,480140,479968,479997,480007,479828,479575,479810,479817,480007,479057,480155,480017,479725,479804,480783,479568,479936,479714,479742,479911,480531,479793,479478,479643,479816,479765,480286,479693,480269,479432,479786,479738,480302,479773,480286,480425,479916,480438,479486,480125,479278,480371,480008,480120,479578,479906,479237,480952,479822,480605,480346,480235,480109,480164,479189,479911,479615,479628,480133,480196,479367,479753,479697,479939,479061,480391,479869,479561,480158,480579,480312,479683,479777,480514,479636,479562,480086,479675,479982,479573,479236,479523,480357,479778,480080,479500,479432,479509,480577,479559,480129,479482,479704,479732,480078,479805,479902,479303,479893,479897,479357,479665,480533,479791,479261,479911,479718,479819,480103,479516,479443,479946,479688,480031,479496,480016,479772,480161,480432,479392,479223,479764,479759,479928,479630,479096,480392,480263,479745,479734,479454,479099,480054,478882,479584,479897,479982,479496,480011,479635,479915,479920,479772,478904,479950,479584,479137,479678,479608,479389,479316,479048,479420,480321,479295,480163,478993,479613,479841,479523,479284,479488,479296,479750,479570,479418,479635,480044,479343,479880,479349,479196,479316,479290,479573,478872,479456,479766,479392,479874,479159,479128,479345,479176,478894,479378,479002,479482,479698,479178,479024,480057,479101,479465,479712,479364,479593,480089,479205,479356,479900,479125,479311,479297,478893,479352,480183,479215,479270,479755,478950,479780,479368,479617,479844,479814,479499,478867,479281,479342,479449,479426,480405,479074,479858,478971,479129,478891,479405,478507,480358,480031,479459,478955,479865,478943,479560,479669,479065,478939,479080,478988,479709,479522,479452,479392,479186,479258,479678,479003,479109,478994,479478,479560,479455,479383,478792,478554,479807,479740,478690,479168,479655,478791,479486,479154,479911,479200,479150,479132,479146,479103,479640,478958,478644,479150,479501,479641,479414,479250,479355,479401,479278,479061,478758,479148,479599,479005,479244,478570,479326,478841,479282,479261,479199,479592,479053,479103,479118,479002,479251,479181,479163,479449,478379,479749,479596,478949,479249,479034,478253,479445,478960,479288,479529,479264,478759,479058,479376,479302,478745,479314,479283,479191,479136,479280,479323,478842,478956,479118,479115,479311,478854,479016,479453,478947,478789,479177,478554,478622,478828,478070,479616,479184,479030,478376,479665,478550,478503,479689,478994,479180,478935,479791,478769,479192,478878,478885,479279,478744,478633,479025,478880,478485,479681,478678,479272,478812,479371,478245,478696,479605,479015,478566,478955,478467,478239,479621,479427,478214,479699,479384,478757,478358,478725,478980,479162,478997,479200,478373,478828,478904,479216,478723,479084,479411,479207,479255,478779,479124,479330,478959,478941,478571,478492,479127,478995,479123,479230,478651,478885,478939,478545,479152,478595,478989,478393,478498,479879,479000,478005,478600,478479,478657,478345,478479,478613,479367,479137,478567,479296,479258,478782,479198,478786,478912,477212,478980,478391,478713,478488,479098,479747,478372,478472,478577,478367,479133,478526,479272,478551,478913,478635,479188,478031,478948,478815,478449,479316,478293,478925,478883,478942,478447,478408,478407,478790,477670,478568,478962,478169,478921,479107,478660,478411,479169,478463,478106,478615,477903,478631,478756,478946,479205,478379,478536,478815,477836,478365,478754,478438,478398,478963,479016,478333,477815,478474,478837,478590,478815,478368,478494,478020,478059,478214,478823,478250,478333,478294,477976,478626,478574,478316,478584,478451,478461,478236,478309,478228,478101,478558,478310,478255,478097,478791,478995,478480,478279,478338,478958,478355,477820,478108,478416,478937,478336,478610,478712,478119,478673,477650,478533,479191,478741,478534,478332,478343,478274,478610,477639,478055,478525,478689,478574,478860,479200,477985,478629,478076,477457,478453,478418,479227,478198,478412,478386,478287,477937,478183,478451,478618,478133,478410,478356,478298,478065,478659,478233,478620,478689,478674,478432,478482,478192,478016,477819,478229,477968,478536,478512,477774,478857,477865,478692,478258,478274,478241,478250,478613,477967,478146,478820,477620,478870,478662,478933,477506,478736,478037,478532,477738,478587,478463,478916,478202,478097,478460,478719,478468,477518,477669,477767,478210,477767,478458,478172,478116,477889,477516,478812,477629,478061,477981,478057,478094,478795,478519,478149,477891,477769,478569,478528,478208,477317,478543,477911,478242,477059,478466,477849,478464,478097,478921,477310,477927,478147,477628,478288,478464,477480,478065,478297,477871,478524,477372,478099,478210,477537,477233,478427,478696,477554,478321,478610,477769,477917,478549,478376,478519,477774,478027,477803,477478,478367,477532,477418,477830,477941,477848,477940,478282,478424,478216,478573,477156,477764,477355,478695,477869,478027,477551,477510,478489,478131,477492,477334,477481,478498,477975,478196,477615,478042,478238,478565,478082,477976,477569,478237,477762,478022,477636,478243,477660,478025,477986,478129,477984,477777,478089,477778,477674,477860,478436,477588,478244,477253,478297,477464,477993,477710,477215,477736,478033,477679,477747,478502,478504,477193,477973,477523,478585,477401,477567,477653,477814,477618,477870,477376,477667,477315,477715,477927,477121,478169,477598,478581,477486,477737,477939,477943,477462,477963,477735,477766,477273,478491,477675,477474,478035,478016,477451,477468,477578,477469,478030,477602,478753,478021,477841,477456,477435,477484,477249,478060,477874,477559,478180,478060,476780,478054,477371,477534,477883,477025,478152,477481,477800,477658,477393,477746,477779,477701,478018,477895,477470,477485,477901,477363,477440,476870,477685,477492,477785,477612,477165,477473,477351,478322,477342,477308,477677,477417,477846,478005,477468,478691,477298,477614,477694,477645,477563,477826,477674,477626,476742,477373,477158,477126,477382,477636,477485,477084,478245,477599,477544,477875,477718,477192,477502,477344,476441,477412,477240,477871,477837,477984,477233,477895,477964,477967,477208,476692,477487,477546,477524,477773,477380,477863,477875,477391,477238,476912,478164,477801,476827,478314,477712,476904,477218,477390,477102,478162,476988,476983,476979,477091,477639,477341,477937,477537,478094,477365,477873,477158,477032,477305,476783,477789,477496,477988,477622,477546,477538,476578,476770,476806,477459,477985,476740,477515,477907,478008,477420,477173,477280,477230,476823,477124,477382,477597,477450,477159,476511,477441,477404,477098,476887,478189,477022,477537,477231,478146,477134,477516,476601,477380,477018,476922,477164,476742,478135,477452,476602,476968,477222,477038,476999,477519,476730,476950,477514,477776,477164,477182,477559,477599,477408,477103,477674,477267,477647,477291,477717,476973,476934,477261,477450,477651,476976,477185,477547,476869,478253,477150,477401,476850,477459,476872,476883,477007,477455,477456,476415,477068,477603,476819,477300,477167,477306,477236,477253,477145,477051,476855,477041,476136,476979,476617,476918,477088,477237,477504,477514,477022,476483,477527,477879,477099,477405,476603,476553,476939,477610,476854,476843,476902,476313,476923,477949,477273,477262,476488,477091,477473,476949,476790,476253,476734,477241,476890,476524,477057,477217,477401,476324,476821,477050,477049,477198,476577,476783,476875,476685,477127,476427,477611,477412,477572,477083,476761,477070,477049,477026,477442,476963,476817,476677,477178,477602,477482,476674,476744,477049,476993,477553,476840,476883,477304,476897,476739,476759,476016,476569,477359,476244,477130,476914,476849,477439,477218,476984,477091,476060,477547,477303,476337,476340,476989,476881,476533,477140,477010,477307,476812,476735,477005,476351,476825,476774,476699,476865,476926,477191,477265,476425,476789,476557,476241,476646,476503,477070,476689,476675,477566,476820,476937,477224,477068,476853,476952,476827,476639,477078,476045,477174,476541,477135,476720,476918,476529,477141,476850,476537,476656,476337,476421,476187,476529,476737,476011,476452,476286,476881,476844,476780,476530,476512,476594,476260,477080,476733,476803,477741,476679,477082,476583,476350,477322,476551,476957,476724,476527,476895,476591,476322,476325,476681,476976,477367,476161,476940,476558,476951,476412,476633,476509,476351,476596,476976,477001,476377,477284,476757,476583,476802,476699,475882,476202,476818,476223,475684,477522,476628,476039,477148,476024,476676,476431,476283,476569,475844,476782,475923,475586,476484,477066,476893,476467,475900,476519,476560,476582,476374,476023,476244,477141,476536,476898,476234,477119,476060,476323,476741,476424,476211,476830,476577,476615,475865,476252,476891,476599,476051,476282,476780,476503,475910,476699,476259,475918,476822,476608,476250,476909,476271,477174,476303,476629,476495,476632,476099,476883,475567,476613,476686,476502,476332,476598,476515,476636,476396,476084,476984,476737,476268,475991,476383,476659,476852,476503,476430,476148,476232,476857,475974,476985,476063,476623,475786,476969,476957,476447,476391,476530,475555,477155,476108,476106,476408,476512,475853,476624,476036,476894,476188,476322,476567,476779,475785,475718,476062,476126,476322,476061,476481,476216,476082,476283,476280,475999,476602,476025,476458,476097,477037,475938,476037,476153,476450,476689,476443,476355,477220,476130,476120,476311,476071,476274,475910,476263,475942,476027,476179,475454,476159,475787,476056,476354,475702,475899,475897,476436,476075,475824,476710,476187,476415,475692,475954,476923,476300,476117,476611,476384,476003,475925,475298,475739,475970,475713,476420,475981,476340,476455,476465,476433,476278,476279,475804,475588,476628,475970,476579,476226,475731,476731,476097,476375,475504,476091,476555,475813,475644,475885,476751,476496,476173,476338,475638,476077,476161,475677,476557,476452,475501,476594,475796,476190,475998,476180,476064,476186,476216,476110,476406,476165,475871,475585,475765,475742,476017,476446,476052,475829,475587,475846,476556,476087,474971,475802,475981,476170,476776,476090,476609,475735,475502,475257,476238,476308,475978,476116,476190,475509,476010,476569,475998,476695,475755,476504,476166,475504,475519,475677,475956,475707,475407,476109,476067,475506,475837,475919,476021,476304,475463,475530,476013,475722,475905,475944,476336,475959,476143,476077,476059,476061,475683,475682,476362,476552,476533,475604,475971,475917,475878,475136,475790,476184,476204,475448,475790,475819,475034,475983,475898,475910,475137,475780,475504,475664,475995,475740,475986,475758,475920,475865,476064,476260,475288,475149,475565,475519,475821,475211,475786,475894,476115,475778,475370,475274,475245,475649,476189,475533,475749,476045,475658,476061,475568,475988,475327,475772,476217,475732,475109,475869,475630,475426,475595,476010,476091,475896,474984,476154,475662,475691,476056,475445,475456,476598,476081,475418,475759,475477,475791,475573,475705,475835,475664,475767,475422,475298,475505,475734,476427,475497,475614,475626,476065,475769,475245,475594,475804,475226,475634,475315,475230,476557,476118,475734,476284,474968,475541,475174,475414,476427,475154,474935,475360,475837,475747,475824,474955,476575,475412,475485,475756,476355,475486,475404,475392,475242,474987,475308,475222,475845,475578,475052,475879,475626,475568,474568,475984,475794,475489,475563,476132,474992,475697,475318,475258,475671,476488,474909,475052,475632,475654,475675,475739,475710,475762,475103,475687,475638,475650,475186,475477,475979,475493,475413,475175,474958,475581,475766,475464,475992,476178,474785,475805,476255,474196,474955,475152,475591,475318,475648,475181,475501,475666,475203,475042,475626,475078,475846,475031,475462,476233,475585,475660,475065,475507,476123,474843,475426,475171,475148,475419,475413,475386,474809,475531,474430,476128,475198,475904,475653,474812,475444,475071,475463,475736,475807,475001,475741,474846,475567,474552,475947,475047,475318,475445,475977,475663,475215,475574,475484,475302,475289,475234,475193,475133,475664,474851,475235,474702,475188,475341,475688,475603,475411,475462,475277,476075,475006,475827,475211,475652,475125,474727,475123,475147,474706,474590,475498,475436,475546,474892,475224,475462,474850,475207,475059,475962,474839,475153,475317,475444,474583,474898,474925,475242,474571,475113,474823,475525,474945,475478,474825,474760,474512,474811,475222,475590,474918,474943,475820,475303,475419,475077,475498,475361,475554,474682,475726,475157,475294,475118,474767,475107,475339,475052,475369,474308,474770,475475,474939,475356,475029,475375,475278,474967,474783,474783,475697,475192,475211,475449,474919,475272,474895,474938,475235,475246,475132,475471,475206,475141,475295,474756,474745,475626,475272,475455,474673,475049,475015,475156,474659,475060,474189,475054,475566,474993,475162,475480,475114,475103,474833,474957,475037,475005,474901,474961,475012,475843,474667,474830,475192,474714,475258,475055,475758,475145,474213,475427,475282,475437,475013,474484,474874,475050,474177,474705,475346,475389,474763,475024,474874,475348,474874,474992,475306,474656,475077,474377,475448,475539,474889,474970,474593,474547,474223,475275,474803,475142,474494,474613,475612,475404,474111,474668,475001,474758,475494,474144,474499,474813,475085,475114,474885,474612,475130,474948,474747,474457,474499,474973,474265,474885,475243,474746,474900,474802,474702,474739,474425,474794,474920,474698,475170,475211,474897,475025,474405,475250,474688,474622,474523,474807,474198,474618,475067,474878,474379,474841,475095,474781,474399,474521,475287,474715,474608,474489,474616,474309,475152,475212,475452,474438,474719,475198,474559,474606,474573,474994,475184,474648,475037,475143,474514,474579,475020,474541,474025,474262,474627,475544,474696,474352,474794,474352,474779,473902,474876,474710,474309,474033,474265,474604,474981,474744,474952,474210,474409,474873,475507,474438,474306,475523,474049,474899,474630,474834,474484,474891,474726,474841,474675,474637,474665,474755,473985,474309,475093,474159,475125,474896,474935,474519,473932,474135,474748,475122,474895,474037,475136,474110,475047,474524,474205,474491,474463,475077,474949,474494,474716,474794,474365,474327,474600,474620,474534,474823,475258,474260,474305,474662,474627,474109,474292,474836,474481,474656,474669,474540,474997,475002,474271,474355,474144,474046,474393,474836,473777,474216,474818,474136,474653,474404,474873,474363,474644,473967,474067,474566,474269,474206,474524,474448,474898,474140,474302,474477,474388,474457,474634,475284,474104,474470,474383,474354,474432,474168,473650,474734,474300,474302,474932,473918,473298,474629,474263,474381,474672,474139,475444,473466,474367,474561,473922,474341,474330,474665,474715,473864,474911,474104,473778,475021,474107,474132,474664,475156,474252,474890,474668,474145,474084,474070,474659,473882,474232,474610,474186,474625,475236,474062,474634,474235,474072,474028,474490,474048,474330,474676,474339,474119,474571,474337,474104,473483,474533,475039,474204,473754,474424,474708,474307,473843,474581,474179,473924,473896,474176,474492,474750,473802,474013,474470,474226,473874,474687,474614,473769,474483,474982,474015,474341,474179,473830,474255,474477,474281,474303,473903,474047,474096,474627,474725,473848,473813,474434,474356,474643,474268,473898,473955,473944,474585,474704,474530,474067,473752,474522,474620,473895,473969,474788,474273,474459,474609,473667,474146,474687,473619,474568,474555,474640,473911,474441,473941,474646,473773,474078,474699,473913,473765,474224,474412,474170,474755,474146,474122,473587,473720,473747,474398,473670,473933,473926,473322,474337,473943,474407,473869,474645,474031,473710,473551,474099,474113,474333,474540,474136,474368,474728,473778,473429,474342,474167,473800,474425,473606,473994,474594,473489,474309,473468,473753,473985,473731,473975,474443,474102,473590,474357,473980,473615,474491,473856,474036,473445,474305,473665,474113,474058,473226,474286,474624,473974,473412,474492,474412,473968,473719,474019,473471,473113,473844,473923,474393,473752,473126,473434,474219,474189,473611,474017,474145,474374,473985,473762,473776,474436,473394,474089,473980,473820,474562,474196,474167,474287,473519,474004,473629,473679,474378,473925,473638,473808,473539,473482,474729,473411,473926,474457,473913,473637,474112,474390,473746,473884,473384,473148,473855,473531,473783,473672,473181,474511,473558,473641,473869,473841,473992,473874,473317,474197,473612,473609,473837,474263,473799,474062,473182,473887,473539,473789,474560,473428,473745,474630,473706,473808,473569,473713,474170,474010};
const int TN=8334;
void prepare(void){
    for(int i=1;i primes;
void sieve(int n){
    tot++;
    for(int i=2;i<=n;i++){
        if(flag[i]!=tot){
            primes.push_back(i);
            for(LL j=(LL)i*i;j<=n;j+=i){
                flag[j]=tot;
            }
        }
    }
}
int count_sieve(LL L,LL R){
    tot++;
    L=max(L,2LL);
    int ans=int(R-L)+1;
    for(int i=0;i