2018沈阳M(可逆背包+线性优化完全背包+生成函数)

77 阅读 0 评论 51 点赞

我是靠谱客的博主美丽项链，最近开发中收集的这篇文章主要介绍2018沈阳M(可逆背包+线性优化完全背包+生成函数)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题意：给定ai和bi，表示第i个商店有ai个商品可以买，单价为bi元，给出m个询问，问用c元在l~r商店买东西的方案数

可能这是窝打acm以来做过的最好的题了。。学到了太多东西。。orz

统计方案数的背包是可以逆的。。可以参考牛客多校2E。。

然后显然可以做个前缀，求出前r个物品的背包，这个多重背包的复杂度是O(ncb)，用二进制可以优化到O(nclogb)，但是有T组数据的存在这个复杂度比较危险。如果套用单调队列优化背包的套路，对余数一一进行转移求区间和可以优化到O(nc)。。

然后对m次询问，如果套用牛客多校的撤销做完全背包合并复杂度是O(mc^2)，T了。。

然后cls跟窝说要预处理可逆背包，那么就预处理吧。。

预处理就是把每个物品放进去加进去做完全背包，维护的时候把系数取反就可以了。。

这个其实就把完全背包的过程先做了，剩下的就把背包合并一下就可以了。。

合并的复杂度又是O(c^2)。。。然而只需要求<=c的方案数，所以直接枚举一个背包的容量，求另一个背包的前缀和就可以了。。

复杂度是O(T(n+m)c)

然后看到cjb又交了一发跑的飞快于是很好奇他的写法。。

结果是他求背包的时候是利用可逆背包的性质把O(ncb)降到O(nc)的。。于是很好奇他如何做到的，然后看了半天没看懂，请来fffasttime他说这个可以用生成函数解释？？

一种物品的背包可以看成 $sum_{i=0}^{a}x^{ib}=frac{1-x^{(a+1)b}}{1-x^b}$ ，所以可以先用(a+1)b去做一个01背包(系数为负)，再除以一个x^b的(系数为负)01背包就可以了。。

可是怎么除呢？？其实这个和带撤销背包就是一个套路了，反着做一遍完全背包就可以了。。即对x^b做一遍(系数为正)完全背包

从生成函数来看， $frac{1}{1-x^b}=sum_{i=0}^{infty}x^{bi}$ ，即做一遍完全背包就可以等效。。

然后对可逆背包的预处理，由于 $frac{1-x^b}{1-x^{(a+1)*b}}=(1-x^b)*sum_{i=0}^{infty}x^{i*(a+1)b}$ ，于是反过来对x^b做01背包，对(a+1)b做完全背包就可以了。。。

这题让窝见识到了各位大佬的强大

orz cls orz cjb orz fffasttime泥萌怎么这么强蛙orz!!!!

解法一：

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=1;i<=n;++i)
#define mp make_pair
#define pb push_back
#define x0 gtmsub
#define y0 gtmshb
#define x1 gtmjtjl
#define y1 gtmsf
const int len=1e3+5,N=1e4+5,MOD=1e9+7;
int a[N],b[N],g[N][len],r[N][len],T,n,m;
void mul(int *f,int u){
for(int i=len-1;i>=u;--i)f[i]=(f[i]-f[i-u]+MOD)%MOD;
}
void div(int *f,int u){
for(int i=u;i<len;++i)f[i]=(f[i]+f[i-u])%MOD;
}
int main()
{
g[0][0]=1;
for(int i=0;i<len;++i)r[0][i]=1;
scanf("%d",&T);
rep(Case,T){
printf("Case #%d:n",Case);
scanf("%d%d",&n,&m);
rep(i,n)scanf("%d%d",a+i,b+i),a[i]=(a[i]+1)*b[i];
rep(i,n){
memcpy(g[i],g[i-1],sizeof(g[i]));
mul(g[i],a[i]);div(g[i],b[i]);
memcpy(r[i],r[i-1],sizeof(r[i]));
mul(r[i],b[i]);div(r[i],a[i]);
}
int ans=0;
rep(i,m){
int L,R,c;
scanf("%d%d%d",&L,&R,&c);
L=(L+ans)%n+1;
R=(R+ans)%n+1;
if(L>R)swap(L,R);
ans=0;
for(int i=0;i<=c;++i)ans=(ans+1ll*g[R][i]*r[L-1][c-i])%MOD;
printf("%dn",ans);
}
}
return 0;
}

