Submission #1696082
Source Code Expand
#include<bits/stdc++.h>
using namespace std;
long long fac[3005],fx[3005],inv[3005];
const int mod=1e9+7;
void init()
{
fac[1]=1;for(int i=2;i<=3001;++i)fac[i]=fac[i-1]*i%mod;
inv[0]=inv[1]=1;for(int i=2;i<=3001;++i)inv[i]=(mod-mod/i)%mod*inv[mod%i]%mod;
fx[0]=fx[1]=1;for(int i=2;i<=3001;++i)fx[i]=inv[i]*fx[i-1]%mod;
}
struct node
{
int l,r;
}p[3005],q[3005];
int a[3005];
char s[3005];
long long dp[3005][3005];
int n,m;
long long C(int n,int m)
{
return fac[n]*fx[m]%mod*fx[n-m]%mod;
}
int main()
{
init();
scanf("%d%d",&n,&m);scanf("%s",s);
for(int i=0;i<n;++i)
a[i+1]=a[i]+s[i]-'0';
for(int i=1;i<=m;++i)
scanf("%d%d",&p[i].l,&p[i].r);
int cnt=0;
for(int i=1;i<=m;i++)
{
if(p[i].l==p[i+1].l&&p[i].r<=p[i+1].r){
continue;
}
int j=i+1;
while(p[i].l<=p[j].l&&p[i].r>=p[j].r&&j<=m)
{
++j;
}
q[++cnt].l=p[i].l;q[cnt].r=p[i].r;
i=j-1;
}m=cnt;
memset(dp,0,sizeof(dp));
q[m+1].l=n+1;q[m+1].r=n+1;a[n+1]=a[n];
dp[1][a[q[1].r]-a[q[1].l-1]]=1;
for(int i=1;i<=m;++i){
if(q[i].r<q[i+1].l){
int tmp=a[q[i+1].r]-a[q[i+1].l-1];
for(int j=0;j<=q[i].r-q[i].l+1;++j)
dp[i+1][tmp]=(dp[i+1][tmp]+dp[i][j]*C(q[i].r-q[i].l+1,j))%mod;
}
else
{
int tmp=a[q[i+1].r]-a[q[i].r];
int t=q[i].r-q[i].l+1;
int pre=q[i+1].l-q[i].l;
int len=q[i].r-q[i+1].l+1;
for(int j=0;j<=t;++j)
for(int k=max(0,j-pre);k<=j&&k<=len;++k){
dp[i+1][tmp+k]=(dp[i+1][tmp+k]+dp[i][j]*C(pre,j-k))%mod;
}
}
}
printf("%lld",dp[m+1][0]);
return 0;
}
Submission Info
Submission Time |
|
Task |
F - Shuffling |
User |
vjudge5 |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
1490 Byte |
Status |
WA |
Exec Time |
22 ms |
Memory |
70912 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:26:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&n,&m);scanf("%s",s);
^
./Main.cpp:26:35: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&n,&m);scanf("%s",s);
^
./Main.cpp:30:31: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&p[i].l,&p[i].r);
^
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 900 |
Status |
|
|
Set Name |
Test Cases |
Sample |
subtask0_0.txt, subtask0_1.txt, subtask0_2.txt |
All |
subtask0_0.txt, subtask0_1.txt, subtask0_2.txt, subtask1_0.txt, subtask1_1.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_2.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_3.txt, subtask1_4.txt, subtask1_5.txt, subtask1_6.txt, subtask1_7.txt, subtask1_8.txt, subtask1_9.txt |
Case Name |
Status |
Exec Time |
Memory |
subtask0_0.txt |
AC |
20 ms |
70912 KB |
subtask0_1.txt |
AC |
20 ms |
70912 KB |
subtask0_2.txt |
AC |
20 ms |
70912 KB |
subtask1_0.txt |
WA |
21 ms |
70912 KB |
subtask1_1.txt |
WA |
21 ms |
70912 KB |
subtask1_10.txt |
WA |
22 ms |
70912 KB |
subtask1_11.txt |
AC |
21 ms |
70912 KB |
subtask1_12.txt |
WA |
21 ms |
70912 KB |
subtask1_13.txt |
WA |
22 ms |
70912 KB |
subtask1_14.txt |
WA |
22 ms |
70912 KB |
subtask1_15.txt |
WA |
21 ms |
70912 KB |
subtask1_16.txt |
WA |
22 ms |
70912 KB |
subtask1_17.txt |
WA |
21 ms |
70912 KB |
subtask1_18.txt |
WA |
21 ms |
70912 KB |
subtask1_19.txt |
WA |
21 ms |
70912 KB |
subtask1_2.txt |
WA |
21 ms |
70912 KB |
subtask1_20.txt |
WA |
21 ms |
70912 KB |
subtask1_21.txt |
WA |
21 ms |
70912 KB |
subtask1_22.txt |
WA |
21 ms |
70912 KB |
subtask1_23.txt |
WA |
21 ms |
70912 KB |
subtask1_3.txt |
WA |
21 ms |
70912 KB |
subtask1_4.txt |
WA |
21 ms |
70912 KB |
subtask1_5.txt |
WA |
21 ms |
70912 KB |
subtask1_6.txt |
WA |
21 ms |
70912 KB |
subtask1_7.txt |
WA |
21 ms |
70912 KB |
subtask1_8.txt |
WA |
21 ms |
70912 KB |
subtask1_9.txt |
WA |
21 ms |
70912 KB |