17岁了

上完德叔的生物课,做了两道题。

惊喜发现马上要到第二天了。

无意义地打开洛谷,水了一条动态。

噢?下一秒就是第二天了?

突然想起,第二天就是自己的生日呢。

然后无感。

然后发现,我还没怎么青春地过过就要老了。

不过早睡身体好。

CSP – S 2019游记

这是一篇流水账式游记。

主要写第二轮。

Day -1

今天巨佬搬过来和我坐了。

打了一些板子。

然后中途写题。

一道题都不会写。

wtcl。

Day 0

上午打了一点板子。学了一下单调队列优化多重背包。到现在也还没学斜率优化,如果像去年那样考个板子就很尴尬。

下午一点就出发了。

路上听了一些以前下的歌。把一直没听清楚的歌词看了一遍。忽然好喜欢你戳。

大概三点钟的时候到了神大对面的宾馆。简单收拾了东西之后写了一道博弈论的题。然而什么都没搞懂。

房间临水,水声听起来很舒服。

五点多和其他小朋友们出去吃饭。忽然想起去年的Day 0也是这个点去吃饭的呢。(我在走到图中同样的位置时截下了这张图。比去年早了8分钟)

晚饭吃的还算好,人均43.75。

拍这张图是想拿来让偷偷跑走的另外四位神犇犇嘴馋的。一时间觉得发了也没多大意思,就没发给他们了。

虽然其实写这个游记也没多大意思…

中午没睡觉,于是晚上吃饭的时候很晕很恶心,一度感觉自己不在状态。可能我需要一瓶脉动?

不在状态的时候居然被几对情侣虐了。于是在旁边的超市买了几块巧克力。

回到房间看了B站上一个关于Vae的互动视频。

于是就到现在了。现在(20:53)在补这篇游记从到达酒店开始的部分。

教练讲了一些注意事项。

希望明早的T1不要太难吧。就当成是参加了两天的面包矿泉水自助餐了。

希望明早起来就不头晕恶心了。

希望不要考我任务列表的最后这几点未完成任务。

然后用小凶凶的微博安慰一下自己。

放平静。

Day 1

晚上醒了几次,不过也还算好。有些时候晚上睡太饱会导致第二天频繁走神。

七点钟准时起了床,在宾馆旁边的店里吃了早饭。

在某谷打了卡。居然是中吉。kkk不是说一定会大吉的么?

看来特别设定的大吉都对我无效了。

wtcl。

爆零必不可免了。

忽然收到我妈微信发来的红包。原来今天是自己的农历生日呢。

半点和大佬们一起过天桥到对面的神大。不过已经来过两次了,没有很紧张。感受也和之前差不多。真的没有很紧张。

唯一的不同是,去年NOIP和今年省选不是禁止坐电梯上楼么,现在电梯居然被人占满了。

不过我依然走的楼梯。

考场在五楼。怕到时候人多,所以先在四楼上了个厕所。心里想着就算一道题都不会做也要多嫖一点考场的面包和矿泉水。怎料刚上楼面包和矿泉水就没了。

坐到位置上忽然觉得有点奇怪:这显示器为啥是正方形的?镇定一下才想起前两次来用的显示器都是正方形的。

旁边坐了一位很小很小的妹妹,应该是小学来的吧。最开始她都不知道怎么从FTP上下载试题。

我想起去年拿到压缩包的时候,我怎么输密码都解压不了。当时用普通话问了一下旁边的选手(还没到开考时间),可惜他似乎不太想理我。可能他在担心这是一种作弊行为?

这个时候我也有点犹豫,如果我就告诉她怎么下载会不会也被判为作弊?不过旁边的一位选手咳了几声,在自己的电脑上演示了一次。可惜小妹妹还是不懂。

折腾一会之后监考老师请还没看到题的选手举手。小妹妹手太短了。我跟监考老师对视了一眼,指了一下旁边的小妹妹。

那么就仁至义尽了。

这个时候我已经打开虚拟机,然后看了几眼题。

开考时间已到,监考老师开始传草稿纸。我坐在最左边,不幸的是传到最左边的草稿纸多了一张。我拿到了两张。可能是被CCF的禁赛警告搞自闭了,这个时候我心里想的全是“多拿草稿纸会不会被当成作弊然后被禁赛啊”之类的。

可惜监考老师跑后面传纸了。一直等到检查准考证我才给他说了这事。

“你拿着就是了。”

然后来说说做题。

先照例打了快读的和最值更新的函数。

T1。题面有些长,没读完的时候以为要让我生成格雷码,瞬间有些慌:T1都这么难么?

不过还是和神奇的幻方一样,题目给出了生成方法。

第一感觉是,递归下去,每次n的规模减小1不就行了。

注意到题目范围给到了2^{64}-1。嗯,不就是unsigned long long 吗,没关系。

在NOI Linux下用测评软件测试了一下自己的程序,99,OK,不用管了。

插播一下有关T1的后续:下午没事,听说牛客网可以测测。于是靠记忆敲了一次。用yms大佬给的数据才发现一个问题:我的算法用到了(1<<64)-1这个运算。虽然结果在ull内,可惜中间结果溢出了。n =64就必炸。交上去果然只有95分。

幸好原题也只有一个点满足n==64

说回考场。做完并且测完T1已经是8:55了。

然后做T2。看前两行,有点一道很经典的动态规划题(UVA1626谷 P1241 )的味道。可惜我很久没看过这道经典题了,第一次交的时候似乎也只是半懂。

不过这道题的区别在于,空串不能算作一个合法的括号串。

暂时没想到什么思路,只是隐约觉得一个位置能从前面的位置继承过来。看到有链的分,在想能不能推一个适用于链的转移方程。又想起前两天听到“大神经验分享”里,“大神”们要求无论如何都先把暴力打出来,然后再搞正解。

一时间几种选择摆在面前,还是有点慌的。但淡定了一下,决定再看看T3。然后又淡定地在虚拟机里把后面两道题的数据都配置在了Arbiter里。

这时候忽然脑海里有一个声音:这是D1啊,想想去年,应该T2是能做的吧。

于是开始专心做T2。先推了链上的情况,想到用栈来维护能和当前位置匹配的位置。既然要继承,第i个位置的答案应该用之前的答案,加上以第i个位置结尾的字串的答案。于是考虑用f[i]表示以i位置结尾能扩展多少个。然后乱糊了一通,期间前缀和乱入了,后来发现状态转移不需要前缀和,只是统计答案需要。

然后一想,既然是树形,深度优先遍历再加上回溯,不就可以让刚刚链上的方法适用了吗?

然后测了一下在Arbiter里测了一下T2,看样子应该是过了。

看了下时间,大概是10:11。

总觉得哪里不对,又反复测了一下T1和T2,然后检查文件名和输入输出。

然后就开始干T3了。

开始以为菊花图上的答案就是1,2,3, ..., n,只需要不断把当前中心的那个数字x放到编号x相同的结点上就行了。不过似乎如果x本身就在x号结点上就不行了。