解法二：

/**
*　　　　　　　　┏┓　　 　┏┓
* 　　　　　　　┏┛┗━━━━━━━┛┗━━━┓
* 　　　　　　　┃　　　　　　　┃ 　
* 　　　　　　　┃　　　━　　 　┃
* 　　　　　　　┃　＞　　　＜　┃
* 　　　　　　　┃　　　　　　　┃
* 　　　　　　　┃...　⌒　... 　┃
* 　　　　　　　┃　　　　　　　┃
* 　　　　　　　┗━┓　　　┏━┛
* 　　　　　　　　　┃　　　┃　Code is far away from bug with the animal protecting　　　　　　　　　　
* 　　　　　　　　　┃　　　┃
神兽保佑,代码无bug
* 　　　　　　　　　┃　　　┃　　　　　　　　　　　
* 　　　　　　　　　┃　　　┃
　　　　　　
* 　　　　　　　　　┃　　　┃
* 　　　　　　　　　┃　　　┃　　　　　　　　　　　
* 　　　　　　　　　┃　　　┗━━━┓
* 　　　　　　　　　┃　　　　　　　┣┓
* 　　　　　　　　　┃　　　　　　　┏┛
* 　　　　　　　　　┗┓┓┏━┳┓┏┛
* 　　　　　　　　　　┃┫┫　┃┫┫
* 　　　　　　　　　　┗┻┛　┗┻┛
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,l,r) for(int i=l;i>=r;i--)
#define link(x) for(edge *j=h[x];j;j=j->next)
#define mem(a) memset(a,0,sizeof(a))
#define ll long long
#define eps 1e-8
#define succ(x) (1LL<<(x))
#define lowbit(x) (x&(-x))
#define sqr(x) ((x)*(x))
#define NM 10005
#define nm 1005
#define pi 3.1415926535897931
using namespace std;
const ll inf=1e9+7;
ll read(){
ll x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return f*x;
}
int n,m,_x,_y,_t,ca,tot;
int ans,d[NM][nm],g[NM][nm];
void mul(int*d,int t){dec(i,tot,t){d[i]-=d[i-t];if(d[i]<0)d[i]+=inf;}}
void div(int*d,int t){inc(i,t,tot){d[i]+=d[i-t];if(d[i]>inf)d[i]-=inf;}}
int main(){
//freopen("data.in","r",stdin);
tot=1000;
int _=read();while(_--){
n=read();m=read();
printf("Case #%d:n",++ca);
inc(i,0,n)inc(j,0,tot)g[i][j]=d[i][j]=0;
ans=0;g[0][0]=d[0][0]=1;
inc(i,1,n){
int a=read(),b=read();a=(a+1)*b;
memcpy(d[i],d[i-1],sizeof(d[i]));
memcpy(g[i],g[i-1],sizeof(g[i]));
mul(d[i],a);div(d[i],b);
mul(g[i],b);div(g[i],a);
}
/*inc(i,0,n)g[i][0]=1;
inc(i,0,n)inc(j,1,tot)inc(k,0,j-1)g[i][j]-=d[i][j-k]*g[i][k];*/
/*printf("%d %dn",a[1],b[1]);
inc(i,1,n){printf("%d:",i);inc(j,0,20)printf("%2d ",g[i][j]);putchar('n');}*/
inc(i,0,n)inc(j,1,tot){
g[i][j]+=g[i][j-1];
if(g[i][j]>inf)g[i][j]-=inf;
}
while(m--){
_x=(read()+ans)%n+1;_y=(ans+read())%n+1;_t=read();
if(_x>_y)swap(_x,_y);ans=0;
inc(i,0,_t){
ans+=1ll*d[_y][i]*g[_x-1][_t-i]%inf;
if(ans>inf)ans-=inf;
}
printf("%dn",ans);
}
}
return 0;
}

M. Renaissance Past in Nancy

time limit per test

6 seconds

memory limit per test

1024 megabytes

