好题
第一问不难，毕竟二分答案类的题目在USACO上都练了好多遍了
第二问充分的暴露了我dp渣的本性
一开始楞是没想出来
f[i,j]表示到第i根木棒切了j刀满足最长段小于等于ans的方案数
式子是这样的f[i,j]=sigma(f[k,j-1]) if sum[i]-sum[k]<=ans
然后发现我的优化水平还是不错的，
首先是空间上的问题，观察得知，切这刀的方案数只与切前一刀有关，于是我们滚动数组
再看时间，观察k的选取，与这是第几刀无关
再看，如果满足sum[i]-sum[k]<=ans 那么k~i-1一定都是符合的切法
于是我们预先处理一下即可
复杂度为O(nlogn+mn)
const mo=;
var f:array[..,..] of longint;
sum,s,a,b:array[..] of longint;
p,l,r,mid,n,m,i,j,t,ans:longint; function check(s:longint):boolean;
var t,len,i:longint;
begin
t:=;
len:=;
p:=;
for i:= to n do
if len+a[i]>s then
begin
inc(t);
if t>m then exit(false);
if len>p then p:=len;
len:=a[i];
end
else len:=len+a[i];
if len>p then p:=len;
exit(true);
end;
begin
readln(n,m);
for i:= to n do
begin
readln(a[i]);
sum[i]:=sum[i-]+a[i];
if l<a[i] then l:=a[i];
end;
r:=sum[i];
while l<=r do //二分答案
begin
mid:=(l+r) shr ;
if check(mid) then
begin
ans:=p;
r:=p-;
end
else l:=mid+;
end;
for i:= to n do
if sum[i]<=ans then f[,i]:= else break;
j:=;
for i:= to n do //预处理
begin
while sum[i]-sum[j]>ans do inc(j);
b[i]:=j;
end;
p:=;
t:=f[p,n];
for i:= to m do
begin
p:=-p;
fillchar(s,sizeof(s),);
for j:= to n do
begin
if b[j]-> then r:=b[j]- else r:=; //小细节
f[p,j]:=(s[j-]-s[r]+mo) mod mo;
s[j]:=(s[j-]+f[-p,j]) mod mo;
end;
t:=(t+f[p,n]) mod mo;
end;
writeln(ans,' ',t);
end.