于是瞎搞链,乱贪心。

最后11:49才把样例的链过了。可惜第一阶梯的数据还没打暴力。

不过也懒得打了。

又在Arbiter里测了一下程序。又检查了几次文件名。差不多就颓到12:00了。

咦,我好像还没嫖到面包和矿泉水呢。

所以Day 1预估:95+100+(0~25)。也就195~210吧。

下午和几位巨佬玩了两个小时的4399大富翁。程序写的很精致,可惜设计有些问题。因为一个人死都不能破产。这个游戏似乎可以永远进行下去。

然后和lch julao玩了十几分钟森林冰火人。这个时候教练忽然来访……

教练走后在宾馆瞎逛,又遇到教练,被教练牵桥邀请和辰星凌巨佬散步。可惜辰星凌巨佬不想。

lch julao也不想。

再然后本来约了跟几位他校julao面基,后来julao不来了。我也就自己在神大里逛了逛。

天呐,好多情侣啊,我为什么要找虐。

还在神大里再次偶遇教练了woc。

lch julao等我回房间一起点外卖。于是我就掉头回了。再不回也受不了这些恶臭的情侣们了。

路上看Q群消息,同校的其他julao们出去吃饭了。

lch julao和我点了一些外卖。等外卖的时候我和他校另外两位julao在宾馆外谈笑风生。可惜他们只知道装弱。我实在无法和他们沟通了。

忽然发现这个游记的流水账太流水了。还有些细节就不谈了吧。

22:12。今天就写到这里。

Day 2

昨晚睡觉前居然流了鼻血。

看来我必然会爆零了。

大吉。

很惊喜的是外面起了很大的雾。

上午 7:39

昨天的题把比我强一些的大佬们的分卡到和我差不多的样子了。但今天心里还是有点忐忑。

很高兴成功嫖到了场地提供的两个小面包。

和昨天完全相反。今天草稿纸传到我这里就没了。主动向监考老师要了一张。

周围没什么键盘声。我想敲,恐禁三。

于是就只是默默开了虚拟机,改了一下IDE的配色。

奶了一口今天的密码: 9Zi%Xi*DuTi! ,可惜是 抓紧时间。

非常失望。于是开始干题。

通读整个题面,T2和T3题意似乎很好懂。

但想的是T1应该能拿满吧,于是开始干T1。很可惜的是DP方程推不出来,暴力搜索打不出去。一直搞到9:40左右。开始慌了。

这个时候感觉马上要做出来了,但就是做不出来。心跳忽然加速,有一种绝望的感觉。我D2不会就这么爆零了吧。

尝试深呼吸,一度引来右边小妹妹迷惑的目光。

然并卵。

遂决定出考场走走。向老师请假上了个厕所。

回来的时候心跳差不多平静了。决定先放弃第一题。

看了下T2,打了一个n^3的暴力。在Arbiter里测试了一下,应该可以拿到\frac{9}{25}的分数。

此时大概十点多吧。

被刚刚的T1整怕了,不敢回头去做。所以开始做第三题了。

嗯,我一定不要先想正解。我一定要先打暴力。否则又会像T1那么惨不忍睹。

于是打了一下暴力。忘了打完是几点了。好像还挺早的。

又在Arbiter里测试了一下。暴力分应该稳了。

打完两道题的暴力,心情稍微好了一点。又看了一下几个特殊点,发现T3链上的情况可以O(n)做。又花了点时间打链上的分。Arbiter里测试通过。

这个时候大概是11:30。嗯,把目标定小一点就很空闲了。

这个时候心情差不多更好了,所以回头去看了第一题。最开始迟迟没把第一做出来,就是因为自己非要想把暴力优化一下。这么一想,我决定开始打 暴力。时间复杂度大概是O(m^n)吧。过了前两个样例,开心。

可惜没过第三个小样例。

这个时候,乱检查了一下,加了一个a[i][j]=0的判断,过了。但是我想,我的这个算法加不加判断都无所谓啊。

忽然发现其实是一个地方数组只开了3的大小。虽然这个复杂度只能过m=3的数据,但是后来我把整个数组下标右移了。

然后再次测了一下。T3有\frac{11}{20}的分吧。此时大概是11:55?真险。

反复在Arbiter里测试了一下三道题,非常担心这个垃圾软件因为刷新不及时迷惑我的眼睛。手动刷新了几次,应该可以确认无误了。

今天的预估分数就是:32+36+55=123.(所以应该倒序开题!)

两天一共:95+100+(0~25)+32+36+55=(318~343)=AFO。

好了。中午吃了碗兰州拉面,回房间收拾东西,坐了一会之后就上车回学校了。

下午放假。打了支疫苗。回家。

那就等分数出来了再更。(我打赌今年CCF又会在出初评成绩的时候咕咕咕几下。)

Day 3

今天教练来文化课班里说程序已经公开了,要给我们发程序。

晚上回家发现他忘了。没发。

在几个OI群里问程序,没人有。

聪明的我想到,如果有人拿到了SC源程序,应该会在洛谷的讨论区里发吧。所以就一页一页地往前翻今天的讨论,果然看到了SC的源码

重新下回来电报,然后在笔记本里解压。等等,为什么我的D1T1代码是空的?有文件没有代码这种。注意这里面的code是0字节。

我解压又删除了整整三次,都是一样的结果。

他说我刚刚修改过,但是我解压完就是这样子。真的没有修改过啊。而且只有00153和00154的代码是这样的。

我差点被吓死了。

然后非常淡定地打开台式电脑的Windows 10,传包,解压。

太好了,发现自己的代码还在。

在洛谷交了一发,居然有350分。我自己都不信。

在nowcoder交了一发,318,刚好是我自己估分的下限。(看上文,我估的分数是318~343,这25分的差距来自于D1T3链上的情况)

现在也就坐等官方数据公开了。

早睡身体好。

to be continued..

2019 12 04,下午第三节课到机房收拾东西 顺便更新:

1号晚上就查了分了,一直没更新这篇游记。318。果然AFO了。

这大概是最后一次所有人都坐满机房了吧。

大佬们还是和以前一样颓游戏,颓知乎,虐题库。

还是挺感慨的。

OI生涯总算告一段落了。

不过结束就是新的起点吧。

想起初中毕业那天上线并且在毕业晚会上放过的歌:

等到记忆只剩精华 等到笑容不掺伪装 我们相约老地方

等到人已不再奔忙 等到心也不再轻狂 我们相约老地方

THE END

题解 UVA11361 【Investigating Div-Sum Property】

数位DP,对于每一个询问,回答为ask(B)-ask(A-1).

我主要想分享一下一些实现上的细节。但还是先说一下思路,这里借鉴了《算法竞赛入门经典:训练指南》的讲解。

f(w,m_1,m_2)表示有w位数(可以有前导0)需要确定,需要让各位数字之和除以K的余数为m_1,需要让这w位数组成的数字除以K的余数为m_2需要的方案数。然后我们一步一步确定前面几位数,加起来得到答案。