input

standard input

output

standard output

Nancy used to be known for its Art Nouveau quarter, the rum baba and good King Stanislas Leszczynski, the deposed Polish king who gave the city its gorgeously frilly architectural centrepiece in the 18th century.

But in 2013, Nancy rediscovered its Renaissance past, with events and exhibitions all around town this summer, from the fine art museum to the thermal establishment and the botanical gardens. Now it is time for me to discover the old town's Renaissance relics and the Utopian town-planning schemes of Duke Charles III, from the days when Nancy was capital of a powerful independent duchy at the crossroads between northern and southern Europe.

The old and new towns are seamlessly connected today. The new city or Ville Neuve laid out in 1588 is still the commercial heart of the city with its shops and banks, and covered by food markets in the street near the square originally planned for the cathedral.

In this autumn, I have the privilege of spending a several-months-long holiday in Ville Neuve. Daily contemplations always follow the breakfasts together with baguettes' sweet and smooth. What makes a baguette better is not La vache qui rit cheese, but where I get it. But why should people who program computers be so concerned about the number of food markets in a street? I do label those food markets which supply baguettes in the street from 1

to ?

At each glimmering daybreak came, I carry several one-euro coins and make a plan to visit several consecutive food markets. Regardless of winds and rains, a food market always offers a fixed number of baguettes at a fixed price. Two different food markets may be different: The numbers of their daily baguettes offered and the prices differ.

The early bird catches the worm. Since there is no need to worry about other customers, enough money makes me free to buy all the baguettes in a food market or be blind and go to the next market.

But why should people just like you be so concerned about the number of different ways that I have to purchase baguettes? They even double-check with me that I may cost nothing and starve, or spend any amount of money that I have. As what theorists always say in a knapsack-like problem, two ways to purchase baguettes are different if, at some markets, the numbers of baguettes purchased vary.

A man who pursuits high efficiency like you tries to tell me the number of ways I have once he confirmed the amount of money I carry and my visit plan day after day. An undisciplined man like me, though I have made a long list of plans for all days, decides to make a new plan for the next day once I received your reply about one day. I use ???????

to denote the number in your reply and set it to zero before my first day in Ville Neuve.

On a day, I check what I made in the original plan, say ?′

and ?′ the index of the first food market I decided to visit, and of the last one, and say ?

the number of one-euro coins I decided to carry. A transformation like an encryption

?=min{((?′+???????)mod?)+1,((?′+???????)mod?)+1}

and

?=max{((?′+???????)mod?)+1,((?′+???????)mod?)+1}

shows me a new plan, where min{?,?}

and max{?,?} correspond to the minimum and the maximum of ? and ? respectively, and that is what I execute this morning. You need to tell me the number you calculate for this day and I will set ??????? to your reply in modulo (109+7)

Input

The input contains several test cases, and the first line contains a positive integer ?

indicating the number of test cases which is up to 1000

For each test case, the first line contains two integers ?

and ? which are the number of food markets in the street and the total number of days I plan to spend in Ville Neuve respectively, where 1≤?,?≤10000

Each of the following ?

lines describes a food market. The ?-th line of them contains two integers ?? and ?? indicating the number of baguettes provided by the ?-th food market and its unit price in euro respectively, where 1≤??,??≤1000

Each of the following ?

lines contains three integers ?′,?′ and ? describing the original plan I made for one day, where 1≤?′≤?′≤? and 1≤?≤1000

We guarantee that no more than 10

test cases satisfy ?>100 or ?>100

Output

For each test case, output "Case #x:" (without quotes) in a line at first, where x is the test case number starting from 1

Then for each day, output an integer in a line indicating the number of the different ways to purchase baguettes on this day in modulo the prime number (109+7)

Example

Input

Copy

Output

Copy

Case #1:
2
3
4

Note

In the sample case, I visit the first market and the second market with only one coin on the first day. Thus I can buy nothing or buy one baguette in the first shop. On the second day, I visit all markets carrying two coins, so I can buy nothing or buy one baguette in any one of the first two markets. On the last day, I visit the first two markets again but carry with me three coins. Then I have four different ways to purchase baguettes, but I am too tired to list them all after a three-day shopping.