/category/dp/ /archives/159/ 2016-12-26T15:09:00+08:00 ###Description 给出一个长度为N由B、W、X三种字符组成的字符串S，你需要把每一个X染成B或W中的一个。 对于给出的K，问有多少种染色方式使得存在整数a,b,c,d使得: 1 /archives/156/ 2016-12-20T09:03:00+08:00 ###Description 农夫栋栋近年收入不景气，正在他发愁如何能多赚点钱时，他听到隔壁的小朋友在讨论兔子繁殖的问题。 问题是这样的：第一个月初有一对刚出生的小兔子，经过两个月长大后，这对兔子从第三个月开始，每个月初生一对小兔子。新出生的小兔子生长两个月后又能每个月生出一对小兔子。问第n个月有多少只兔子？ 聪明的你可能已经发现，第n个月的兔子数正好是第n个Fibonacci(斐波那契)数。栋栋不懂什么是Fibonacci数，但他也发现了规律：第i+2个月的兔子数等于第i个月的兔子数加上第i+1个月的兔子数。前几个月的兔子数依次为： 1 1 2 3 5 8 13 21 34 … 栋栋发现越到后面兔子数增长的越快，期待养兔子一定能赚大钱，于是栋栋在第一个月初买了一对小兔子开始饲养。 每天，栋栋都要给兔子们喂食，兔子们吃食时非常特别，总是每k对兔子围成一圈，最后剩下的不足k对的围成一圈，由于兔子特别害怕孤独，从第三个月开始，如果吃食时围成某一个圈的只有一对兔子，这对兔子就会很快死掉。 我们假设死去的总是刚出生的兔子，那么每个月的兔子数仍然是可以计算的。例如，当k=7时，前几个月的兔子数依次为： 1 1 2 3 5 7 12 19 31 49 80 … 给定n，你能帮助栋栋计算第n个月他有多少对兔子么？由于答案可能非常大，你只需要告诉栋栋第n个月的兔子对数除p的余数即可。 ###Input 输入一行，包含三个正整数n, k, p。 ###Output 输出一行，包含一个整数，表示栋栋第n个月的兔子对数除p的余数。 ###Sample Input 6 7 100 ###Sample Output 7 ###Solution 按模k余数写出数列，则为 1,1,...,a,0, a,a,...,b,0, b,b,...,c,0, ... 这个数列最后有可能每一排首项循环，也有可能不再出现0 每次求a的逆元，则其在fib数列中首次出现位置就是a后面下一个0的位置，如果没有0特判 ###Code ```c++ #include typedef long long ll; #define fo0(i,n) for(int i=0,i##end=n;i=s[tt].len;n-=s[tt++].len)r*=s[tt].x; return r*pow((mat){0,1,0,1,1,0,0,0,1},n); } int main() { scanf("%lld%d%d",&n,&k,&p); for(int i=3;;i++) { f[i]=f[i-1]+f[i-2]; if(f[i]>=k)f[i]-=k; if(!pos[f[i]])pos[f[i]]=i; if(f[i]==1&&f[i-1]==0)break; } int ns=1,sc=1; for(;!p2[ns];sc++) { s[sc].st=ns; p2[ns]=sc; int t1,t2; exgcd(k,ns,t1,t2); if(t2 /archives/74/ 2016-11-15T08:21:00+08:00 ###Description “寄没有地址的信，这样的情绪有种距离，你放着谁的歌曲，是怎样的心心静，能不能说给我听。” 失忆的Eden总想努力地回忆起过去，然而总是只能清晰地记得那种思念的感觉，却不能回忆起她的音容笑貌。 记忆中，她总是喜欢给Eden出谜题：在 valentine’s day 的夜晚，两人在闹市中闲逛时，望着礼品店里精巧玲珑的各式玩偶，她突发奇想，问了 Eden这样的一个问题：有n个玩偶，每个玩偶有对应的价值、价钱，每个玩偶都可以被买有限次，在携带的价钱m固定的情况下，如何选择买哪些玩偶以及每个玩偶买多少个，才能使得选择的玩偶总价钱不超过m，且价值和最大。众所周知的，这是一个很经典的多重背包问题，Eden很快解决了，不过她似乎因为自己的问题被飞快解决感到了一丝不高兴，于是她希望把问题加难：多次 询问，每次询问都将给出新的总价钱，并且会去掉某个玩偶（即这个玩偶不能被选择），再问此时的多重背包的答案（即前一段所叙述的问题）。 这下Eden 犯难了，不过Eden不希望自己被难住，你能帮帮他么？ ###Input 第一行一个数n，表示有n个玩偶，玩偶从0开始编号 第二行开始后面的 n行，每行三个数 ai, bi, c i，分别表示买一个第i个玩偶需要的价钱，获得的价值以及第i个玩偶的限购次数。 接下来的一行为q，表示询问次数。 接下来q行，每行两个数di. ei表示每个询问去掉的是哪个玩偶（注意玩偶从0开始编号）以及该询问对应的新的总价钱数。（去掉操作不保留，即不同询问互相独立） ###Output 输出q行，第i行输出对于第 i个询问的答案。 ###Sample Input 5 2 3 4 1 2 1 4 1 2 2 1 1 3 2 3 5 1 10 2 7 3 4 4 8 0 5 ###Sample Output 13 11 6 12 4 ###Solution 多重背包+分治背包 递归处理[l,r)，每次加入左半部分的点，处理右边，再加入右边，处理左边 时间复杂度$$O(n^2log^2n+q)$$ ###Code ```c++ #include typedef unsigned char uchar; typedef unsigned int uint; typedef long long ll; typedef unsigned long long ull; typedef double db; typedef long double ldb; #define xx first #define yy second template inline T max(T a,T b){return a>b?a:b;} template inline T min(T a,T b){return a0?a:-a;} template inline void repr(T &a,T b){if(ab)a=b;} template T gcd(T a,T b){if(b)return gcd(b,a%b);return a;} #define mp(a,b) std::make_pair(a,b) #define pb push_back #define lb(x) ((x)&(-(x))) #define sqr(x) ((x)*(x)) #define pm(a,b,c,d) a=(a+(ll)(b)*(c))%(d) struct _toy { int a,b,c; }toy[1000]; struct _qr { int w,ans,ne; }qr[300001]; int p[1000],n,q,f[11][1001]; inline void merge(int *s,int a,int b) { for(int i=1000;i>=a;i--) repr(s[i],max(s[i-1],s[i-a]+b)); } void solve(int l,int r,int d) { if(l+1==r) { for(int i=p[l];i;i=qr[i].ne) qr[i].ans=f[d][qr[i].w]; } else { int p=(l+r)>>1; memcpy(f[d+1],f[d],sizeof(f[d])); for(int i=l;i /archives/21/ 2016-09-09T20:13:00+08:00 ###Description 阿申准备报名参加GT考试，准考证号为N位数X1X2....Xn(0