显然,我们可以从09枚举最高位上的数字head,从而有:

f(w,m_1,m_2)=\sum f(w-1,(m_1 - head)mod \, K,(m_2 - 10^{w-1}head)mod \,K).

边界:f(0,0,0)=1f(0,m_1 ≠0,m_2≠ 0)=0.

理解:要让w位数各个位之和mod \, Km_1,且第一位为head,那么肯定需要没有head的时候mod \, K的值为为(m_1-head)mod \, K。第三个参数亦然。

几个细节:

1.记忆化搜索,那么时间复杂度为O(ws* K^2).可是K这么大怎么办?

如果ask(val)valws位数,但是K > 9* ws,显然没有合法的数字。因为所有位加起来都没有K那么大,肯定加起来之后不能整除K.

所以题中数据范围给那么大是没用的…..

于是可以用数组来记搜,数字最多十位数,所以K>9 * 10 =90时肯定是无解的。数组可以开得下。

2. val=0时答案为1不为0

3.可以先让val=val+1,然后紧贴val求解答案,需要同时记录已经有的各位数字之和和总的数字之和。

还有一些细节见代码:

#include<cmath>
#include<cstdio>
#include<cstring>
template<typename T>
inline bool read(T &x){
    x=0;char c;T  f=1;
    do{c=getchar();if(c=='-')f=-1;else if(c==EOF)return false;}while(c>'9'||c<'0');
    do{x=x*10+c-'0';c=getchar();}while(c>='0'&&c<='9');
    return x*=f,true;
}
long long A,B,K;
long long tp[20];//tp[i]表示10 的i次方
long long Div[20];
long long d[20][200][200];

#define res1 (d[w][m1][m2])
long long f(int w,int m1,int m2){
    if(w==0){
        return m1==0&&m2==0;
    }
    if(~d[w][m1][m2])return d[w][m1][m2];
    res1=0;
    for(register int  i=0;i<=9;++i){
        //i即为前所述的head 即最高位的数字
        res1+=f(w-1,(m1-i%K+K)%K,(m2-(1ll*tp[w-1]*i%K)+K)%K);
        //必须保证mod K之前为非负数 所以加上一个K 
    }
    return res1;
}
long long Getws(long long val){//分割这个数,并且返回它的位数

    if(!val){//其实这步可以不要。毕竟在GetAns()的入口处特判了0的情况
        return Div[0]=(Div[1]=0)+1;
    }
    Div[0]=0;
    while(val){
        Div[++Div[0]]=val%10;
        val/=10;
    }
    return  Div[0];
}
long long GetAns(long long val){
    if(!val)return 1ll;
    long long res=0;
    ++val;
    //紧贴val来计算答案,如果不加1会漏掉val这个数
    //当然也可以不加1,最后特判val这个数
    long long ws=Getws(val);
    if(ws*9<K)return 1ll;
    long long presum=0,presum2=0;
    //presum:当前累计的各位数字之和 如322的presum=3+2+2=7
    //presum2:当前已确定数字组成的数:如32***的presum2=32000.
    for(register int  i=ws;i>=1;--i){
        for(register int  j=0;j<Div[i];++j){
            if(j)presum+=1;presum%=K;
            if(j)presum2+=tp[i-1];presum2%=K;
            //presum,presum2每步取模更方便
            res+=f(i-1,(K-presum+K)%K,(K-presum2+K)%K);
            //此处有减法,必须保证它是非负数
        }
        //紧贴val来取值,则最高一位没有被讨论到
        //例如,如果val=32565
        //如果已经枚举到第二位
        //那么实际上我们暂时只会先考虑30***和31***的情况
        //但在后面的讨论中,应保证第二位为2
        //所以还要把2的贡献累加进去
        if(Div[i]){
            ++presum;
            presum2+=tp[i-1];
        }
    }
    return res;
}
void  work(){
    // GetAdd();
    long long ans=GetAns(B)-GetAns(A-1);
    printf("%lld\n",ans);
}
int main(){
    //freopen("testin.txt","r",stdin);
    //freopen("testout.txt","w",stdout);
    tp[0]=1;
    for(register int  i=1;i<=15;++i){
        tp[i]=10ll*tp[i-1];
    }
    long long T;
    read(T);
    while(T--){
        read(A);
        read(B);
        read(K);
        memset(d,-1,sizeof(d));
        work();
    }

    return 0;
}

题解 UVA1073 【Glenbow Museum】

如果有一个点能看到各个顶点,那么这个点的上下左右一定要对应四个RR

如果有OO,那么这两个270°的角延伸出去的角的可视范围没有交集,即它们不能被同时被看到(点A能看到点B,那么点B也能看到点A。反之B一定不能看到点A),如下图所示:(延伸出去的角可能是R也可能是O,这里以R为例)

所以一定不能有OO

如果没有OO,但是有OR。那么OR前面一个字符一定是R。(否则就有OO了)。这O,R两个角的可视范围是有交集的。如下图所示:

同样地,相邻的RR两角的可视范围也是有交集的。至少它们两个角是可以被同时看到的。

如果一个点能看到所有内角,那么它的正对的上下左右一定都是RR。因为如果某个方向是RR,显然成立。如果某个方向上的角度序列有OR,那么这个方向的角度序列只能是OROROR…ORR。即只能以RR结尾。(如果一直不结尾,那就不构成多边形。如果以OO结尾,那么不合法)。

既然以RR结尾,那么能同时看到这个RR的点一定在如图所示的灰色区域。

反过来说,一个点的正对的上下左右四个方向一定是RR

稍加思考可以发现,只要满足上下左右四个方法有RR,且整个序列没有OO,那么一定满足条件。(没有OO意味着不会往外拐)

L个内角代表L条边,根据多边形内角和公式:
90R+270O=(L-2)* 180.

又因为R+O=L.

所以有R=(L+4)/2,O=(L-4)/2.

所以我们要求的就是(L+4)/2R(L-4)/2R的字符串中,有至少四个RR且没有OO的个数。注意L<4或者L为奇数时无解。(为奇数时的内角和不为180°的整数倍)

前两个实现方法参考《算法竞赛入门经典:训练指南》:

方法一:

f(i,j,b,e)表示有iRjO,开头为b0表示R1表示O),结尾为e

f(x,0,0,0)=f(0,1,1,1)=1,x > 0.

f(i,j,b,0)=f(i-1,j,b,1)+f(i-1,j,b,0).

