Submission #1696085


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;*/
	for(int i=1;i<=m;i++){
		scanf("%d%d",&q[i].l,&q[i].r);
		if(q[i].r<=q[i-1].r)m--,i--;
	}
	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]%mod);
	return 0;
} 

Submission Info

Submission Time
Task F - Shuffling
User vjudge4
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1589 Byte
Status WA
Exec Time 27 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:46:32: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&q[i].l,&q[i].r);
                                ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 900
Status
AC × 3
AC × 3
WA × 24
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 25 ms 70912 KB
subtask0_1.txt AC 26 ms 70912 KB
subtask0_2.txt AC 26 ms 70912 KB
subtask1_0.txt WA 26 ms 70912 KB
subtask1_1.txt WA 26 ms 70912 KB
subtask1_10.txt WA 26 ms 70912 KB
subtask1_11.txt WA 26 ms 70912 KB
subtask1_12.txt WA 26 ms 70912 KB
subtask1_13.txt WA 27 ms 70912 KB
subtask1_14.txt WA 26 ms 70912 KB
subtask1_15.txt WA 26 ms 70912 KB
subtask1_16.txt WA 26 ms 70912 KB
subtask1_17.txt WA 26 ms 70912 KB
subtask1_18.txt WA 26 ms 70912 KB
subtask1_19.txt WA 26 ms 70912 KB
subtask1_2.txt WA 27 ms 70912 KB
subtask1_20.txt WA 27 ms 70912 KB
subtask1_21.txt WA 26 ms 70912 KB
subtask1_22.txt WA 26 ms 70912 KB
subtask1_23.txt WA 26 ms 70912 KB
subtask1_3.txt WA 26 ms 70912 KB
subtask1_4.txt WA 26 ms 70912 KB
subtask1_5.txt WA 26 ms 70912 KB
subtask1_6.txt WA 26 ms 70912 KB
subtask1_7.txt WA 26 ms 70912 KB
subtask1_8.txt WA 26 ms 70912 KB
subtask1_9.txt WA 26 ms 70912 KB