Submission #1696078
Source Code Expand
#include<bits/stdc++.h> using namespace std; long long fac[2005],fx[2005],inv[2005]; const int mod=1e9+7; void init() { fac[1]=1;for(int i=2;i<=2000;++i)fac[i]=fac[i-1]*i%mod; inv[0]=inv[1]=1;for(int i=2;i<=2000;++i)inv[i]=(mod-mod/i)%mod*inv[mod%i]%mod; fx[0]=fx[1]=1;for(int i=2;i<=2000;++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][2005]; 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 | vjudge2 |
Language | Bash (GNU bash v4.3.11) |
Score | 0 |
Code Size | 1490 Byte |
Status | RE |
Exec Time | 6 ms |
Memory | 692 KB |
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 | RE | 6 ms | 692 KB |
subtask0_1.txt | RE | 3 ms | 568 KB |
subtask0_2.txt | RE | 3 ms | 568 KB |
subtask1_0.txt | RE | 3 ms | 572 KB |
subtask1_1.txt | RE | 3 ms | 576 KB |
subtask1_10.txt | RE | 3 ms | 568 KB |
subtask1_11.txt | RE | 3 ms | 572 KB |
subtask1_12.txt | RE | 3 ms | 564 KB |
subtask1_13.txt | RE | 3 ms | 568 KB |
subtask1_14.txt | RE | 3 ms | 572 KB |
subtask1_15.txt | RE | 4 ms | 572 KB |
subtask1_16.txt | RE | 3 ms | 572 KB |
subtask1_17.txt | RE | 3 ms | 568 KB |
subtask1_18.txt | RE | 3 ms | 568 KB |
subtask1_19.txt | RE | 3 ms | 568 KB |
subtask1_2.txt | RE | 3 ms | 572 KB |
subtask1_20.txt | RE | 3 ms | 568 KB |
subtask1_21.txt | RE | 3 ms | 572 KB |
subtask1_22.txt | RE | 3 ms | 568 KB |
subtask1_23.txt | RE | 4 ms | 572 KB |
subtask1_3.txt | RE | 3 ms | 572 KB |
subtask1_4.txt | RE | 3 ms | 568 KB |
subtask1_5.txt | RE | 4 ms | 568 KB |
subtask1_6.txt | RE | 4 ms | 572 KB |
subtask1_7.txt | RE | 3 ms | 572 KB |
subtask1_8.txt | RE | 3 ms | 568 KB |
subtask1_9.txt | RE | 3 ms | 572 KB |