f(i,j,b,1)=f(i,j-1,b,0).(不能出现OO

答案就很显然了(把几个f(i,j,b,e)加起来),你可以自行推一推或者见代码。

递归加上记忆化即可O(n)解决。(直接递推则需O(n^2)

代码:

#include<cstdio>
#include<cstring>
int L,kase;
long long d[520][520][2][2];
long long f(int i,int j,int b,int e){
    if(~d[i][j][b][e]){
        return d[i][j][b][e];
    }
    if(!j){
        return i&&!b&&!e;
    }
    if(!i){
        return j==1&&b==1&&e==1;
    }
    if(e){
        return d[i][j][b][e]=f(i,j-1,b,0);
    }
    else{
        return d[i][j][b][e]=f(i-1,j,b,0)+f(i-1,j,b,1);
    }
}
int main(){
    memset(d,-1,sizeof(d));
    long long ans;
    while(~scanf("%d",&L)&&L){
        ans=0;
        if(!(L&1||L<4)){
            ans+=f((L+4)/2,(L-4)/2,0,0);
            ans+=f((L+4)/2,(L-4)/2,1,0);
            ans+=f((L+4)/2,(L-4)/2,0,1);
        }
        printf("Case %d: %lld\n",++kase,ans);
    }
    return 0;
}

方法二:

d(i,j,k)表示以k开头,有iR,有j对相邻的RRRR算两对,ROR0对),且以R结尾的方案数。

d(1,0,0)=d(1,0,1)=1.

其余d(i,j,k)=d(i-1,j,k)+d(i-1,j-1,k).表示当前字符串可由某个R结尾的字符加上ORR来得到。

A=(L+4)/2

答案是d(A,4,1)+d(A,3,0)+d(A,4,0).

第一项表示O开头R结尾。

第二项表示R开头R结尾。求的是字符串中只有3RR。但是把开头和结尾这一对算上就有4对了。

第三项很难理解,它表示R开头O结尾。每一个R开头O结尾的合法字符串都对应一个把最后一个O去掉之后的,R开头R结尾的字符串。因为最后一个字符是O,不能和前面的R接在一起,所以需要保证前面就有4R

也就是说把4RR对的R开头R结尾的字符串后面加上一个O就可以得到4RR对的R开头O结尾的字符串。

代码:

#include<cstdio>
#include<cstring>
int L,kase;
long long d[520][520][2];
long long f(int i,int j,int k){
    if(i==1){
        return !j;
    }
    if(~d[i][j][k])return d[i][j][k];
    return d[i][j][k]=f(i-1,j,k)+f(i-1,j-1,k);
}
int main(){
    memset(d,-1,sizeof(d));
    while(~scanf("%d",&L)&&L){
        if(L&1||L<4){
            printf("Case %d: 0\n",++kase);
            continue;
        }
        printf("Case %d: %lld\n",++kase,
            f((L+4)/2,3,0)+//R...R
            f((L+4)/2,4,1)+//O...R
            f((L+4)/2,4,0)  //R...O
        );
    }
    return 0;
}

方法三:(参考了KobeDuu的博客

组合计数。

其实可以发现,只要有A=(L+4)/2RB=(L-4)/2O(其实B=A-4),并且OO不相连,那么一定可以保证有4个RR对。

可以这样想:把A \ge 4R连成一个环,那么有ARR对。

再把B=A-4O插入,每插入一个O,就会少一个RR对。

所以最后剩下A-B=4RR对。刚好满足条件。

所以可以这样利用组合数算,把所有RR排成一行之后:

1.在开头放O

那么,最后一个位置不能放O。剩下A-1个位置可以放,要放下B-1O

计数C_{A-1}^{B-1}

2.不在开头放O

那么剩下A个位置可以放BO
计数C_{A}^{B}.

所以答案为C_{A-1}^{B-1}+C_{A}^{B}.

代码太简单就略了吧。

祝AC。

题解 UVA11806 【Cheerleaders】

以下内容中C_{n}^{m}表示组合数。

考虑四角上四个点的情况:

1.四个角都不放人。

显然需要枚举最外圈(第一行、最后一行、第一列、最后一列的并集)除开四个角之外的放置方案。

设第一列、最后一列、第一行、最后一行中除开第一个位置和最后一个位置分别放置j_1,j_2,k_1,k_2个人,那么它们分别有:C_{n-2} ^{j_1},C_{n-2}^{j_2}, C_{m-2}^{k_1},C_{m-2}^{k_2}种放置方法。(需要保证1 \leq j_1,j_2,k_1,k_2 <kj_1+j_2+k_1+k_2 \leq k)

除开最外圈,里面还剩下left=k-(j_1+j_2+k_1+k_2)个人,需要把他们放置在中间共(m-2) (n-2) 个位置上。有C_{(m-2)  (n-2)}^{left} 种方法。

所以一共有( \sum C_{n-2}^{j_1} C_{n-2}^{j_2} C_{m-2}^{k_1} C_{m-2}^{k_2})  C_{(m-2)  (n-2)}^{left}种方案。

(也就是说要枚举j_1,j_2,k_1,k_2)

2.仅一个角放人。 那么又有四种情况:左上、左下、右上、右下。显然这四种是等价的,求一种之后乘以4即为答案。

为了方便讲述,假设选择了左上的那一个角。

那么第一行、第一列都不需要找了。为了使方案合法,我们需要一种方案,使得最后一行、最后一列都有人。

因为左下、右上、右下都不放人,所以最后一列n-2个位置中至少要选择一个人,最后一行m-2个位置中要选择至少一个人。

假设最后一列放j_1个人,最后一行放k_1个人,那么方案数为C_{n-2}^{j_1}  C_{m-2}^{k_1}.

除去左上角一个点、最后一整列、最后一整行,还剩下(m-1)  (n-1)-1个点可以放人,还剩下k-j_1-k_1-1个人需要放。

于是放这剩下的k-j_1-k_1-1个人就有C_{(m-1) (n-1)-1}^{k-j_1-k_1-1}种方法。

于是这种情况下有(\sum C_{n-2}^{j_1}  C_{m-2}^{k_1}) C_{(m-1)  (n-1)-1} ^ { k-j_1-k_1-1}种方法。

3.有且只有两个角放人。

假设这两个人不在同一对角线上

那么只有在n>2时才能在左上左下、右上右下放置。只有在m>2时才能在左上右上、左下右下放置。(否则若要满足情况,则不止要放2个角)。

假设n>2且在左上左下(或者右上右下)放置,那么只有最后一列(或者第一列)没有被覆盖了。我们需要在最后一列(或者第一列)的n-2个位置上选出至少一个人来参与。设选择j人,那么方案数为C_{n-2}^{j}

还剩下left=k-2-j个人,放置在nm-2-n个位置。

方案数为(\sum C_{n-2}^{j})  C_{n  m-2-n}^{left}
由于可以选左上左下或者右上右下,所以需要把这个玩意乘以2

同理,如果m>2且选择左上右上(或者左下右下),给最后一行(或者第一行)放置j个人,那么方案数共为:(\sum C_{m-2}^{j})  C_{n  m-2-m}^{left}。同样需要计数时乘以2

假设在同一对角线上:

除了四个角,每个位置都可以放置,方案数为C_{n m-4}^{k-2}。在对角线上有两种情况(左上右下,左下右上),所以这个数也要乘以2

4.有且只有三个角放人。

那么无论怎么放,都是满足条件的。
4个点中选出3个有C_{4}^{3}种方法,除开四角有C_{n  m - 4}^{k-3}种方法。

所以计数:C_{4}^{3}C_{nm-4}^{k-3}

5.所有角都放人。

那么所有角都放人有一种方法,除开这四个角共有C_{n  m -4}^{k-4}种方法,所以计数C_{nm-4}^{k-4}

当然要记得每步取模。

代码:

#include<cstdio>
#include<cstring>
// #define LOC

const long long mod=1000007;
long long C[505][505];
long long n,m,k;
long long ans;
long long T;
int kase;
void init(){
    C[0][0]=1;
    for(register int i=1;i<=500;++i){
        C[i][0]=1;
        for(register int j=1;j<=i;++j){
            C[i][j]=C[i-1][j-1]+C[i-1][j];
            C[i][j]%=mod;
            // printf("C[%d][%d]=%lld\n",i,j,C[i][j]);
        }
    }
}

void work(){
    scanf("%lld%lld%lld",&n,&m,&k);
    ans=0;
    if(m*n>=k){
        {//四个角都不放人
            for(register int j1=1;j1<=n-2;++j1){
                if(j1>=k)continue;
                for(register int j2=1;j2<=n-2;++j2){
                    if(j1+j2>=k)continue;
                    for(register int k1=1;k1<=m-2;++k1){
                        if(j1+j2+k1>=k)continue;
                        for(register int k2=1;k2<=m-2;++k2){
                            if(j1+j2+k1+k2>k)continue;
                            ans+=C[n-2][j1]*C[n-2][j2]%mod*C[m-2][k1]%mod*C[m-2][k2]%mod*C[(m-2)*(n-2)][k-(j1+j2+k1+k2)]%mod;
                            ans%=mod;
                        }
                    }
                }
            }
            ans%=mod;
        }

        {// 一个角上放人
            for(register int j1=1;j1<=n-2&&j1<k;++j1){
                for(register int k1=1;k1<=m-2;++k1){
                    if(j1+k1+1>k)continue;
                    ans+=C[n-2][j1]*C[m-2][k1]%mod*C[(m-1)*(n-1)-1][k-1-j1-k1]%mod*4%mod;
                    ans%=mod;
                }
            }
            ans%=mod;
        }

        {//左上左下或者右上右下放置
            for(register int j=1;j<=n-2&&j<=k-2;++j){
                ans+=C[n-2][j]*C[m*n-n-2][k-2-j]%mod*2%mod;
                ans%=mod;
            }
            ans%=mod;
        }

        {//左上右上或者左下右下放置
            for(register int j=1;j<=m-2&&j<=k-2;++j){
                ans+=C[m-2][j]*C[m*n-m-2][k-2-j]%mod*2%mod;
                ans%=mod;
            }
            ans%=mod;
        }


        if(k>=2){//对角线上放置
            ans+=2*C[m*n-4][k-2];
            ans%=mod;
        }

        if(k>=3){//三个角都放
            ans+=C[4][3]*C[m*n-4][k-3]%mod;
            ans%=mod;
        }

        if(k>=4){//四个角都放
            ans+=C[m*n-4][k-4];
            ans%=mod;
        }
    }
    printf("Case %d: %lld\n",++kase,ans);
}
int main(){
    scanf("%lld",&T);
    init();
    while(T--){
        work();
    }
    return 0;
}

[SDOI2015]寻宝游戏 题解

自己搞出来一种树状数组+倍增的做法,A掉之后发现网上的题解都是平衡树。心里还是有点美滋滋。

于是决定分享出来。(其实只是想找个借口颓废一下)

不过其实非常简单,耐心读一读就懂了。

在阅读实现部分之前,请不要考虑“这个操作怎么实现呢?”“时间复杂度会不会过高?”这类的问题。否则很可能你会很快放弃阅读。先理解这种做法的流程即可。(可以先剧透一下:时间复杂度大约是O(m\,log^2n)

题意分析

分析一下题意,其实就是给定一棵树,在这棵树上选择某几个节点(设这几个节点的集合为S),求从其中的某个节点出发,经过所有被选择的节点后再回到出发点的最短路径长度。

从起点到终点,和从终点到起点的路径长度L是一样的,仅仅是沿原路返回而已。

也就是说,我们要求的即是将所有S中的节点连接起来的路径长度的二倍,即2L

下两图分别是S={3,4,6}时的路径和S={2,3}时的路径,请自行理解,我就不再赘述。

(在机房只能用Windows 7的画图工具,只能说还算能看吧)

那么,我们可以求出把选择的所有节点连接起来的最短路径,然后输出它的二倍。

于是题目就变成了,动态维护使树上某些节点连通的最短路径长度,并且在每一次修改操作完成后输出这个长度的二倍。

解决方案

题目中有两种操作,增加选择的节点和删除选择的节点。

假设要处理的节点为u,我们先考虑将向S中增加u的情况。删除u的情况是可以建立在增加u的情况之上的:令S'=S-{u},在S中删除u的花费就是在S'中增加u的花费——他们是前后两种路径长度的差。

现在考虑增加u时的情况。

情况1.|S|=0,即S中还没有任何节点。向其中加入u也不会产生任何长度。因此可以不修改答案。

情况2.在原图中,u至少有两个子节点(设其中一个为v) ,满足以v为根节点的子树中有节点属于S

于是u是属于S的2个(或更多)点的LCA,使他们连通则必须经过u。那么,在加入u之前,使节点连通的路径就已经经过了u,因此可以不修改答案。

如下图所示,4的两个子节点5,8的子树中都至少有一个节点在S中,在加入4之前,连通S中节点的路径就已经经过了4。即加入4也不会对答案造成影响。

情况3.在原图中,以u为根的子树中有节点属于S,并且以u为根的子树外也有节点属于S

那么同上,在加入u之前,使节点连通的路径已经经过了u。换句话说,u的加入不会对路径长度造成影响,因此不需要修改答案。

如图所示,假如要加入5,在加入5之前已有4,7 \in S,连接4,7的路已经覆盖了5,因此加入5不会使答案改变。

情况4.不满足上述三种情况中的任何一个。

那么我们需要找到一个在原路径上的点v,满足dist(u,v)最小。并且使答案加上dist(u,v)

寻找v的方法是,从u开始向上倍增,找到离u最近的,且子树中有节点属于S的点。设这个点为y

那么:

a.假如y在原有路径上,即加入u之前,y就被使节点连通的路径覆盖。也就是说,y满足情况2或情况3。

此时v=y

那么只需要让答案加上dist(u,y).

即,如下图所示:

u=9,S={3,4,7}4u 能到达的 最近的 子树中有节点在S中的 点。

那么只需要将94连接起来即可。

b.假如y不在原有路径上,那么以y的子树外一定没有节点在S中。(否则满足情况3,原有路径一定经过y

也就是说,S中的点全部都在以y为根的子树中。

我们只需要在这当中选择一个离u最近的点,将它与u连起来即可。

如下图所示:

那如何寻找离u最近的v呢?(请先往上翻,确认自己已知悉u,y,v的含义后再继续阅读)

dist(v,u)=dist(v,y)+dist(y,u)可知,无论选择哪个点,都有一段dist(y,u),而这段距离是已固定的。(当前只有v不确定)

所以我们要找的其实是dist(v,y)最小的点。

由于yv的父节点,所以有:

dist(root,v)=dist(root,y)+dist(v,y)

dist(root,y)是恒定的。

所以我们要找的就是dist(root,v)最小的点。

于是可以先处理出每个点到根节点(任选一个即可)的距离。

以上的讨论就包含所有的情况了。

代码实现

上述流程有几个需要高效算法维护的内容:

1.节点x的子树中有多少节点属于S

2.离节点x最近的 子树中有节点属于S的 点;

3.树上任意两点间的距离;

4.已经被路径覆盖的点中,距离根最近的点。

由于要维护子树中的信息,很自然地想到用DFS序。设In(x)表示深度优先搜索时,x是第几个被遍历到的。Out(x)表示从x往上回溯时,已经遍历了多少的点。

x的子树中的点就是DFS序在[In(x),Out(x)]中间的点。

当我们要将y加入到s中时,令FT[In(y)]=1。那么\sum_{i=In(x)}^{Out(x)}FT[i]就是以x为根的子树中在S中的个数。

用树状数组维护即可。

于是1就解决了。单次操作O(log\,n)

树上x,y之间的距离等于dist(root,x)+dist(root,y)-2*dist(root,LCA(x,y)),于是用LCA维护即可。巧了,我们本来就要维护每个节点的dist(root,x)啊,一举两得。

于是问题3解决。单次操作O(log\, n)

由于只要x的子树中有节点属于S,那么x的父节点(或者父节点的父节点,等等)中也一定有节点属于S。换句话说,”子树中是否有节点属于S“ 这一属性具有单调性。

于是可以用倍增的方法。每次向上倍增某个节点的2^k个祖先,找到最近的即可。

(又巧了,倍增LCA不正好维护了每个节点的2^k倍祖先么?)

于是问题2可在log^2n内解决。

最巧的是问题4。 由于树的形态确定后,每个点xdist(root,x)都是不变的,所以可以考虑小根堆维护。

但是,是不是我们要把路径上所有的点(包括没在S中的点)都加入小根堆?如果是,那么每次需要O(n\,logn)的时间来找出路径上的点并将其加入小根堆中。这显然是不可接受的。

重新考虑之前讨论的4种加入点的情况。除了在S中的点,我们只需要将距离根最近的点加入小根堆即可。

例如,在情况1(|S|=0 )中,我们将这唯一添加进去的点加入小根堆即可。

在情况2(有至少两个子树中有点属于S)中,我们将正在处理的u(即图中的4)加入小根堆即可。它就是最近的,最有可能被选中的点。

假如4在后面被删掉了怎么办?会不会遗漏5,8这种候选项?

不会。

假如4被删掉,我们先不在小根堆中删除4,而是在取用它的时候判断它是否在路径上。只要它在路径上(满足情况2或3或者本身就是S中的点),就直接取用,否则将它弹出,考虑下一个候选项。

如果4被弹出,那么除非有其它操作使得58在路径上,否则候选项肯定不可能是58

而当其它操作使得58在路径上并且可能成为备选点时,我们会将58加入小根堆,所以不会遗漏。

类似地,在情况3下,将要处理的点(图中的9)加入小根堆即可。

在情况4下,将倍增找到的点和正处理的点加入小根堆即可。

其实我们发现,除了要向上倍增的情况,所有情况都要将要处理的点加入小根堆中。

#include<cmath>
#include<queue>
#include<cstdio>
#include<cstring>

//#define LOC
#define nowy (L[i].to)
using std::queue;
using std::priority_queue;
template <typename T>
inline void read(T &x){
    x=0;char c; T f=1;
    do{c=getchar();if(c=='-')f=-1;}while(c>'9'||c<'0');
    do{x=x*10+c-'0';c=getchar();}while(c>='0'&&c<='9');x*=f;
}

const int N=1e5 + 10;

int n,m,t;
int h[N],tot=1;
int f[N][18];
int d[N];
long long len[N];
int bg[N],ed[N];
int Inq[N];
int DFN;
int TotIn;
int Diff[N];//Diff是FT的一个拷贝 便于直接确认一个点是否在S中
int x,y,z;
int Num_SonIn,Cls_F;
long long ans=0;

struct line{
    int to,nxt,w;
}L[2*N];

struct OneNode{
    int num;
    bool operator <(const OneNode b)const {
        if(len[num]==len[b.num])return d[num]>d[b.num];
        return len[num]>len[b.num];
    }
    OneNode(int x):num(x){}
};//通过便于维护小根堆
struct FenwickTree{
    int v[N];
    inline void clear(){
        memset(v,0,sizeof(v));
    }
    inline void add(int x,int y){
        for(;x<=n;x+=x&-x){
            v[x]+=y;
        }
    }
    inline int ask(int x){
        int res=0;
        while(x>0){
            res+=v[x];
            x-=x&-x;
        }
        return res;
    }
    FenwickTree(){clear();}
}FT;
priority_queue<OneNode> OQ;

inline void add(int x,int y,int z){
    L[++tot].to=y;L[tot].nxt=h[x];h[x]=tot;L[tot].w=z;
    L[++tot].to=x;L[tot].nxt=h[y];h[y]=tot;L[tot].w=z;
}

void GetLCA_DFS(int x){
//DFS 同时求出祖先数组、距离根节点的距离、DFS序
    bg[x]=++DFN;
    for(int i=h[x];i;i=L[i].nxt){
        if(d[nowy])continue;
        d[nowy]=d[x]+1;
        f[nowy][0]=x;
        len[nowy]=len[x]+L[i].w;
        for(int j=1;j<=t;++j){
            f[nowy][j]=f[f[nowy][j-1]][j-1];
        }
        GetLCA_DFS(nowy);
    }
    ed[x]=DFN;
}
inline int LCA(int x,int y){
    if(d[x]>d[y]){
        x^=y;y^=x;x^=y;
    }
    //d[x]<=d[y]
    for(register int i=t;i>=0;--i){
        if(d[f[y][i]]>=d[x]){
            y=f[y][i];
        }
    }
    if(x==y)return x;
    for(register int i=t;i>=0;--i){
        if(f[y][i]!=f[x][i]){
            y=f[y][i];
            x=f[x][i];
        }
    }
    return f[x][0];
}
inline long long LEN(int x,int y){
    return 1ll*len[x]+len[y]-2*len[LCA(x,y)];
}
inline int GetSonIn(int x){//including x
//判断x的子树中有多少节点属于S
    if(!x)return TotIn;
    int Num=FT.ask(ed[x])-FT.ask(bg[x]-1);
    return Num;
}
inline bool TwoSon(int x,int v){
//是否满足情况2
    int SonV;
    for(register int i=h[x];i;i=L[i].nxt){
        if(d[nowy]<=d[x])continue;
        SonV=GetSonIn(nowy);

        if(SonV){
            if(SonV==v)return false;
            return true;
        }
    }
    return false;
}
inline bool check(int x){
//是否满足情况2或3 这两种情况可以一同处理
    if(!x)return true;
    int Num_SonIn;
    return (Num_SonIn=GetSonIn(x))&&(Num_SonIn<TotIn||TwoSon(x,Num_SonIn));
}
inline int GetCls_F(int x){
//倍增求离自己最近的 子树里有节点属于S 的节点
    if(GetSonIn(x))return x;
    int Num;
    for(register int i=t;i>=0;--i){
        if(!(Num=GetSonIn(f[x][i]))){
            x=f[x][i];
        }
    }
    return f[x][0];
}
inline void Change(long long t){
//通过t变量实现增加删除在同一个函数处理 减少码量
    if(TotIn!=0){
        if(!check(x)){
            Cls_F=GetCls_F(x);
            if(check(Cls_F)){
                if(t&&!Inq[Cls_F]){OQ.push(OneNode(Cls_F));Inq[Cls_F]=1;}
                    ans+=LEN(x,Cls_F)*(-1+2*t);
            }
            else {
                while(!OQ.empty()){
                    z=OQ.top().num;
                    if(check(z)||Diff[z])break;
                    OQ.pop();
                    Inq[z]=0;
                }
                if(t&&!Inq[Cls_F]){OQ.push(OneNode(Cls_F));Inq[Cls_F]=1;}
                ans+=LEN(x,z)*(-1+2*t);
            }
        }
    }
}
int main(){
    read(n);read(m);
    t=log(n)/log(2)+1;
    for(register int i=1;i<n;++i){
        read(x);
        read(y);
        read(z);
        add(x,y,z);
    }
    d[1]=1;
    GetLCA_DFS(1);
    for(register int i=1;i<=m;++i){
        read(x);
        if(!Diff[x]){
            Change(1);
            FT.add(bg[x],1);
            Diff[x]+=1;
            if(!Inq[x]){Inq[x]=1;OQ.push(OneNode(x));}
            ++TotIn;
        }
        else{
            --TotIn;
            FT.add(bg[x],-1);
            Diff[x]-=1;

            Change(0);
        }
        printf("%lld\n",ans*2);
    }
    return 0;
}

然后就可以愉快地AC了。

Uae牛逼!

几道水题的题解

这篇文章包含了这几道简单题的题解:

逆序排列

给出2个数nk,求1~n的全排列中,逆序数为k的排列有多少种。每个测试点包含T组数据。

1 \leq T \leq 10000, 2 \leq n \leq 1000, 0 \leq k \leq 20000

1n的全排列有n!个,每个测试点的数据组数很多。考虑动态规划。

1296 有限制的排列 一样,假如以“当前考虑到1N的全排列的第i位,且逆序对数为j的排列个数”来定义状态d[i][j],必然会困于如何去重。即使找到去除重复数字的方法,也会导致时间复杂度偏高。

因此我们这样简化状态:定义d[i][j]1i的全排列中,逆序对数为j的排列数。可以发现d[n][j]仍然包含了所需要的状态。

如何由1(i-1)的全排列转移到1i的全排列?怎么保证没有重复的数字?假如新排列第i位是j,这些新排列和1(i-1)的全排列的关系是什么?

借鉴 1296 有限制的排列 的思想(这两道题的在思想上很相像),我们可以把每一个1(i-1)的全排列通过以下方式变成一个长度为i,且最后一位为j的全排列:

  1. 将原排列中,大于等于j的数加上1;
  2. 在最后添上j

可以发现每个1(i-1)的全排列都可以转化为各不相同的长度为i,且最后一位为j的全排列 。(从数学上理解,最后一位确定,前i-1位的排列数为(i-1)!,也就是1(i-1)的全排列个数。)

在理解上述内容的基础上,我们可以得到状态转移方程:

d[i][j]=\sum_{k=1}^i d[i-1][j-(i-1-k+1)] = \sum_{k=1}^i d[i-1][j-(i-k)]

在给第i位填上k后,前面大于ki-k个数就会和k构成逆序对。因此需要满足在转移之前有j-(i-k)个逆序对。注意,这里计算的大于k的个数,是指新排列中大于k的个数。即在长度为i-1的原排列中大于等于k的个数。

由于频繁求区间和,可以考虑维护前缀和。长度为i的全排列的状态只与长度为i-1的全排列的状态有关,所以考虑滚动数组。

时间复杂度O(nk+TlogT)

代码如下:

#include<cstdio>
#include<algorithm>
#include<cstring>
using std::sort;
const long long maxn=1000,mod=1e9 + 7;
long long n,k,done=1;
long long ans[10*maxn+5];
long long sum[2][20005];
struct qst{
long long n,k,id;
}Q[maxn*10+5];
inline void read(long long &x){
x=0;char c;long long f=1;
do{
c=getchar();if(c=='-')f=-1;
}
while(c>'9'||c<'0');
do{
x=x*10+c-'0';c=getchar();
}
while(c>='0'&&c<='9');
x*=f;
}
inline long long max(long long a,long long b){
return a>b?a:b;
}
long long d[2][20005];
void work(){
d[0][0]=1;
sum[0][0]=1;
for(register int i=1;i<=k;++i){
    sum[0][i]=1;
}
for(register long long i=1;i<=n;++i){
for(register long long nk=0;nk<=k;++nk){
d[i&1][nk]=0;
d[i&1][nk]=(sum[(i-1)&1][nk]-(nk-i>=0?sum[(i-1)&1][nk-i]:0)+mod)%mod;
if(i==Q[done].n&&nk==Q[done].k){
ans[Q[done++].id]=d[i&1][nk];
}
sum[i&1][nk]=((nk?sum[i&1][nk-1]:0)+d[i&1][nk])%mod;
}
}
}
inline bool cmp(qst a,qst b){
if(a.n!=b.n)return a.n<b.n;
return a.k<b.k;
}
int main(){
long long T;
read(T);
for(register long long i=1;i<=T;++i){
read(Q[i].n);
read(Q[i].k);
n=max(n,Q[i].n);
k=max(k,Q[i].k);
Q[i].id=i;
}
sort(Q+1,Q+1+T,cmp);
work();
for(register long long i=1;i<=T;++i){
printf("%lld\n",ans[i]);
}
return 0;
}

最长递增路径

一个无向图,可能有自环,有重边,每条边有一个边权。你可以从任何点出发,任何点结束,可以经过同一个点任意次。但是不能经过同一条边2次,并且你走过的路必须满足所有边的权值严格单调递增,求最长能经过多少条边。

1 \leq N \leq 50000, 0 \leq M \leq 50000, 0 \leq W \leq 10^9

有点像最长上升子序列,只不过是在图上。

考虑将每条无向边拆成两条有向边,按照边的大小排序,由于一条路径走过后不能再走,所以没有后效性。

每次从边a转移到边b,需要满足两个条件:

  1. a的终点是b的起点。
  2. a的长度必须严格小于b的。

考虑用数组maxb[]保存每个节点作为终点的,已经走过的最长的边数。那么通过某条边从一个点u走向另一个点v时,可以用maxb[u]+1来更新maxb[v]。为了满足第二点,我们可以以边长为标准分段,将某几条长度相同的边处理完之后,再一起更新这些边更新过的maxb[]

时间复杂度O(mlogm)

代码:

#include<cstdio>
#include<algorithm>
#include<cstring>
using std::sort;
const int maxn=5e4;
struct line{
int u,v,w;
}l[maxn*2+5];
int ans;
int d[maxn*2+5],maxb[maxn+5];
inline void read(int &x){
x=0;char c;int f=1;
do{c=getchar();if(c=='-')f=-1;}while(c>'9'||c<'0');
do{x=x*10+c-'0';c=getchar();}while(c>='0'&&c<='9');x*=f;
}
inline bool cmp(line a,line b){
return a.w<b.w;
}
int n,m;

int main(){
read(n);read(m);
for(register int i=1;i<=m;++i){
read(l[i].u);read(l[i].v);read(l[i].w);
l[i+m].w=l[i].w;
l[i+m].u=l[i].v;
l[i+m].v=l[i].u;
}
sort(l+1,l+1+2*m,cmp);
int lst=1;
for(register int i=1;i<=2*m;++i){
if(l[i].w!=l[lst].w){
for(register int j=lst;j<i;++j){
maxb[l[j].v]=std::max(maxb[l[j].v],d[j]);
}
lst=i;
}
d[i]=maxb[l[i].u]+1;
if(d[i]>ans)ans=d[i];
}
printf("%d\n",ans);
return 0;
}

选数字

当给定一个序列a[0],a[1],a[2],…,a[n-1] 和一个整数K时,我们想找出,有多少子序列满足这么一个条件:把当前子序列里面的所有元素乘起来恰好等于K。 每个测试点包含不超过20组数据,1 \leq n \leq1000,2 \leq K \leq 100000000

很显然是一道动态规划题。

读入一个数字,就可以用它 与 前面的数字能构成的数 来构成新的数(或者给已有的数增加方案数)。这算是最普通的做法。

给出一种优化:

  1. 读入a[i]时,假如k \bmod a[i]\ne0,则直接忽略,读入下一个数字。
  2. a[i]与之前已经生成的某个数x构成新的数时,若k \bmod (x*a[i])\ne0则跳过。

这样我们就可以保证,所有存入的数都是尽可能对答案有帮助的。因为假如一个数不能整除k,必然不可能对答案造成影响。

a[i]与已有的数来更新新的数时,应该将所有的修改都保存起来,等到更新完了之后再应用更新。什么意思呢?假如读入了一个数3,之前已经有了{2,6,18}这三个数,且构成这三个数的方案数分别为{1,2,3}。由我们的推算可知,加入3后,可以由2*3来使构成6的方案数加1,由6*3使构成18的方案数加1,由18*3使构成54的方案数加1。加上3本身,处理之后的已有数字和方案数分别为:{2,3,6,18,54}{1,1,3,4,1}。但是如果我们边处理边更新,会导致同一个3被重复计算。给6的方案数加1后,新增的这个已经用过3的方案,又与3一起更新了18的答案。所以应该把每次要修改的操作保存起来,把所有的待更新数更新完毕后,再应用修改到方案数组中。

由于k较大,可能出现的数字不定,所以可以通过STL map来作为数组。

时间复杂度大概是O(n log k)

#include<cstdio>
#include<map>
using std::map;
const long long maxn=1e3;
const long long mod=1000000007;
long long n,k;
long long a[maxn+5];
map<long long,long long>d;
map<long long,bool> ment;
long long mentd[maxn+5];
struct addo{
long long to,val;
addo(long long to=0,long long val=0):to(to),val(val){}
}add[maxn+5];
inline void read(long long &x){
x=0;char c;long long f=1;
do{c=getchar();if(c=='-')f=-1;}while(c>'9'||c<'0');
do{x=x*10+c-'0';c=getchar();}while(c>='0'&&c<='9');x*=f;
}
void work(){
for(register long long i=1;i<=n;++i){
read(a[i]);
if(k%a[i]!=0)continue;
long long lmentd=mentd[0],tadd=0;
for(register long long j=1,y;j<=lmentd;++j){
if(k%(y=a[i]*mentd[j])!=0)continue;
add[++tadd]=addo(y,d[mentd[j]]);
if(!ment[y]){
mentd[++mentd[0]]=y;
ment[y]=true;
}
}
for(register long long j=1;j<=tadd;++j){
d[add[j].to]+=add[j].val;
d[add[j].to]%=mod;
}
d[a[i]]++;
d[a[i]]%=mod;
if(!ment[a[i]]){
mentd[++mentd[0]]=a[i];
ment[a[i]]=true;
}
}
printf("%lld\n",d[k]);
}
int main(){
long long T;
read(T);
while(T--){
read(n);read(k);
work();
if(T){
ment.clear();
mentd[0]=0;
}
}
return 0;
}

整数划分

将N分为若干个不同整数的和,有多少种不同的划分方式,例如:n = 6,{6} {1,5} {2,4} {1,2,3},共4种。由于数据较大,输出Mod 10^9 + 7的结果即可。

1 \leq N \leq 50000

当成一个0/1背包问题,1N每个数是一件物品,背包的容积为N。把普通背包(求最大价值)改为求价值之和即可。

但是这种做法的时间复杂度为O(N^2),很显然过不了此题的数据范围。

考虑用g[i][j]表示考虑用i个数构成j的方案数。要求用的数各不相同,所以应该保证构造的数不出现重复。

g[i][j]表示用j个数构成i的方案数,由于每个数各不相同,最多的数的个数m满足(1+2+...+m=n)。计算得知m_{max}=316

i个数字来组成j,假如不选择数字1,那么方案数为g[i][j-i],也就是把构成j-ii个数每个都加上1;假如要选择数字1,为了保证前面没有数字1(题目要求所有数不相同),我们需要把前面i-1个数加上1,再给最后一位放一个1。方案数就是g[i-1][j-i](前i-1位构成j-i)。

选择1和不选择1,包含了所有的情况。

于是我们得到状态转移方程:

    \[g[i][j]=g[i-1][j-i]+g[i][j-i].\]

答案就是\sum_{i=1}^{316} g[i][n].

代码:

#include<cstdio>
#include<cmath>
const long long mod=1e9+7;
const long long maxn=5e4;
long long g[320][maxn+5];
long long ans;
long long n,m;
int main(){
    scanf("%lld",&n);
    g[0][0]=1;
    for(register int i=1;i<=319;++i){
        for(register int j=i;j<=n;++j){
            g[i][j]=(g[i][j-i]+g[i-1][j-i])%mod;
        }
    }
    for(register int i=1;i<=319;++i){
        ans+=g[i][n];
        ans%=mod;
    }
    printf("%lld\n",ans);
    return 0;
}